題目鏈接

(lugou) https://www.luogu.org/problem/P4091
(bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=4555

題解

終于不是神仙題了啊。。。
首先\(O(n\log n)\)的FFT做法非常明顯，直接用容斥展開，這里不再贅述了。發(fā)現最后就是要求一個\(\sum^{n}_{k=0}\sum^{n}_{j=k}(-1)^{j-k}{j\choose k}2^j(\sum^{n}_{i=0}k^i)\).
注意容斥的公式在上指標小于下指標時依然成立，此時其給出的值恒為\(0\).

然后去膜了一波大佬的線性做法:
依然是要求那個式子，但是那個式子可以不用卷積算。
我們發(fā)現，假設某序列\(A\)的生成函數為\(A(x)=\sum^{n}_{i=0}a_ix^i\), 那么\(\sum^{n}_{j=0}\sum^n_{i=j}a_i{i\choose j}q^{i-j}x^j=\sum^{n}_{j=0}a_j(x+q)^j=A(x+q)\).
所以要求的就相當于令\(A_i=2^i,q=-1\), 那么\(A(x)=\frac{(2x)^{n+1}}{2x-1}, A(x-1)=\frac{(2x-2)^{n+1}}{2x-3}\), 這個東西直接把上面的二項式展開然后除以一次式\(O(n)\)解決。
這樣求出了多項式的每一項，再和\(\sum^{n}_{i=0}k^i\)乘起來求和即可。
對于快速冪，可以用線性篩先求出所有質數的\((n+1)\)次冪，然后按積性函數乘起來，假設質數密度是\(O(\frac{1}{\log n})\)那么復雜度就是\(O(\frac{n}{\log n}\times \log n)=O(n)\).

現在思考一個問題: 這個做法先把二項式展開之后的組合數合了起來，又把合起來之后的式子二項式展開了，那么實際上應該相當于啥也沒干，憑什么就優(yōu)化復雜度了呢？
其實是因為，原來的二項式合并有\(n\)項(做了\(n\)次合并)，合并完了之后它變成了一個非常好看的等比數列求和的形式，那么可以直接表示成\((n+1)\)次減\(1\)除以\(1\)次\(-1\), 那么再做二項式展開就只要做一次了，于是復雜度成功降了下來！
真神奇。

代碼

由于我懶得寫線性篩所以用了快速冪復雜度依然是\(O(n\log n)\).
但是線性做法的思想還是非常值得借鑒的。

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #define llong long long using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 1e5+1; const int P = 998244353; const llong INV2 = 499122177; llong fact[N+3],finv[N+3]; int n;llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; } llong mulinv(llong x) {return quickpow(x,P-2);} llong comb(llong x,llong y) {return x<0||y<0||x<y ? 0ll : fact[x]*finv[y]%P*finv[x-y]%P;}llong a[N+3]; llong aa[N+3]; llong b[N+3];int main() {fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;scanf("%d",&n);for(int i=0; i<=n+1; i++){a[i] = quickpow(2ll,n+1)*comb(n+1,i);if((n+1-i)&1) {a[i] = P-a[i];}}a[0]--;for(int i=n; i>=0; i--){aa[i] = a[i+1]*INV2%P;a[i] = (a[i]+3ll*aa[i])%P;}b[0] = 1ll; b[1] = n+1;for(int i=2; i<=n; i++){b[i] = (quickpow(i,n+1)-1)*mulinv(i-1)%P;}llong ans = 0ll;for(int i=0; i<=n; i++) {ans = (ans+aa[i]*b[i])%P;}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 4555 Luogu P4091 [HEOI2016/TJOI2016]求和 (第二类斯特林数)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。