不知道几百年前写的计数 dp 博客

计数是真的菜/kk，特地总结了一下这几天做的计数 $dp$.

CF1606E

设 $f_{i, j}$ 表示当场上还有 $i$ 个英雄，血量最大值为 $j$ 且最后无人存活的方案数。

当再进行一轮所有英雄都要寄时：

$f_{i, j} = j ^ i - (j - 1) ^ i$

$j ^ i$ 为所有血量的选择方案， $(j - 1) ^ i$ 为没有人血量 $j$ 的选择方案，即不合法方案。

当在进行一轮后还有英雄存活时：

枚举一个 $k$ 表示在进行一轮后剩余存活人数

$f_{i, j} = f_{k, j - i + 1} \times C ^ {i - k}_{i} \times (i - 1) ^ {i - k}$

时间复杂度 $O(n ^ 2 x log_2{n})$

$code : $

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long LL;
const int N = 507;
const int P = 998244353;
LL f[N][N];
LL c[N][N];
int n, m;

inline void Init()
{
	for (int i = 0; i <= n; i ++ )
		for (int j = 0; j <= i; j ++ )
			if (!j) c[i][j] = 1;
			else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
}

inline LL Qmi(LL a, LL b)
{
    LL res = 1, x = a;
    while (b)
    {
        if (b & 1) res = res * x % P;
        x = x * x % P;
        b >>= 1;
    }
    return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	
	Init();
	
	f[0][0] = 1;
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
		{
			if (i - 1 >= j)
			{
				f[i][j] = (Qmi(j, i) - Qmi(j - 1, i) + P) % P;
				continue;
			}
			for (int k = 1; k <= i; k ++ )
				f[i][j] = (f[i][j] + f[k][j - i + 1] * Qmi(i - 1, i - k) % P * c[i][k] % P) % P;
		}
	
	LL res = 0;
	for (int i = 1; i <= m; i ++ )
        res = (res + f[n][i]) % P;
	
	printf("%lld\n", res);

	return 0;
}

P3914 染色计数

样例好水，附一组

$input : $

5 4
3 1 2 3
2 1 2
2 2 3
2 1 4
2 1 3
1 2
1 3
3 4
3 5

$output : $

16

很简单的一道计数题/jy

设 $f_{u, x}$ 表示当前染色染到了 $u$ 节点，当前节点是颜色编号为 $x$ 时的方案数。

转移显然 ： $f_{u, x} = \prod\limits_{son}\sum\limits_{y = 1} ^ {m , y != x} f_{son, y}$

但是这样做时间复杂度时 $O(n ^ 3)$ 的。/kk

观察转移方程，发现可以通过预处理总和来将 $\sum$ 那一层优化掉

$code : $

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long LL;
const int P = 1e9 + 7;
const int N = 5007, M = N * 2;
int e[M], ne[M], h[N], idx;
int n, m;
int f[N][N];
int sum[N];

inline void Init()
{
	for (int i = 1; i <= n; i ++ )
		h[i] = -1;
}

inline void Add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

inline void Dp(int u, int fa)
{
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int v = e[i];
		if (v == fa) continue;
		Dp(v, u);
		for (int x = 1; x <= m; x ++ )
			f[u][x] = (LL)(f[u][x] * (LL)(sum[v] - f[v][x] + P) % P) % P;
	}
	for (int x = 1;x <= m; x ++ )
		sum[u] = (sum[u] + f[u][x]) % P;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ )
	{
		int x;
		scanf("%d", &x);
		for (int j = 1; j <= x; j ++ )
		{
			int y;
			scanf("%d", &y);
			f[i][y] = 1;
		}
	}
	
	Init();
	
	for (int i = 1; i < n; i ++ )
	{
		int u, v;
		scanf("%d%d", &u, &v);
		Add(u, v), Add(v, u);
	}
	
	Dp(1, -1);
	
	LL res = 0;
	for (int i = 1; i <= m; i ++ )
		res = (res + f[1][i]) % P;
	printf("%lld\n", res);
	
	return 0;
}

P6870 【COCI2019-2020#5】 Zapina

题不难，就是我是sb

设 $f_{i, j}$ 表示考虑到第 $i$ 个人， 前 $j$ 道题且有一个人开心的方案数。

