求 $sumlimits_{i=0}^nsumlimits_{j=0}^n Stirling2(i,j) imes 2^j imes j!$
$n leq 100000$
sol：
小清新斯特林数多项式题
首先熟知斯特林数的卷积形式 $Stirling2(i,j) = sumlimits_{k=0}^j frac{(-1)^{(j-k)}}{(j-k)!} imes frac{k^i}{k!}$
这题就是先对 $i$ 求个前缀和，再乘以 $2^j imes j!$ 再求和
于是卷积后一项的 $k^i ightarrow sumlimits_{i=0}^n k^i$
这是一个等比数列求和的形式，注意特判一下 $k=1$ 形式即可
然后就是套路啦，令 $A(x) = frac{sumlimits_{i=0}^n{k^i}}{k!} x$，$B(x)=frac{(-1)^i}{i!}$，$C = A imes B$
则 $ans = sumlimits_{i=0}^n 2^i imes i! imes [x^i]C(x)$
注意 $A(x),B(x),C(x)$ 的常数项都是 $1$
#include <bits/stdc++.h> #define LL long long #define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i) #define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i) using namespace std; inline int read() { int x = 0,f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar())if(ch == '-') f = -f; for(; isdigit(ch); ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 400010, mod = 998244353; inline int inc(int x, int y) { x += y; if(x >= mod) x -= mod; return x; } inline int dec(int x, int y) { x -= y; if(x < 0) x += mod; return x; } inline int mul(int x, int y) { return 1LL * x * y % mod; } inline int ksm(int x, int t, int res = 1) { for(; t; x = mul(x, x), t = t >> 1) if(t & 1) res = mul(res, x); return res; } int n, a[maxn], b[maxn]; int r[maxn], lg[maxn], fac[maxn], ifac[maxn], pw[maxn]; void fft(int *a, int n, int f) { rep(i, 0, n-1) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lg[n] - 1)); rep(i, 0, n-1) if(i < r[i]) swap(a[i], a[r[i]]); for(register int i = 1; i < n; i <<= 1) { int wn = ksm(3, (mod - 1) / (i << 1)); if(f == -1) wn = ksm(wn, mod - 2); for(register int j = 0; j < n; j += (i << 1)) { int w = 1; for(register int k = 0; k < i; k++, w = mul(w, wn)) { int x = a[j + k], y = mul(w, a[j + k + i]); a[j + k] = inc(x, y); a[j + k + i] = dec(x, y); } } } if(f == -1) { int inv_n = ksm(n, mod - 2); rep(i, 0, n - 1) a[i] = mul(a[i], inv_n); } } inline int cal(int x) { if(x == 1) return n + 1; else return mul(dec(ksm(x, n+1), 1), ksm(dec(x, 1), mod - 2)); } int main() { lg[0] = -1; rep(i, 1, maxn - 1) lg[i] = lg[i >> 1] + 1; n = read(); int len = 1; for(; len <= (n<<1); len <<= 1); fac[0] = ifac[0] = ifac[1] = pw[0] = 1; rep(i, 1, n) fac[i] = mul(fac[i - 1], i); rep(i, 2, n) ifac[i] = mul((mod - mod / i), ifac[mod % i]); rep(i, 1, n) ifac[i] = mul(ifac[i], ifac[i - 1]); //cout << mul(ifac[3], fac[3]) << endl; rep(i, 1, n) pw[i] = inc(pw[i - 1], pw[i - 1]); a[0] = b[0] = 1; rep(i, 1, n) a[i] = mul(cal(i), ifac[i]); rep(i, 1, n) b[i] = (i & 1) ? (mod - ifac[i]) : ifac[i]; fft(a, len, 1); fft(b, len, 1); //for(int i=0;i<len;i++) cout << a[i] << " "; cout << endl; // for(int i=0;i<len;i++) cout << b[i] << " "; cout << endl; rep(i, 0, len - 1) a[i] = mul(a[i], b[i]); // for(int i=0;i<len;i++) cout << a[i] << " "; cout << endl; fft(a, len, -1); int ans = 0; //for(int i=1;i<=n;i++) cout << a[i] << " "; cout << endl; rep(i, 1, n) ans = inc(ans, mul(pw[i], mul(fac[i], a[i]))); cout << inc(ans, 1) << endl; }
还有一个小清新多项式求逆的做法
令 $f(n) = sumlimits_{i=0}^n Stirling2(n,i) imes i! imes 2^i$，这个东西的组合意义为把 $n$ 个不同的物品放入若干个不同的集合中，且每个集合有两种不同的状态的方案数
枚举最后一个集合的大小和状态，得到 $f(n) = sumlimits_{i=1}^n 2 imes inom{n}{i} imes f(n-i)$
多项式求逆即可（远古代码
#include<bits/stdc++.h> #define LL long long using namespace std; const int maxn = 500010,P = 998244353,G = 3; int n,L,num,R[maxn],a[maxn],b[maxn],c[maxn],d[maxn]; int m; int INV[maxn]; inline int ksm(int x,int t) { int res = 1; while(t) { if(t & 1) res = 1LL * res * x % P; x = 1LL * x * x % P; t >>= 1; } return res; } inline void NTT(int *a,int f,int n,int L) { for(int i=0;i<n;i++) R[i] = (R[i>>1] >> 1) | ((i & 1) << (L - 1)); for(int i=0;i<n;i++)if(i < R[i])swap(a[i],a[R[i]]); for(int i=1;i<n;i<<=1) { int wn = ksm(G,(P - 1) / (i << 1)); if(f == -1)wn = ksm(wn,P - 2); for(int j=0;j<n;j+=(i<<1)) { int w = 1; for(int k=0;k<i;k++,w=1LL * w * wn % P) { int x = a[j + k], y = 1LL * w * a[j + k + i ] % P; a[j + k] = ((x + y) % P + P) % P; a[j + k + i] = ((x - y) % P + P) % P; } } } if(f == -1) { int inv = ksm(n,P - 2); for(int i=0;i<n;i++)a[i] = 1LL * a[i] * inv % P; } } inline void inverse(int *a,int *b,int n,int L) { if(n == 1){b[0] = ksm(a[0],P - 2);return;} inverse(a,b,n>>1,L-1); memcpy(c,a,n*sizeof(int));memset(c+n,0,n*sizeof(int)); NTT(c,1,n<<1,L+1);NTT(b,1,n<<1,L+1); for(int i=0;i<(n<<1);i++) b[i] = 1LL * b[i] * ((2 - 1LL * c[i] * b[i] % P + P) % P) % P; NTT(b,-1,n<<1,L+1);memset(b+n,0,n*sizeof(int)); } int main() { scanf("%d",&n); for(INV[0] = INV[1] = a[0] = m=1;m<=n;m<<=1)L++; for (int i=2; i<=n; i++) INV[i]=P-(LL)INV[P%i]*(P/i)%P; for (int i=3; i<=n; i++) INV[i]=(LL)INV[i-1]*INV[i]%P; for (int i=1; i<=n; i++) a[i]=((P-INV[i])<<1)%P; inverse(a,b,m,L); int ans=b[n]; for (int i=n;i;i--) ans=((LL)ans*i+b[i-1])%P; printf("%d ",ans); return 0; }