題目鏈接：點擊查看

題目大意：初始時給出 $n$ 個點，分別為 $\{(0,a_0),(0,a_1),?,(0,a_n)\}$，每次可以向下走或向左走，問到達點 $\{(1,0),(2,0),?,(n,0)\}$ 且路徑不相交的方案數(shù)

題目分析：有向圖路徑不相交方案數(shù)問題，考慮 $LGV$ 定理，實質(zhì)上就是要求

假設(shè) $a_i$ 和 $b_j$ 用坐標(biāo)表示，那么不難看出 $$e(a_i,b_j)=\left(\genfrac{}{}{0ex}{}{(a_{i,x}?b_{j,x})+(a_{i,y}?b_{j,y})}{a_{i,x}?b_{j,x}}\right)$$

又因為本題中 $a_i=(0,a_i)$，$b_j=(j,0)$，所以$$e(a_i,b_j)=\left(\genfrac{}{}{0ex}{}{a_i+j}{j}\right)$$
根據(jù) $\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\frac{n!}{m!(n?m)!}$ 展開 $$e(a_i,b_j)=\frac{(a_i+j)!}{j!a_i!}$$

于是目標(biāo)行列式為

$$M=\left|\begin{array}{cccc}\frac{(a_1+1)!}{1!a_1!}& \frac{(a_1+2)!}{2!a_1!}& ?& \frac{(a_1+n)!}{n!a_1!}\\ \frac{(a_2+1)!}{1!a_2!}& \frac{(a_2+2)!}{2!a_2!}& ?& \frac{(a_2+n)!}{n!a_2!}\\ ?& ?& ?& ?\\ \frac{(a_n+1)!}{1!a_n!}& \frac{(a_n+2)!}{2!a_n!}& ?& \frac{(a_n+n)!}{n!a_n!}\end{array}\right|$$

每列提出 $\frac{1}{j!}$

$$M=\prod _{j=1}^n\frac{1}{j!}\left|\begin{array}{cccc}\frac{(a_1+1)!}{a_1!}& \frac{(a_1+2)!}{a_1!}& ?& \frac{(a_1+n)!}{a_1!}\\ \frac{(a_2+1)!}{a_2!}& \frac{(a_2+2)!}{a_2!}& ?& \frac{(a_2+n)!}{a_2!}\\ ?& ?& ?& ?\\ \frac{(a_n+1)!}{a_n!}& \frac{(a_n+2)!}{a_n!}& ?& \frac{(a_n+n)!}{a_n!}\end{array}\right|$$

化簡

$$M=\prod _{j=1}^n\frac{1}{j!}\left|\begin{array}{cccc}(a_1+1)& (a_1+1)(a_1+2)& ?& (a_1+1)(a_1+2)...(a_1+n)\\ (a_2+1)& (a_2+1)(a_2+2)& ?& (a_2+1)(a_2+2)...(a_2+n)\\ ?& ?& ?& ?\\ (a_n+1)& (a_n+1)(a_n+2)& ?& (a_n+1)(a_n+2)...(a_n+n)\end{array}\right|$$

根據(jù) $(x+1{)}^2=x^2+2x+1=(x+1)(x+2)+(x+1)$

以及 $(x+1{)}^3=x^3+3x^2+3x+1=(x+1)(x+2)(x+3)?3(x+1)(x+2)+(x+1)$

所以根據(jù)行列式的初等變換，是可以通過前面的列消去后面的列，使得行列式變成

$$M=\prod _{j=1}^n\frac{1}{j!}\left|\begin{array}{cccc}(a_1+1)& (a_1+1{)}^2& ?& (a_1+1{)}^n\\ (a_2+1)& (a_2+1{)}^2& ?& (a_2+1{)}^n\\ ?& ?& ?& ?\\ (a_n+1)& (a_n+1{)}^2& ?& (a_n+1{)}^n\end{array}\right|$$

不難看出每一行提出 $(x+1)$ 后，這就是一個 范德蒙德行列式

$$M=\prod _{j=1}^n\frac{1}{j!}\prod _{i=1}^n(a_i+1)\left|\begin{array}{cccc}1& (a_1+1)& ?& (a_1+1{)}^{n?1}\\ 1& (a_2+1)& ?& (a_2+1{)}^{n?1}\\ ?& ?& ?& ?\\ 1& (a_n+1)& ?& (a_n+1{)}^{n?1}\end{array}\right|$$

即

$$M=\prod _{j=1}^n\frac{1}{j!}\prod _{i=1}^n(a_i+1)\prod _{1\le i<j\le n}((a_j+1)?(a_i+1))$$

化到最簡

$$M=\prod _{j=1}^n\frac{1}{j!}\prod _{i=1}^n(a_i+1)\prod _{1\le i<j\le n}(a_j?a_i)$$

瓶頸在于如何快速求解 $\prod _{1\le i<j\le n}(a_j?a_i)$，參考之前的題目：2021HDU多校7 - 7054 不難發(fā)現(xiàn)可以將 $a_j?a_i$ 視為背包，求出 $c[k]$ 為 $a_j?a_i=k$ 的方案數(shù)，那么答案就是 $\prod k^{c[k]}$ 了，加個偏移量當(dāng)背包轉(zhuǎn)移就好啦

需要注意的是，因為本題保證了 $a_i$ 是互不相同的，所以 $c[k]$ 不會太大，不需要用 $MTT$ 降冪，用 $NTT$ 就足夠了

代碼：

// Problem: Cells // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11260/C // Memory Limit: 1048576 MB // Time Limit: 6000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=5e6+100,M=1e6,mod=998244353,G=3,Gi=(mod+1)/3; int limit,L,r[N]; int a[N],b[N]; int q_pow(int a,int b) {int ans=1;while(b) {if(b&1) ans=1LL*ans*a%mod;a=1LL*a*a%mod,b>>=1;}return ans; } int inv(int x) {return q_pow(x,mod-2); } void NTT(int *A,int type) {for(int i=0;i<limit;i++) if(i<r[i]) swap(A[i],A[r[i]]);for(int mid=1;mid<limit;mid<<=1) { int Wn=q_pow(type==1?G:Gi,(mod-1)/(mid<<1));for(int j=0;j<limit;j+=(mid<<1)) {int w=1;for(int k=0;k<mid;k++,w=1LL*w*Wn%mod) {int x=A[j+k],y=1LL*w*A[j+k+mid]%mod;A[j+k]=(x+y)%mod,A[j+k+mid]=(x-y+mod)%mod;}}}if(type==-1) {int inv=q_pow(limit,mod-2);for(int i=0;i<limit;i++) {A[i]=1LL*A[i]*inv%mod;}} } void init(int n,int m) {limit=1;L=0;while(limit<=n+m) limit<<=1,L++;for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(L-1)); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;read(n);LL ans=1,fac=1;for(int i=1,x;i<=n;i++) {read(x);fac=fac*i%mod;ans=ans*inv(fac)%mod;ans=ans*(x+1)%mod;a[x]=1;b[M-x]=1;}init(M+1,M+1);NTT(a,1),NTT(b,1);for(int i=0;i<limit;i++) {a[i]=1LL*a[i]*b[i]%mod;}NTT(a,-1);for(int i=M+1;i<=M+M;i++) {ans=ans*q_pow(i-M,a[i])%mod;}cout<<ans<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021牛客多校9 - Cells(推公式+NTT)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。