现有大写英文字母A-Z，个数分别为C[i]，总共可以组成多少个长度在[1,K]之间的不同串？答案对998244353取模。1<=K<=1000,0<=C[i]<=1000分析：记dp[i][k]表示前i类字母构成长度为k的不同方案数，枚举第i类字母的个数j进行转移。#include<bits/stdc++.h>usingi64=longlong;templat

Counting苦手本来都准备白兰了，但祁神发现了关键的性质然后就发现可做了稍作观察我们就可以发现对于一个最终合法的序列，其任意一个前缀中白球的数量都必须大于等于这段前缀的颜色数直接对长度为\(n\timesk\)的序列DP复杂度显然不能接受，不过我们发现我们只关心每种颜色出现

B-MST对于整个序列进行一次kruskal对于序列中如果需要访问的点数小于300那么将所有的点的边存入序列中进行kruskal如果大于300那么直接对于所有的点进行kruskal点击查看代码#include<bits/stdc++.h>#defineintlonglong#defineall(x)x.begin(),x.end()#defineral

先判掉\(k>\min(n,m)\)的情况。首先有个明显的计算最长合法括号子序列的贪心方法：初始一个值为\(0\)的计数器，从左到右枚举每个字符，遇到(时将计数器加一，遇到)时如果计数器不为\(0\)就减一然后将答案加一。考虑绘制它的折线图。初始时纵坐标为\(0\)，从左到右枚举每个字符

我们先默认第一头牛是John的，另一种情况本质相同，最后答案乘上\(2\)就可以了。先说结论：我们将相邻两头牛配对，那么最终答案即满足至少一对牛间隔了奇数个空位的方案数。证明很简单，分\(3\)种情况讨论：每对牛间都间隔了奇数个空位。那么John开始时让所有牛往右行动，在Nhoj行

给出T次询问，每次给出n和m，求C(n,m)对998244353取模的结果。为了避免输出太多内容，只需要输出所有查询结果的异或和。1<=T<=5E6;0<=m<=n<=5E6先O(n)预处理出所有数的阶乘及其对应的乘法逆元，然后O(1)处理每次询问。#include<bits/stdc++.h>usingnamespacestd;#defineintlon

有T次询问，每次给出整数n,m,p，计算C(n+m,n)%p的值。输入保证p为质数。1<=n,m,p<=1E5;1<=T<=10n较大，p较小且为质数时，可以用lucas定理来计算组合数：lucas(n,k,p)=lucas(n/p,k/p,p)*C(n%p,k%p,p)#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definer

其实不会反演也可以做。首先显然要考虑给你每个数个数，怎么计数。最简单的方法是从大枚举到小，设\(c_i\)为\(i\)的个数，\(f_i\)为\(\gcd=i\)的\(k\)元组出现了多少次，则\(f_i=\binom{c_i}{k}-\sum_jf_{ij}\)，就是\(\gcd\)为\(i\)或\(i\)的倍数减去\(\gcd\)为\(i\)

同样来自@Explodingkonjac学长的讲题。但是我没认真听讲，所以自己想出来了。原本的想法是设对于每一组分别设\(dp_{i,j}\)为当前枚举到第\(i\)个位置，已经钦定了\(j\)个该组中的人投给自己组的方案数。转移就是枚举有多少人投给\(i\)然后容斥。但是可能是我没有处理好，总

DescriptionStackhasanarray$a$oflength$n$suchthat$a_i=i$forall$i$($1\leqi\leqn$).Hewillselectapositiveinteger$k$($1\leqk\leq\lfloor\frac{n-1}{2}\rfloor$)anddothefollowingoperationon$a$an

Description有\(N\)行\(N\)列的网格图，只能向下或向右走，合法路径的开端和结尾的格子上数字一样找到合法路径条数，对\(998244353\)取模\(1\leqN\leq400,1\leqa_{i,j}\leqN^2\)。Solution有一个\(O(n^4)\)的做法是每次枚举起点和终点然后用组合数计算答案，但是由于同

题目链接点击打开链接题目解法这种树的形态计数题首先可以想到\(prufer\)序列计数，如果没有任何限制，那么方案数为\(\prod\frac{(n-2)!}{deg_i}\)，其中\(deg_1=d_1-1,deg_i=d_i(2\lei\len)\)对于每个点分开求贡献考虑这个式子只和点的个数和子树内的\(\sumdeg\)有关

逆元\(a\divb\modp=a\times\dfrac{1}{b}\modp\)费马小定理:\(a^{p-1}\modp=1\)，也就是\(a^{p-1}\equiv1\pmodp\)。得$a^{p-2}\equiv\dfrac{1}{a}\pmodp$。所以可以直接带逆元为\(a^{p-2}\modp\)。\(\varphi(i)\)指\(1\)到\(i\)中有多少数与

