P4091 [HEOI2016/TJOI2016]求和
题目描述
在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。
现在他想计算这样一个函数的值:
\[f(n)=\sum_{i=0}^n\sum_{j=0}^i S(i,j)\times 2^j \times (j!)
\]
\]
\(S(i, j)\)表示第二类斯特林数，递推公式为:
\[S(i, j) = j \times S(i - 1, j) + S(i - 1, j - 1), 1 \le j \le i - 1
\]
\]
边界条件为：
\[S(i, i) = 1(0 \le i), S(i, 0) = 0(1 \le i)
\]
\]
你能帮帮他吗?
输入输出格式
输入格式：
输入只有一个正整数
输出格式：
输出\(f(n)\)。由于结果会很大，输出\(f(n)\)对\(998244353(7 × 17 × 2^{23} + 1)\)取模的结果即可。
说明
对于\(50\%\)数据\(1 ≤ n ≤5000\)
对于\(100\%\)数据\(1 ≤ n ≤ 100000\)
迷迷糊糊的乱推...
\[\begin{aligned}
&\sum_{i=0}^n\sum_{i=0}^i{i\brace j}2^jj!\\
=&\sum_{i=0}^n\sum_{i=0}^n{i\brace j}2^jj!\\
=&\sum_{j=0}^n2^jj!\sum_{i=0}^n{i\brace j}\\
=&\sum_{j=0}^n2^jj!\sum_{i=0}^n\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{(j-k)^i}{(j-k)!}\\
=&\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}\sum_{i=0}^n\frac{(j-k)^i}{(j-k)!}
\end{aligned}
\]
&\sum_{i=0}^n\sum_{i=0}^i{i\brace j}2^jj!\\
=&\sum_{i=0}^n\sum_{i=0}^n{i\brace j}2^jj!\\
=&\sum_{j=0}^n2^jj!\sum_{i=0}^n{i\brace j}\\
=&\sum_{j=0}^n2^jj!\sum_{i=0}^n\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{(j-k)^i}{(j-k)!}\\
=&\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}\sum_{i=0}^n\frac{(j-k)^i}{(j-k)!}
\end{aligned}
\]
\[A_i=\frac{(-1)^i}{i!},B_i=\sum_{k=0}^n\frac{k^i}{k!}
\]
\]
然后卷一下子就行了。
注意一点，\(B_0=1\)，这个要代入原式的定义式得到。
Code:
#include <cstdio>
#include <algorithm>
const int N=(1<<18)+10;
const int mod=998244353,G=3,Gi=332748118;
#define mul(a,b) (1ll*(a)*(b)%mod)
#define add(a,b) ((a+b)%mod)
int n,A[N],B[N],len=1,L=-1,turn[N],ifac[N],fac[N];
int qp(int d,int k){int f=1;while(k){if(k&1)f=mul(f,d);d=mul(d,d),k>>=1;}return f;}
void NTT(int *a,int typ)
{
for(int i=1;i<len;i++) if(i<turn[i]) std::swap(a[i],a[turn[i]]);
for(int le=1;le<len;le<<=1)
{
int wn=qp(typ?G:Gi,(mod-1)/(le<<1));
for(int p=0;p<len;p+=le<<1)
{
int w=1;
for(int i=p;i<p+le;i++,w=mul(w,wn))
{
int tx=a[i],ty=mul(w,a[i+le]);
a[i]=add(tx,ty);
a[i+le]=add(tx,mod-ty);
}
}
}
if(!typ)
{
int inv=qp(len,mod-2);
for(int i=0;i<len;i++) a[i]=mul(a[i],inv);
}
}
int main()
{
scanf("%d",&n);
while(len<=n<<1) len<<=1,++L;
for(int i=0;i<len;i++) turn[i]=turn[i>>1]>>1|(i&1)<<L;
fac[0]=1;for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
ifac[n]=qp(fac[n],mod-2);
for(int i=n-1;~i;i--) ifac[i]=mul(ifac[i+1],i+1);
A[0]=1;
for(int i=1;i<=n;i++) A[i]=i&1?mod-ifac[i]:ifac[i];
B[0]=1,B[1]=n+1;
for(int i=2;i<=n;i++) B[i]=mul(qp(i,n+1)-1,mul(qp(i-1,mod-2),ifac[i]));
NTT(A,1),NTT(B,1);
for(int i=0;i<len;i++) A[i]=mul(A[i],B[i]);
NTT(A,0);int ans=0;
for(int i=0;i<=n;i++) ans=add(ans,mul(qp(2,i),mul(fac[i],A[i])));
printf("%d\n",ans);
return 0;
}
2018.12.23