NTT)"/>
bzoj4555 [Tjoi2016Heoi2016]求和(NTT)
Description
在2016年,佳媛姐姐刚刚学习了第二类斯特林数,非常开心。
现在他想计算这样一个函数的值:
S(i, j)表示第二类斯特林数,递推公式为:
S(i, j) = j ∗ S(i − 1, j) + S(i − 1, j − 1), 1 <= j <= i − 1。
边界条件为:S(i, i) = 1(0 <= i), S(i, 0) = 0(1 <= i)
你能帮帮他吗?
Input
输入只有一个正整数
Output
输出f(n)。由于结果会很大,输出f(n)对998244353(7 × 17 × 223 + 1)取模的结果即可。1 ≤ n ≤ 100000
Sample Input
3
Sample Output
87
分析:
这比那道序列计数友善多了
一看到这条限制,
998244353,yg=3
NTT啊
确实,那我们现在的任务就是找卷积
但是这个第二类斯特林数好烦人啊
ta到底是什么呢
第二类斯特林数S(n,m)定义为把n个元素划分成m个无序集合的方案数
根据这个定义我们不难写出递推式
设状态S(i,j),讨论第i个元素是否单独一个集合
若单独一个集合,则方案数等价于S(i-1,j-1)
若不是单独一个集合,则他可以在之前任意j个集合里,方案为S(i-1,j)*j
这样我们得到式子S(i,j)=S(i-1,j-1)+S(i-1,j)*j
递推的时间复杂度是O(n^2)的
其实关键是知道斯特林数的通项公式
把通项公式带入化简一下
经过一系列的移项约分
我天,有除法,
需要线性求逆元
看来我们需要复习一下数论知识了
那我们就现在就需要在柿子(式子)上开刀了
tip
熟练运用不同的数学知识
一道题可能主体算法是NTT,
但是实际上在维护小东西的时候可能需要其他的姿势
板子打不对,
其他都jj, (╯‵□′)╯︵┻━┻
循环的时候注意,
只要循环的是数组下标,
一定要从0开始
——从0开始的~~异世界生活~~NTT循环
这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long longusing namespace std;const ll mod=998244353;
const int N=400005;
ll mi[N],jc[N],inv[N],f[N],g[N];
int n,fn;ll KSM(ll a,ll b,ll p)
{ll t=1;a=(a+mod)%mod; //while (b){if (b&1) t=(t*a)%p;b>>=1;a=(a*a)%p;}return t%p;
}void NTT(ll *a,int n,int opt)
{int i,j=0,k;for (i=0;i<n;i++){if (i>j) swap(a[i],a[j]);for (int l=n>>1;(j^=l)<l;l>>=1);}for (i=1;i<n;i<<=1) ///{ll wn=KSM(3,(mod-1)/(i<<1),mod); //(mod-1)/(i<<1)int m=i<<1;for (j=0;j<n;j+=m){ll w=1;for (k=0;k<i;k++,w=(w*wn)%mod){ll z=(a[j+k+i]*w)%mod;a[j+i+k]=(a[j+k]-z+mod)%mod;a[j+k]=(a[j+k]+z)%mod;}}}if (opt==-1) reverse(a+1,a+n); //
}int main()
{scanf("%d",&n);inv[0]=inv[1]=1;jc[0]=1; mi[0]=1;for (int i=1;i<=n;i++) mi[i]=(mi[i-1]*2)%mod; //2的若干次幂 for (int i=1;i<=n;i++) jc[i]=(jc[i-1]*i)%mod;for (int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;for (int i=1;i<=n;i++) inv[i]=(inv[i-1]*inv[i])%mod; //阶乘逆元 for (int i=0;i<=n;i++)if (i&1) f[i]=-inv[i]; //(-1)^k/k!else f[i]=inv[i];g[0]=1; g[1]=n+1; for (int i=2;i<=n;i++) //sigma/(j-k)!{ll t=(KSM(i,n+1,mod)-1+mod)%mod; //等差数列公式 t=t*KSM(i-1,mod-2,mod)%mod; //(a^(n+1)-1)/(n-1) g[i]=(t*inv[i])%mod;}fn=1;while (fn<=n*2+1) fn<<=1;NTT(f,fn,1); NTT(g,fn,1);for (int i=0;i<=fn;i++) f[i]=(f[i]*g[i])%mod;NTT(f,fn,-1); //IDNTll t=KSM(fn,mod-2,mod);for (int i=0;i<=fn;i++) f[i]=(f[i]*t)%mod; //IDNT不要忘了/nll ans=0;for (int i=0;i<=n;i++) ans=(ans+f[i]*jc[i]%mod*mi[i]%mod)%mod;printf("%lld",ans); return 0;
}
更多推荐
bzoj4555 [Tjoi2016Heoi2016]求和(NTT)
发布评论