ARC110D Binomal Coefficient is Fun
给你一个序列 \(A\)，求对于所有满足 \(\sum B_i=m\) 的序列 \(B\)，\(\prod\limits_{i=1}^n\binom{B_i}{A_i}\) 的和。
\(n,A_i\le 2000,m\le 10^9\)
首先可以知道 \(\forall i,B_i\ge A_i\)，不然没贡献。
设 \(s=\sum A_i\)。其组合意义为将 \(m\) 个球分成 \(n\) 组（相当于在 \(m+n\) 个球里选走了 \(n\) 个球），再在第 \(i\) 组里选出 \(A_i\) 个球的方案数，即 \(\binom{m+n}{s+n}\)。
直接用阶乘求是 \(O(m)\) 的，考虑将原式转化为下降幂 \(\frac{(m+n)^{\underline{m-s+1}}}{(s+n)!}\)，最后时间复杂度 \(O(s+n)\)。
code
#include<bits/stdc++.h>
#define int long long
const int maxn=3e3+3;
const int mod=1e9+7;
using namespace std;
int n,m;
int a[maxn],fac[maxn*maxn],inv[maxn*maxn],invf[maxn*maxn];
int C(int a,int b){if(a<b) return 0;return fac[a]*invf[b]%mod*invf[a-b]%mod;
}
int qpow(int a,int b){int res=1;for(;b;a=a*a%mod,b>>=1) if(b&1) res=res*a%mod;return res;
}
signed main(){cin>>n>>m;inv[1]=fac[1]=1;for(int i=2;i<=maxn*maxn-9;i++){inv[i]=(mod-mod/i)*inv[mod%i]%mod;fac[i]=fac[i-1]*i%mod;}invf[maxn*maxn-9]=qpow(fac[maxn*maxn-9],mod-2);for(int i=maxn*maxn-10;i;i--) invf[i]=invf[i+1]*(i+1)%mod;int s=0;for(int i=1;i<=n;i++){cin>>a[i];s+=a[i];}int ans=1;for(int i=m-s+1;i<=m+n;i++){ans=ans*i%mod;}cout<<ans*invf[n+s]%mod;return 0;
}
CF785D Anton and School
给你一个长为 \(n\) 的括号序列，求所有形如 (((...))) 的子序列数。
\(n\le 2\times 10^5\)
考虑枚举一个位置 \(i\)，设其左边 ( 的个数为 \(L_i\)，右边 ) 的个数为 \(R_i\)，则包含 \(i(s_i=\texttt{(})\) 的合法子序列数为 \(\sum\limits_{m=1}^{\min(L_i,R_i)} \binom{L_i-1}{m-1}\binom{R_i}{m}\)（左边在剩下的 \(L_i-1\) 个 ( 里选 \(m-1\) 个，右边选 \(m\) 个），范德蒙德卷积一下
切记范德蒙德卷积下标从 0 开始！！！！！！！
时间复杂度 \(O(n)\)。
code
#include<bits/stdc++.h>
#define int long long
const int maxn=2e5+3;
const int mod=1e9+7;
using namespace std;
int n,m;
int l[maxn],r[maxn],fac[maxn],inv[maxn],invf[maxn];
int C(int a,int b){if(a<b) return 0; return fac[a]*invf[b]%mod*invf[a-b]%mod;
}
int qpow(int a,int b){int res=1;for(;b;a=a*a%mod,b>>=1) if(b&1) res=res*a%mod;return res;
}
char s[maxn];
signed main(){cin>>(s+1);n=strlen(s+1);for(int i=1;i<=n;i++)l[i]=l[i-1]+(s[i]=='(');for(int i=n;i;i--)r[i]=r[i+1]+(s[i]==')');inv[1]=fac[0]=fac[1]=1;for(int i=2;i<=n;i++){inv[i]=(mod-mod/i)*inv[mod%i]%mod;fac[i]=fac[i-1]*i%mod;}invf[n]=qpow(fac[n],mod-2);for(int i=n-1;~i;i--) invf[i]=invf[i+1]*(i+1)%mod;int ans=0;for(int i=1;i<n;i++)if(s[i]=='(')ans=(ans+C(l[i]+r[i]-1,l[i]))%mod;cout<<(ans?(ans-1):0);return 0;
}
CF1657E Star MST
有一个完全图，所有边边权在 \([1,k]\) 之间，其最小生成树权值等于所有与 \(1\) 相连的边权和，求可能的完全图数量。
\(n,k\le 250\)
设 \(f[i][j]\) 表示当前完全图中有 \(i\) 个点，MST 上的最大边权为 \(j\)，则 \(f[i][j]\leftarrow f[i-t][j-1],t\in[0,i-1]\) 即在 \(i-t\) 个点，MST 最大边权为 \(j-1\) 的图上加上 \(t\) 个点，向 \(1\) 连边的权值为 \(j\)，得到 \(i\) 个点，MST 最大边权为 \(j\) 的图。而新加的 \(t\) 个点，与其他点的连边数量为 \(w=t(i-1)-\binom{t}{2}\)，每边边权要 \(\ge j\)，方案数为 \((k-j+1)^{w}\)。
综上有转移：
时间复杂度 \(O(n^2k\log n^2)\)。
code
#include<bits/stdc++.h>
#define int long long
const int maxn=250+3;
const int mod=998244353;
using namespace std;
int n,k;
int fac[maxn],inv[maxn],invf[maxn],f[maxn][maxn];
int C(int a,int b){if(a<b) return 0;return fac[a]*invf[b]%mod*invf[a-b]%mod;
}
int qpow(int a,int b){int res=1;for(;b;a=a*a%mod,b>>=1) if(b&1) res=res*a%mod;return res;
}
signed main(){cin>>n>>k; n--;inv[1]=fac[0]=fac[1]=1;for(int i=2;i<=maxn-3;i++){inv[i]=(mod-mod/i)*inv[mod%i]%mod;fac[i]=fac[i-1]*i%mod;}invf[maxn-3]=qpow(fac[maxn-3],mod-2);for(int i=maxn-4;~i;i--) invf[i]=invf[i+1]*(i+1)%mod;f[0][0]=1;for(int i=0;i<=n;i++){for(int j=1;j<=k;j++){for(int t=i;t>=0;t--){int w=(t*(i-1)-(t-1)*t/2);f[i][j]=(f[i][j]+C(i,t)*f[i-t][j-1]%mod*qpow(k-j+1,w)%mod)%mod;}}}cout<<f[n][k];return 0;
}
ARC001E BBQ Hard
老早就讲过这个题但是一直没做？
给你两个序列 \(A,B\)，求 \(\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\binom{a_i+a_j+b_i+b_j}{a_i+a_j}\)。
\(n\le 2\times 10^5,A_i,B_i\le 2000\)
前置知识：\(\binom{a+b}{a}\) 表示从 \((0,0)\) 只往右或上走到 \((a,b)\) 的方案数。
即原式代表从 \((0,0)\) 走到 \((a_i+a_j,b_i+b_j)\) 的方案数。不难发现，只要起点和终点的相对位置不变，总方案数不变。所以我们可以将起点平移到 \((-a_i,-b_i)\)，终点为 \((a_j,b_j)\)，即可把 \(i,j\) 的贡献分开。设 \(f[i][j]\) 表示从任意位置到达 \((i,j)\) 的方案数，则只要把所有 \((a_i,b_i)\) 加 1 作为起点，即可合并统计到达任意位置的方案数，其实原理和前缀和/二维数点差不多少。时间复杂度 \(O((A_i+B_i)^2+n)\)。
code
#include<bits/stdc++.h>
#define int long long
const int mod=1e9+7;
const int maxn=2e5+3;
using namespace std;
const int N=2003;
int n,a[maxn],b[maxn];
int f[4033][4033],inv[8033],fac[8033],invf[8033];
int C(int a,int b){if(a<b) return 0;return fac[a]*invf[b]%mod*invf[a-b]%mod;
}
int qpow(int a,int b){int res=1;for(;b;a=a*a%mod,b>>=1) if(b&1) res=res*a%mod;return res;
}
signed main(){cin>>n;invf[1]=fac[1]=inv[1]=1;for(int i=2;i<=8030;i++){inv[i]=(mod-mod/i)*inv[mod%i]%mod;fac[i]=fac[i-1]*i%mod;}invf[8030]=qpow(fac[8030],mod-2);for(int i=8029;i;i--) invf[i]=invf[i+1]*(i+1)%mod;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];f[N-a[i]][N-b[i]]++;}for(int i=1;i<4030;i++){for(int j=1;j<4030;j++){f[i][j]=(f[i][j]+f[i-1][j]+f[i][j-1])%mod;}}int ans=0;for(int i=1;i<=n;i++){ans=(ans+f[N+a[i]][N+b[i]])%mod;ans=(ans-C(2*a[i]+2*b[i],2*a[i])+mod)%mod;}cout<<ans*inv[2]%mod;return 0;
}
