题解 CF1096G 【Lucky Tickets】
NaCly_Fish
·
·
题解
注：下文中的 k 都表示可用的数中最大值。
看了一下提交记录，似乎都写的 \Theta(nk \log nk) 的做法，，
来写一发不用 fft 的 \Theta(nk^2) 做法，此题中 k 较小，因此跑的飞快。
题目中要求两边相等的方案数，而两边之间互不影响；所以只用算出一边的和分别为 0,1,2,\dots 的方案数，平方和即是答案。
设 S 为可用的数集合，则每个格子填数方案的生成函数为
f(x)=\sum_{t\in S}x^t
显然 f(x)^{n/2} 就是答案的生成函数。
（不过相信很多同学都会，可以不看）
$$g(x)=f(x)^t$$
$$g'(x)f(x)=tf'(x)g(x)$$
提取一下系数就能发现，计算一项的复杂度只和 $f(x)$ 有关，暴力按式子算就是 $\Theta(k)$ 的，总时间复杂度就是 $\Theta(nk^2)$。
这个方法常数小，还好写，~~不知高到哪里去了~~。
```cpp
#pragma GCC optimize (2)
#pragma GCC optimize ("unroll-loops")
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 1000003
#define p 998244353
#define ll long long
#define reg register
using namespace std;
int n,k;
int f[N],g[N],inv[N];
ll ans = 1;
int main(){
int x,siz = 0,t = 0;
scanf("%d%d",&n,&k);
if(k==1){
putchar('1');
return 0;
}
n >>= 1;
for(reg int i=1;i<=k;++i){
scanf("%d",&x);
f[x] = 1,t = max(t,x);
}
for(reg int i=0;i<=t&&f[i]==0;++i) siz = max(siz,i+1);
if(siz>0){
for(reg int i=0;i<=t;++i) f[i] = f[i+siz];
t -= siz;
}
inv[1] = g[0] = 1;
int tt = t*n;
for(reg int i=2;i<=tt;++i) inv[i] = (ll)(p-p/i)*inv[p%i]%p;
for(reg int i=0;i!=tt;++i){
int tmp = 0;
for(reg int j=0;j<=min(i,t-1);++j) tmp = (tmp+(ll)(j+1)*f[j+1]%p*g[i-j])%p;
tmp = (ll)tmp*n%p;
for(reg int j=max(0,i-t);j!=i;++j) tmp = (tmp-(ll)(j+1)*g[j+1]*f[i-j])%p;
g[i+1] = (ll)tmp*inv[i+1]%p;
ans += (ll)g[i+1]*g[i+1]%p;
}
printf("%lld",ans%p);
return 0;
}
```