让第 $i$ 个人开心：

$f_{i, j} = C_{j} ^ {i} \times$

不让第 $i$ 个人开心：

代码有点阴间，就不放了/hanx

CF367E

CF1051D

CF425E

注意是集合， 和 zzq 大佬讨论了好半天 我是sb。

设 $f_{i, j}$ 表示当右端点都小于等于 $i$ ，$f(S) = j$ 时的方案数

考虑怎么扩展 $j$

枚举上一个线段的右端点 $k$, 可得转移方程

$f_{i, j} = f_{k, j - 1} \times (2 ^ {i - k} - 1) \times $

写个屁，我不写了c

CF1515E

CF559C

S2OJ 排列题

小 Y 的背包计数问题

P5664 [CSP-S2019] Emiya 家今天的饭

寄，太难了/kk

发现前两个条件很好处理，但是第三个不会/kk

然后看了题解发现如果最多只会有一列不合法，考虑计算不合法状态然后容斥，容斥后就可以单独考虑每一行了。

设 $f_{i, j, k}$ 表示考虑到第 $i$ 行，一共选了 $j$ 道菜，枚举的当前列有 $k$ 道菜的方案数。

这样做时间复杂度是 $O(n ^ 3m)$ 的，可以获得 $84pts$ 的好成绩！

考虑优化，发现我们最后的答案要统计的是 $k > \lfloor \frac{j}{2} \rfloor$ 的 $dp$ 结果，我们只关心 $k$ 与 $j$ 的关系，这样就可以压掉一位。

至于怎么压，我们把上面的式子变一下形变为 $2k + n - j > n$

其中 $n - j$ 就是我们没有选的行数

那么就有了一种神奇的定义状态方法

我们设不选一行的权值为 $1$, 选当前列的权值为 $2$。 （这里的权值是我自己定义的，权值是根据上面式子的常数设的）

设 $f_{j, k}$ 表示考虑到第 $j$ 行， 权值为 $k$ 的方案数。

枚举一列 $i$ 可得转移方程

$f_{j, k} = (f_{j, k} + f_{j - 1, k} \times (cnt_j - a_{j, i})) \mod P$ 选了一个其他列

$f_{j, k} = (f_{j, k} + f_{j - 1, k - 2} \times a_{j, i}) \mod P$ 选了当前列

$f_{j, k} = (f_{j, k} + f_{j - 1, k - 1}) \mod P$ 没有选

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long LL;
const int P = 998244353;
const int N = 107, M = 2007;
int a[N][M];
LL cnt[N];
int n, m;
LL f[N][N * 2];
LL res = 1;

inline void Init()
{
	for (int i = 0; i <= n; i ++ )
		for (int j = 0; j <= n * 2; j ++ )
			f[i][j] = 0;
}

int main()
{
	freopen("in.in", "r", stdin);
	
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= m; j ++ )
		{
			scanf("%d", &a[i][j]);
			cnt[i] = (cnt[i] + a[i][j]) % P;
		}
		res = res * (cnt[i] + 1) % P;
	}
	res -- ;
	
	for (int i = 1; i <= m; i ++ )
	{
		Init();
		
		f[0][0] = 1;
		for (int j = 1; j <= n; j ++ )
			for (int k = 0; k <= j * 2; k ++ ) 
			{
				f[j][k] = (f[j][k] + f[j - 1][k] * (cnt[j] - a[j][i])) % P;
				if (k > 1) f[j][k] = (f[j][k] + f[j - 1][k - 2] * a[j][i]) % P;
				if (k) f[j][k] = (f[j][k] + f[j - 1][k - 1]) % P;
			}
		
		for (int i = n + 1; i <= n * 2; i ++ )
			res = ((res - f[n][i]) % P + P) % P;
	}
	
	printf("%lld\n", res);
	
	return 0;
}

woc之前写的题都好 naive 呀/kk

ARC059F

状态很显然，设 $f_{i,j}$ 表示用了 $i$ 次操作，现在串里面有 $j$ 个数字
发现删掉的数字可以是 $0$ 或 $1$,但是最后和串匹配上的必须一样，所以让 $\times 2$ 的贡献在删去时考虑
注意没有数也可以退格