HyperregularBracketStringsLuoguCF1830C题目描述给定一个数\(n\)和\(k\)个区间\(\left[l_i,r_i\right]\in[1,n]\)。我们定义，对于一个长度为\(n\)的，仅由(和)组成的合法括号序列，如果它的每一个区间\(\left[l_i,r_i\right]\)内的子串都是合法括号序列，那么这个

洛谷传送门AtCoder传送门下文的点\(1,2,3,4\)对应原题面中的\(S,T,U,V\)。直接对无向图欧拉回路计数不太好做。考虑给边定向。枚举有\(i\)条边是从\(1\)到\(2\)的。那么\(2\to1\)有\(a-i\)条边。由于这个图必须满足每个点的入度等于出度，设\(j\)条\(

PaperCuttingLuoguAT_keyence2019_f题面翻译有一个\((H+1)\times(W+1)\)的网格，网格中有\(H\)条水平线和\(W\)条竖直线。你需要执行\(K\)次操作，每次沿一条水平线或竖直线将网格切开。定义一次操作的权值为切割后网格被切分的块数。定义一个操作序列的权值为\(K\)

好久没写一整场CF或者AT的题解了，所以写一篇。C有点意思的题。考虑先放横再放竖，若确定所有横的位置，那么每列独立。所以记\(f_i\)表示第\(i\)列最多放多少个，考虑放一个横对\(f_i\)的影响。若\(n\)为奇数，那么第一行放满显然最优。若某时\(A>1\)，那么放一个\(2\times

NFLSOJACF294CShaassandLight考虑初始已点亮的灯将所有剩下的灯划分成的连续段。除开头结尾外，每个长为\(l\)的连续段有\(2^l\)种操作序列。开头结尾的连续段只有\(1\)种操作序列。从前往后将所有的操作序列归并到全局的操作序列里，拿组合数随便乱搞搞就好了。代码

传送门description给定\(n,k\)，求有多少个\(n\)的排列满足\(\foralli\in[k+1,n],\min\limits_{j=i-k}^{i-1}a_j<a_i\)。\(n,k\leq10^7\)solution设\(f_i\)表示对于给定的\(k\)，排列长度为\(i\)时的答案。转移时，我们考虑在头部添加新的数，设添加后的序列是\(\{

T1这个向下取整是没有用的，所以可以直接暴力dfs。然后要注意一下，如果数组里有\(1\)，你需要直接跳过，不然\(1\)可以使用无数次。inlineintksm(inta,intb){ intres=1; while(b){ if(b&1)res=res*a; a=a*a; b>>=1; } returnres;}intn,m;vector<int>a;unord

B-PermutationCheck16检查给定数组是不是一个排列C-POW63判断\(a^c\)和\(b^c\)谁大（int范围，\(c\ge1\)，\(a,b\)可能是负数）c=c%2?1:2，然后特判相等的情况，最后直接做pow比较D-KthExcluded713给定无重复正序数组，多次询问不在数组中的第\(k\)小的正整数

  我不能白给啊啊啊啊啊！！！！！  我会在这里将最近的考到的知识点罗列，也当是快速复习与刷题计划吧。Part1数论相关计数类Lucas定理点击查看代码constintMod=?;intpowM(intx,inty=Mod-2){ intret=1; while(y){ if(y&1)ret=1ll*ret*x%Mod; x=1ll

2023-08-0716:29:49题意有一个\(n\timesm\)的矩阵，求使得每个\(n\timesn\)的矩阵中都有正好\(k\)个点的方案数，方案数对\(1e9+7\)取模。\(1\len\le100,n\lem\le10^{18},0\lek\len^2\)。思路通过观察样例并且自己手玩了一些数据后，我们发现，假设第\(i\)列放了\(k\)

补完番后来做一下这道题。首先考虑\(n=1\)怎么做。一个很直观的感觉是，如果将一组集合进行首尾配对，即\((1,a_i),(2,a_i-1),\cdots\)，那么每一对中的两个数地位均等（即在所有方案中的出现次数均等）。证明可以考虑将所有方案进行配对，\((p_1,p_2,\cdots,p_l)\)对应\((a_i-p_l+1,\cd

思维+dp。如果像题意那样先放球再染色的话不是很好做。所以考虑有\(n\)个白球，\(n\)种其他颜色的球各\(k-1\)个。那么限制就是说对于每个前缀，白球的个数\(\ge\)其他颜色球的种数。所以就可以设\(f_{i,j}\)为放了\(i\)个白球，\(j\)种颜色的\(k-1\)个球的方案数。