CF 好题
个人记录
https://www.luogu.com.cn/problem/CF1096G
FFT 板子？如果 mod 1e9+7 呢？
题解给出了一个有意思的 trick。
我们重新整理问题。
给定F(x)=\sum_{i=0}^k a_i x^i,以及一个整数 b，输入整数 len。
求 F(x)^b的前len项，答案对1e9+7取模，k<=10,len<=2e6,b<=1e18
设 $G(x)=F(x)^b$
$G’(x)=(F(x)^b)'$。
$G’(x)=bF(x)^{b-1}F’(x)$。
$G’(x)F(x)=bF(x)^bF’(x)$。
$G’(x)F(x)=bG(x)F’(x)$。
我们设 $C(x)=bG(x)F’(x)$。
我们考虑从小到大求 $G(x)$ 系数。
首先初始化。
然后使用 $bG(x)F’(x)$ 对 $C(x)$ 进行答案贡献。
当我们计算某个系数 $x^i$ 的系数的时候，我们找到 $F(x)$ 最低的不是 $0$ 的位 $m$。
我们找到 $C(x)$ 的 $i+m-1$ 系数。
这个系数就差当前的贡献。
我们求出当前显然通过 $G’(x)F(x)$ 算。
我们先用这个减去前面的项。
然后发现能关于本系数列方程。
整理即可计算。
由于 $F(x)$ 很短，所以减去的数也很少。
#include<bits/stdc++.h>
#define int long long
const int mod=998244353;
using namespace std;
int n,k;
int b[29];
int ksm(int a,int b){
int ans;
ans=1;
while(b){
if(b&1){
ans*=a;
ans%=mod;
}
a*=a;
a%=mod;
b>>=1;
}
return ans;
}
int cc[2000009];
int a[2000009];
signed main(){
cin>>n>>k;
int mi;
mi=1e16;
n>>=1;
for(int i=1;i<=k;i++){
int x;
cin>>x;
b[x]++;
mi=min(mi,x);
}
int ans;
ans=0;
a[mi*n]=1;
ans+=1%mod;
ans%=mod;
for(int i=1;i<10;i++){
cc[mi*n+i-1]+=a[mi*n]*b[i]%mod*i%mod*n%mod;
}
for(int i=mi*n+1;i<=n*10;i++){
int x;
x=i+mi-1;
int z;
z=cc[x];
for(int j=1;j<=10&&i-j-1>=0;j++){
z-=a[i-j]*b[mi+j]%mod*(i-j)%mod;
z+=mod;
z%=mod;
}//z/(i-b[mi]*mi*n)=x...z+mi*n*x=ix
z*=ksm((i-b[mi]*mi*n%mod+mod)%mod,mod-2);
z%=mod;
a[i]=z;
for(int j=1;j<=10;j++){
cc[i+j-1]+=a[i]*b[j]*j%mod*n%mod;
cc[i+j-1]%=mod;
}
ans+=z*z%mod;
ans%=mod;
}
cout<<ans;
return 0;
}