$code$

#include<cstdio>
#include<iostream>
#include<cstring>
namespace IO{
	template<typename T> inline void rd(T &x){
		x=0;bool f=0;char c=0;
		while(c<'0'||c>'9') f|=c=='-',c=getchar();
		while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
		x=f?-x:x;
	}
	template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
	template<typename T> inline void wt(char c,T x){
		int stk[114],top=0;
		if(x<0) x=-x,putchar('-');
		do stk[++top]=x%10,x/=10; while(x);
		while(top) putchar(stk[top--]+'0');
		putchar(c);
	}
	template<typename T,typename ...Args> inline void wt(char c,T &x,Args &...args){wt(c,x),wt(c,args...);}
};
using namespace IO;
using namespace std;
const int P=1e9+7;
const int N=5007;
int f[N][N];
char s[N];
int n,m;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	rd(n);
	scanf("%s",s+1),m=strlen(s+1);
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++) f[i][j]=(f[i-1][max(j-1,0)]+2ll*f[i-1][j+1])%P;
	}
	wt('\n',f[n][m]);
	return 0;
}

CODE FESTIVAL 2016 Final

$n,m$ 很小，可以设很暴力的状态

发现我每次就是一条路径然后回到 $1$ 所在的强连通分量，不关心我现在在哪个点，所以设 $f_{i,j,k}$ 表示现在走了 $i$ 步， $1$ 所在的强连通分量里面有 $j$ 个点，现在走了 $k$ 个点还没有回到强连通分量里面

转移也非常简单

$f_{i+1,j,k+1}=f_{i,j,k} \times (n-j-k)$ 这条路径继续走不会到强连通分量

$f_{i+1,j,k}=f_{i,j,k} \times k$ 这条路径继续走，但是走到了之前这条路径经过的点

$f_{i+1,j+k,0}=f_{i,j,k} \times j$ 走回强连通分量

然后就没了.

$code$

#include<cstdio>
#include<iostream>
namespace IO{
	template<typename T> inline void rd(T &x){
		x=0;bool f=0;char c=0;
		while(c<'0'||c>'9') f|=c=='-',c=getchar();
		while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
		x=f?-x:x;
	}
	template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
	template<typename T> inline void wt(char c,T x){
		int stk[114],top=0;
		if(x<0) x=-x,putchar('-');
		do stk[++top]=x%10,x/=10; while(x);
		while(top) putchar(stk[top--]+'0');
		putchar(c);
	}
	template<typename T,typename ...Args> inline void wt(char c,T &x,Args &...args){wt(c,x),wt(c,args...);}
};
using namespace IO;
using namespace std;
const int P=1e9+7;
const int N=307;
int f[N][N][N];
int n,m;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	rd(n,m);
	f[0][1][0]=1;
	for(int i=0;i<=m;i++){
		for(int j=1;j<=n;j++){
			for(int k=0;k<=n;k++){
				f[i+1][j][k+1]=(f[i+1][j][k+1]+1ll*f[i][j][k]*(n-j-k))%P;
				f[i+1][j][k]=(f[i+1][j][k]+1ll*f[i][j][k]*k)%P;
				f[i+1][j+k][0]=(f[i+1][j+k][0]+1ll*f[i][j][k]*j)%P;
			}
		}
	}
	int res=0;
	for(int i=0;i<=n;i++) res=(res+f[m][n][i])%P;
	wt('\n',res);
	return 0;
}

Aizu 2439 Hakone

这是什么OJ/yiw

神仙题，根本想不到/kk

首先发现等于鸟用没有，直接去掉

看完题解之后我们知道可以建二分图，第 $i$ 个左部点向右部所有满足限制的点连边，现在就把问题转化成了二分图最大匹配数计数了

但是这是 $NP$ 的……

发现我们图建的非常好看，对于 $i$ 连的一定是点集 $[1,i]$ 或 $[i,n]$

有了这个东西好像就是能做的了

设 $f_{i,j,k}$ 表示同时考虑二分图两边的第 $i$ 个点，前面有 $j$ 个左部点没有匹配上， $k$ 个左部点没有匹配上

转移

