2021牛客多校9 - Cells(推公式+NTT)

题目链接：点击查看

题目大意：初始时给出 $n$ 个点，分别为 $\{(0,a_0),(0,a_1),\cdots ,(0,a_n)\}$，每次可以向下走或向左走，问到达点 $\{(1,0),(2,0),\cdots ,(n,0)\}$ 且路径不相交的方案数

题目分析：有向图路径不相交方案数问题，考虑 $LGV$ 定理，实质上就是要求

假设 $a_i$ 和 $b_j$ 用坐标表示，那么不难看出 $$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)$$
根据 $\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\frac{n!}{m!(n-m)!}$ 展开 $$e(a_i,b_j)=\frac{(a_i+j)!}{j!a_i!}$$

于是目标行列式为

$$M=\left|\begin{array}{cccc}\frac{(a_1+1)!}{1!a_1!}& \frac{(a_1+2)!}{2!a_1!}& \cdots & \frac{(a_1+n)!}{n!a_1!}\\ \frac{(a_2+1)!}{1!a_2!}& \frac{(a_2+2)!}{2!a_2!}& \cdots & \frac{(a_2+n)!}{n!a_2!}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{(a_n+1)!}{1!a_n!}& \frac{(a_n+2)!}{2!a_n!}& \cdots & \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!}& \cdots & \frac{(a_1+n)!}{a_1!}\\ \frac{(a_2+1)!}{a_2!}& \frac{(a_2+2)!}{a_2!}& \cdots & \frac{(a_2+n)!}{a_2!}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{(a_n+1)!}{a_n!}& \frac{(a_n+2)!}{a_n!}& \cdots & \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)& \cdots & (a_1+1)(a_1+2)...(a_1+n)\\ (a_2+1)& (a_2+1)(a_2+2)& \cdots & (a_2+1)(a_2+2)...(a_2+n)\\ ⋮& ⋮& \ddots & ⋮\\ (a_n+1)& (a_n+1)(a_n+2)& \cdots & (a_n+1)(a_n+2)...(a_n+n)\end{array}\right|$$

根据 $(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)$

所以根据行列式的初等变换，是可以通过前面的列消去后面的列，使得行列式变成

$$M=\prod _{j=1}^n\frac{1}{j!}\left|\begin{array}{cccc}(a_1+1)& (a_1+1{)}^2& \cdots & (a_1+1{)}^n\\ (a_2+1)& (a_2+1{)}^2& \cdots & (a_2+1{)}^n\\ ⋮& ⋮& \ddots & ⋮\\ (a_n+1)& (a_n+1{)}^2& \cdots & (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)& \cdots & (a_1+1{)}^{n-1}\\ 1& (a_2+1)& \cdots & (a_2+1{)}^{n-1}\\ ⋮& ⋮& \ddots & ⋮\\ 1& (a_n+1)& \cdots & (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 不难发现可以将 $a_j-a_i$ 视为背包，求出 $c[k]$ 为 $a_j-a_i=k$ 的方案数，那么答案就是 $\prod k^{c[k]}$ 了，加个偏移量当背包转移就好啦

需要注意的是，因为本题保证了 $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; }

总结

以上是生活随笔为你收集整理的2021牛客多校9 - Cells(推公式+NTT)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。