J题: Melborp Elcissalc

原题链接:https://ac.nowcoder.com/acm/contest/33192/J

题目大意

已知 $k(1\le k\le 64)$ ，对于每个仅包含 $[0,k-1]$ 区间内的整数的数组，定义其优美度为非空子段之和为 $k$ 的倍数的数量。

求有多少长度为 $n(1\le n\le 64)$ 的数组，其优美度为 $t(0\le t\le \frac{n(n+1)}{2})$ ，答案对 $998244353$ 取模。

题解

先考虑，如何快速求一个数组 $a_1,a_2,...,a_n$ 的优美度。
求区间和通常的技巧是前缀和，设 $pr{e}_0=0,pr{e}_i=pr{e}_{i-1}+a_i$ ，有前缀和数组 $pr{e}_0,pr{e}_1,...pr{e}_n$ 。
对于一段区间 $[l,r]$ ，其区间和为 $pr{e}_r-pr{e}_{l-1}$ ，若 $pr{e}_r-pr{e}_{l-1}\equiv 0(modk)$ ，则 $[l,r]$ 提供优美度。
不妨将 $pr{e}_i$ 对 $k$ 取模，此时若 $pr{e}_{l-1}=pr{e}_r$ ，则 $[l,r]$ 提供优美度。
设 $cn{t}_i$ 表示 $pr{e}_j=i$ 的数量，可得此时数组 $a$ 的优美度为:
$$\sum _{i=0}^{k-1}{C}_{cn{t}_i}^2$$

(模 $k$ 意义下)由前缀和数组差分可得到原数组，即前缀和数组与原数组一一对应，不妨对前缀和数组进行计数。

我们可以分别考虑每个 $i$ 对应的 $cn{t}_i$ 对优美度的贡献，然后用动态规划进行计数。
设 $f_{x,y,z}$ 表示已经考虑了 $i\in [0,x]$ ，且 $\sum _{i=0}^{x}cn{t}_i=y$ (已有 $y$ 个数字)， $\sum _{i=0}^x{C}_{cn{t}_i}^2=z$ (当前优美度为 $z$ )的数组个数(此时不考虑剩下 $n-y$ 个没有数字的空位)
枚举 $cn{t}_x$ 的值，可得转移式如下(其中 $C_{n-(y-i)}^i$ 表示在除去原先的 $y-i$ 已有数字的位置后，在剩下 $n-(y-i)$ 个位置中插入 $i$ 个 $x$ 的方案数):
$$f_{x,y,z}=\sum _{i=0}^y{f}_{x-1,y-i,z-C_i^2}\ast C_{n-(y-i)}^i$$

初始化时注意，有 $y$ 个 $0$ 时的优美度为 $C_{y+1}^2$ ，因为前缀和有 $pr{e}_0=0$ 。
注意到其中 $x$ 维度在转移时只需上一维度，且 $y,z$ 维度都从较小处转移过来，可以用类似背包的倒序枚举的技巧优化掉 $x$ 维度。

本题时限较紧，注意常数优化。

参考代码

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

const int MAXN=70,P=998244353;
int n,k,t;
int C[MAXN][MAXN];
int f[MAXN][MAXN*MAXN];

inline void add(int&a,int b){//快速取模加法
	a+=b;
	if(a>=P)a-=P;
}

void init(){//组合数打表
	C[0][0]=1;
	for(int i=1;i<MAXN;++i){
		C[i][0]=1;
		for(int j=1;j<=i;++j){
			C[i][j]=C[i-1][j-1];
			add(C[i][j],C[i-1][j]);
		}
	}
}

int main()
{
	read(n),read(k),read(t);
	init();
	for(int y=0;y<=n;++y){
		f[y][C[y+1][2]]=C[n][y];//初始化
	}
	for(int x=1;x<k;++x){
		for(int y=n;y>=0;--y){//倒序枚举
			for(int z=t;z>=0;--z){//倒序枚举
				for(int i=1;i<=n;++i){//枚举数字x的数量
					if(y-i>=0&&z-C[i][2]>=0)add(f[y][z],1ll*f[y-i][z-C[i][2]]*C[n-(y-i)][i]%P);
					else break;//小剪枝
				}
			}
		}
	}
	cout<<f[n][t]<<'\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52