$f_{i,j,k}=f_{i-1,j,k} \times k$ 当是小于号时

$f_{i,j,k}=f_{i-1,j,k} \times j$ 当是大于号时

$f_{i,j,k}=f_{i-1,j+1,k+1} \times k \times j$ 都可以转移

现在的复杂度是 $O(n^3)$ 的，已经可以通过本题

但是我们惊奇的发现，这个 $dp$ 的转移的时候 $j,k$ 加减的数值是一样的，也就是说，$dp$ 中的合法状态都满足 $j=k$ 所以我们可以直接去掉一维，这样时间复杂度就是 $O(n^2)$ 的了

$code$

#include<cstdio>
#include<iostream>
namespace IO{
	template<typename T> inline void rd(T &x){
		x=0;bool f=0;char c=0;
		while(c<'0'||c>'9') f|=c=='-',c=getchar();
		while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
		x=f?-x:x;
	}
	template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
	template<typename T> inline void wt(char c,T x){
		int stk[114],top=0;
		if(x<0) x=-x,putchar('-');
		do stk[++top]=x%10,x/=10; while(x);
		while(top) putchar(stk[top--]+'0');
		putchar(c);
	}
	template<typename T,typename ...Args> inline void wt(char c,T &x,Args &...args){wt(c,x),wt(c,args...);}
};
using namespace IO;
using namespace std;
const int P=1e9+7;
const int N=207;
int f[N][N];
int n,m;
int opt[N];
int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	rd(n);
	for(int i=1;i<=n;i++){
		char s=getchar();
		while(s!='U'&&s!='D'&&s!='-') s=getchar();
		if(s!='-') opt[++m]=s=='U';
	}
	n=m;
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			if(opt[i]) f[i][j]=((j-1>=0?f[i-1][j-1]:0)+1ll*f[i-1][j]*j)%P;
			else f[i][j]=(1ll*f[i-1][j]*j%P+1ll*f[i-1][j+1]*(j+1)%P*(j+1)%P)%P;
		}
	}
	wt('\n',f[n][0]);
	return 0;
}

我是真的菜，这个题做了一晚上/kk

注意要输出行末换行

Aizu 2333 My friends are small

我的朋友很小/yiw，日文翻译是我的朋友很少

傻逼题

将 $W$ 从大到小排序，最后一个没选的就是最小的

数据范围很小，直接记进状态里面就好了

记得滚动数组

$code$

#include<cstdio>
#include<iostream>
#include<algorithm>
namespace IO{
	template<typename T> inline void rd(T &x){
		x=0;bool f=0;char c=0;
		while(c<'0'||c>'9') f|=c=='-',c=getchar();
		while('0'<=c&&c<='9') x=x*10+(c^48),c=getchar();
		x=f?-x:x;
	}
	template<typename T,typename ...Args> inline void rd(T &x,Args &...args){rd(x),rd(args...);}
	template<typename T> inline void wt(char c,T x){
		int stk[114],top=0;
		if(x<0) x=-x,putchar('-');
		do stk[++top]=x%10,x/=10; while(x);
		while(top) putchar(stk[top--]+'0');
		putchar(c);
	}
	template<typename T,typename ...Args> inline void wt(char c,T &x,Args &...args){wt(c,x),wt(c,args...);}
};
using namespace IO;
using namespace std;
const int INF = 1e9;
const int P = 1e9 + 7;
const int N=207,M=1e4+7;
int f[2][M][N];
int n,m;
int w[N];
inline int cmp(int x,int y){return x>y;}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
	#endif
	rd(n,m);
	for(int i=1;i<=n;i++) rd(w[i]);
	sort(w+1,w+1+n,cmp);
	w[0]=INF;
	f[0][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=0;k<=i;k++)f[i&1][j][k]=0;
		}
		for(int j=0;j<=m;j++){
			for(int k=0;k<=i;k++){
				if(j>=w[i]) f[i&1][j][k]=(f[i&1][j][k]+f[(i-1)&1][j-w[i]][k])%P;
				f[i&1][j][i]=(f[i&1][j][i]+f[(i-1)&1][j][k])%P;
			}
		}
	}
	int res=0;
	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++) res=(res+f[n&1][i][j]*(w[j]>m-i))%P;
	}
	wt('\n',res);
	return 0;
}

