关键词：
我们需要知道这样一个东西(大概叫 斯特林公式？)
$S(i,j)=frac1j!sumlimits_k=0^j(-1)^k C_j^k(j-k)^i$
那么就是推啊
$=sumlimits_i=0^nsumlimits_j=0^iS(i,j)*2^j*j!$
然后问题来了，因为后面还有$2^j$和$j!$，我们发现这里展开斯特林数也没用，所以我们要把它们甩出去
因为$j>i$时$S(i,j)==0$，所以让后面求和到$n$，然后前提$2^j$和$j!$
$=sumlimits_i=0^nsumlimits_j=0^nS(i,j)*2^j*j!$
$=sumlimits_j=0^n2^j*j!sumlimits_i=0^nS(i,j)$
展开斯特林数
$=sumlimits_j=0^n2^j*j!sumlimits_i=0^nfrac1j!sumlimits_k=0^j(-1)^k C_j^k(j-k)^i$
一般我们会把$C(j,k)$拆开来消掉前面的$fracij!$
$=sumlimits_j=0^n2^j*j!sumlimits_i=0^nfrac1j!sumlimits_k=0^j(-1)^kfracj!k!(j-k)!(j-k)^i$
$=sumlimits_j=0^n2^j*j!sumlimits_i=0^nsumlimits_k=0^j(-1)^kfrac1k!(j-k)!(j-k)^i$
那后面这个东西明显的分成了两部分：和$k$有关的和和$j-k$有关的
$=sumlimits_j=0^n2^j*j!sumlimits_i=0^nsumlimits_k=0^jfrac(-1)^kk!frac(j-k)^i(j-k)!$
使用高中老师教给我们的等比数列求和公式
$=sumlimits_j=0^n2^j*j!sumlimits_i=0^nsumlimits_k=0^jfrac(-1)^kk!frac(j-k)^i+1-1(j-k-1)(j-k)!$
这样和是一定的，所以用NTT卷出来后面的然后前面的$O(n)$求和就可以了
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=100005,mod=998244353; 6 int a[4*N],b[4*N],rev[4*N],fac[N],inv[N]; 7 int n,ni,G,Gi,pw,ans; 8 void exGCD(int a,int b,int &x,int &y) 9 10 if(!b) x=1,y=0; return; 11 exGCD(b,a%b,y,x),y-=a/b*x; 12 13 int Qpow(int x,int k) 14 15 if(!k) return 1; 16 if(k==1) return x; 17 int tmp=Qpow(x,k/2); 18 return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 19 20 int Inv(int x) 21 22 int xx,yy; 23 exGCD(x,mod,xx,yy); 24 return (xx%mod+mod)%mod; 25 26 void NTT(int *arr,int len,int typ) 27 28 for(int i=0;i<=len;i++) 29 if(rev[i]>i) swap(arr[rev[i]],arr[i]); 30 for(int i=2;i<=len;i<<=1) 31 32 int lth=i>>1,ort=Qpow(~typ?G:Gi,(mod-1)/i); 33 for(int j=0;j<len;j+=i) 34 35 int ori=1,tmp; 36 for(int k=j;k<j+lth;k++,ori=1ll*ori*ort%mod) 37 38 tmp=1ll*ori*arr[k+lth]%mod; 39 arr[k+lth]=(arr[k]-tmp+mod)%mod; 40 arr[k]=(arr[k]+tmp)%mod; 41 42 43 44 if(typ==-1) 45 46 int ni=Inv(len); 47 for(int i=0;i<=len;i++) 48 arr[i]=1ll*arr[i]*ni%mod; 49 50 51 void Init() 52 53 scanf("%d",&n); 54 G=3,Gi=Inv(G),fac[0]=inv[0]=pw=1; 55 for(int i=1;i<=n;i++) 56 fac[i]=1ll*fac[i-1]*i%mod; 57 inv[n]=Inv(fac[n]); 58 for(int i=n-1;i;i--) 59 inv[i]=1ll*inv[i+1]*(i+1)%mod; 60 for(int i=0;i<=n;i++) 61 a[i]=(i%2)?mod-inv[i]:inv[i]; b[0]=1,b[1]=n+1; 62 for(int i=2;i<=n;i++) 63 b[i]=1ll*(Qpow(i,n+1)-1)*Inv(i-1)%mod*inv[i]%mod; 64 65 void Prework() 66 67 int len=1; while(len<=2*n+2) len<<=1; 68 for(int i=1;i<=len;i++) 69 rev[i]=(rev[i>>1]>>1)+(i&1)*(len>>1); 70 NTT(a,len,1),NTT(b,len,1); 71 for(int i=0;i<=len;i++) a[i]=1ll*a[i]*b[i]%mod; 72 NTT(a,len,-1); 73 74 int main() 75 76 Init(),Prework(); 77 for(int i=0;i<=n;i++,pw=pw*2%mod) 78 ans+=1ll*pw*fac[i]%mod*a[i]%mod,ans%=mod; 79 printf("%d",ans); 80 return 0; 81
tjoi/heoi2016求和(代码片段)
题面题目分析[eginsplitsum_i=0^nsum_j=0^iS(i,j)cdot2^jcdotj!&=sum_j=0^n2^jcdotj!sum_i=0^nS(i,j)&=sum_j=0^n2^jcdotj!sum_i=0^nsum_k=0^jfrac(-1)^kk!cdotfrac(j-k)^i 查看详情
bzoj4555[tjoi2016&heoi2016]求和ntt第二类斯特林数等比数列求和优化(代码片段)
[Tjoi2016&Heoi2016]求和TimeLimit: 40Sec MemoryLimit: 128MBSubmit: 679 Solved: 534[Submit][Status][Discuss]Description在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。现在他想计算这样一个 查看详情
[bzoj4555][tjoi2016&heoi2016]求和(代码片段)
Description在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。现在他想计算这样一个函数的值:[f(n)=sum_i=0^nsum_j=0^iS(i,j)*2^j*(j!)]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... 查看详情
bzoj4555:[tjoi2016&heoi2016]求和(代码片段)
$n<=100000$求$\sum_i=0^n\sum_j=0^is(i,j)*2^j*(j!)$，其中$S(i,j)$表示第二类斯特林数。方法一：多项式求逆。不会。方法二：$S(i,j)=\frac1j!\sum_k=0^j(-1)^kC_j^k(j-k)^i$，代入得（这里由于j>i是S(i,j)=0因此j可以枚举到n）$\sum_i=0^n 查看详情
bzoj4555:[tjoi2016&heoi2016]求和排列组合+多项式求逆或斯特林数+ntt(代码片段)
【题意】给定n，求Σi=0~nΣj=1~is(i,j)*2^j*j!，n<=10^5。【算法】生成函数+排列组合+多项式求逆【题解】参考： [BZOJ4555][Tjoi2016&Heoi2016]求和-NTT-多项式求逆$ans=\sum_i=0^n\sum_j=0^is(i,j)*2^j*j!$令$g(n)=\sum_j=0^ns(n,j)*2^ 查看详情
[heoi2016/tjoi2016]求和(代码片段)
NTT卷积#include<cstdio>#include<algorithm>#include<iostream>constintmod=998244353,g=3;constintmaxn=400100;typedeflonglongll;inlineintpow(inta,intb,intans=1)for(;b;b>>=1,a=ll(a)*a%mod)if(b&1)ans=ll(ans)*a%mod;returnans;inlineintinv(inta)returnpow(a,mod-2);inlinevoidreduc... 查看详情
bzoj4555[tjoi2016&heoi2016]求和ntt+第二类斯特林数(代码片段)
...成一个n项的等比数列,这样我们可以把成等比数列的一边求和 查看详情
[heoi2016/tjoi2016]排序解题报告(代码片段)
[HEOI2016/TJOI2016]排序题意给出一个大小为(n)的排列,对这个排列进行(m)次操作,操作分为以下两种,0lr表示将区间([l,r])的数升序排序.1lr表示将区间([l,r])的数降序排序.询问(m)次操作后下标为(q)的数字.思路不看题解打死也想不出来系列... 查看详情
bzoj4555[tjoi2016&heoi2016]求和第二类斯特林数+ntt(代码片段)
题目在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)你能帮帮他吗?... 查看详情
[heoi2016/tjoi2016]求和——第二类斯特林数(代码片段)
给你斯特林数就换成通项公式，给你k次方就换成斯特林数考虑换成通项公式之后，组合数没有什么好的处理方法直接拆开，消一消阶乘然后就发现了(j-k)和k！往NTT方向靠拢然后大功告成 其实只要想到把斯特林公式换成通项... 查看详情
[heoi2016/tjoi2016]求和(代码片段)
XV.[HEOI2016/TJOI2016]求和题意：求一个东西(LARGEsumlimits_i=0^nsumlimits_j=0^iS_i^j*2^j*j!)其中(S_i^j)为第二类斯特林数，递推公式为(S_n^m=S_n-1^m-1+m*S_n-1^m)。我们终于可以像莫反一样，开始喜闻乐见地推式子辣！首先，就让我这个半小时前还在... 查看详情
heoi2016解题报告(代码片段)
树在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：1.标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结... 查看详情
tjojiheoi2016求和(代码片段)
【TJOI/HEOI2016】求和这题好难啊！！斯特林数+NTT。首先我们将第二类斯特林数用容斥展开，具体原理不解释了。(displaystyleS(i,j)=frac1j!sum_k=0^j(-1)^kC_j^k(j-k)^i=sum_k=0^jfrac(-1)^kk!cdotfrac(j-k)^i(j-k)!)。我们交换一下(s 查看详情
[heoi2016/tjoi2016]求和(代码片段)
嘟嘟嘟好多人（神仙）都说这是NTT例题，然后我就做了……做这题，需要一下前置技能：1.第二类斯特林数2.NTT3.没有公式恐惧症额……不会斯特林数的话（就像我），知道通项公式也行。这个博客挺好：第二类斯特林数总结然后... 查看详情
[bzoj4555][tjoi2016&heoi2016]求和(分治fft)
解法一：容易得到递推式，可以用CDQ分治+FFT代码用时:1h比较顺利，没有低级错误。实现比较简单，11348ms#include<cstdio>#include<algorithm>#definerep(i,l,r)for(inti=l;i<=r;i++)typedeflonglongll;usingnamespacestd;constintN=(1<< 查看详情
[heoi2016]求和sum
[HEOI2016]求和sumDescription求[sum_{i=0}^nsum_{j=0}^iS(i,j)×2^j×(j!)]其中S(i,j)代表第二类斯特林数。Solution解法一记Bell数(B(n)=sum_{i=0}^nS(n,i))根据第二类斯特林数的组合意义,(B(i))代表把n个球放进任意个相同的盒子的方案数。那么有[B(n)=sum_{i=0... 查看详情
p4091[heoi2016/tjoi2016]求和(代码片段)
留待警戒FFT的时候长度要写的和函数里一样啊XD瞎扯这是个第二类斯特林数的理性愉悦颓柿子题目颓柿子真的是让我hi到不行啦（才没有）前置芝士一个公式[sum_i=0^nt^i=fract^n+1-1t-1]第二类斯特林数第二类斯特林数的是指把n个对象... 查看详情
[heoi2016/tjoi2016]求和
Discription在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)你能帮帮他... 查看详情