AGC013D Piling Up

挺典的

P4778 Counting swaps

不会的套路题/kk

ABC214G/S2OJ1504

又是我不会的/hanx

做了一天/ng

直接做显然是不行的，所以考虑转化题意，对于 $\forall i$ ，连边 $(A_i,B_i)$ ，现在题意就变成给边染色了，这样统计的就是不合法的，考虑容斥，一个很 $\text{naive}$ 的容斥是 总数-不合法，发现你根本做不了，所以很容易想到加强限制，让答案等于 $\sum\limits_{i=0}^n (-1)^i\times f(i)$ ，其中 $f(i)$ 表示钦定有 $i$ 个位置不满足 $C_i!=A_i,C_i!=B_i$ 的方案数，即断掉 $i$ 条边，考虑怎么求这个东西

考虑一个环怎么做

假设不是环而是一条链，容易想到设 $f_{i,j,0/1}$ 表示现在到了第 $i$ 个点，断掉 $j$ 条边，钦定第 $i$ 条边颜色为 $A_i/B_i$ ，转移就是：

$f_{i,j,0}=\sum\limits_{k=1}^{i-2}f_{k,j-1,1}+\sum\limits_{k=1}^{i-1}f_{k,j-1,0}$

$f_{i,j,1}=\sum\limits_{k=1}^{i-1}f_{k,j-1,1}+\sum\limits_{k=1}^{i-1}f_{k,j-1,0}$

这个可以前缀和优化成 $O(n^2)$ 的

但是这个 $dp$ 是不适用于环的，因为我环上的第一个点会影响到最后一个点，所以要分类讨论强制断环成链

当我第一条边染的色是 $A_i$ 时：

初始化：$f_{1,1,0}=1$

对答案贡献：$\sum\limits_{i=1}^{n}f_{i,j,0}+\sum\limits_{i=1}^{n-1}f_{i,j,1}$

当我第一条边染的色是 $B_i$ 时：

初始化：$f_{1,1,1}=1$

对答案贡献：$\sum\limits_{i=1}^{n}f_{i,j,0}+\sum\limits_{i=1}^{n}f_{i,j,1}$

当我第一条边断掉时：

初始化：$\forall i ,\ f_{i,1,0}=f_{i,1,1}=[i!=1]$

对答案贡献：$\sum\limits_{i=1}^{n}f_{i,j,0}+\sum\limits_{i=1}^{n}f_{i,j,1}$

这三个方程中间的转移发现和上面的链的方程的转移是一样的

然后最后写一个背包合并把所有的环合并起来就好了/hanx

因为背包合并的复杂度是 两背包大小和乘上小的那个背包大小，所以时间复杂度是正确的/hanx

code

libreoj #3144. 「APIO2019」奇怪装置

挺奇怪的一道题，不会 :(

发现 $x,y$ 都是有循环节的，$y$ 的循环节显然是 $B$ ，现在我们只要知道 $x,y$ 拼在一起的循环节就好做了

首先循环节肯定是 $B$ 的倍数

所以我先猜了一手循环节时$\operatorname{lcm}(x,y)$ 但是是错的/ng

所以只能好好推导了/hanx

设当前时间为 $t$，循环节长度为 $kB$

由题可知：

$t+\lfloor \frac{t}{B} \rfloor \equiv t+kB+\lfloor \frac{t+kB}{B} \rfloor (\bmod A)$

$t+\lfloor \frac{t}{B} \rfloor \equiv t+kB+k+\lfloor \frac{t}{B} \rfloor (\bmod A)$

$k(B+1) \equiv 0 (\bmod A)$

所以当 $k=\frac{A}{\gcd(A,B+1)}$ 时，$k$ 有最小值，所以循环节 $len=\frac{AB}{\gcd(A,B+1)}$

后面就很好做了

若区间长度大于循环节，答案就是循环节，否则分类讨论一下

如果 $l_i \bmod len \le r_i \bmod len$ 直接将这个区间插进去

否则拆成两个区间 $[0,r_i \bmod len], [l_i \bmod len, len-1]$

做一下区间并就好了

code