题目大意
求满足 \(\sum b_i\le m\) 的正整数数列 \(b_{1\sim n}\) 的 \(\prod\limits_{i=2}^n\binom{b_{i-1}+b_i-1}{b_i}\) 的和模 \(10^9+7\)。
\(n,m\le 200000\)
题目解法
直接给出一个非人类的结论：
答案是 \((0,0)\) 走到 \((0\sim 2m,0)\)，每一步向右下或者右上，不能越过 \(y=-1\) 和 \(y=n+1\)，且至少经过一次 \(y=n\) 的方案数。
证明：我们考虑把方案一一对应。
我们先把在 \(0\sim 1\) 层放 \(b_1\) 个右上右下
然后在 \(1\sim 2\) 层放 \(b_2\) 个右上右下，且需要插在前一层 \(b_1\) 个右上右下间隙中，方案数相当于 \(b_2\) 个相同球放到 \(b_1\) 个不同可空盒子，为 \(\binom{b_2+b_1-1}{b_2}\)
后面同理。
然后就好做了。
对于 \(n\le \sqrt m\)，暴力 \(dp\)；对于 \(n>\sqrt m\)，做反射容斥。
时间复杂度 \(O(m\sqrt m)\)
点击查看代码
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){FF=0;int RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;FF*=RR;
}
const int N=200010,P=1e9+7;
int f[2][1010];
int fac[N*2],ifac[N*2];
int qmi(int x,int y){int res=1;for(;y;y>>=1){ if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}return res;
}
int bin(int x,int y){ if(x<y||y<0) return 0;return 1ll*fac[x]*ifac[y]%P*ifac[x-y]%P;}
void comb(int n){fac[0]=1;F(i,1,n) fac[i]=1ll*fac[i-1]*i%P;ifac[n]=qmi(fac[n],P-2);DF(i,n-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%P;
}
int calc1(int n,int m){F(i,0,n) f[0][i]=0;f[0][0]=1;int ans=1;F(i,1,m){int p=i&1,q=!p;F(j,0,n) f[p][j]=((j<n?f[q][j+1]:0)+(j?f[q][j-1]:0))%P;ans=(ans+f[p][0])%P;}return ans;
}
int solve(int n,int l,int r){int res=0;for(int k=0;n-k*(r-l)>=0;k++) res=(res+bin(2*n,n-k*(r-l)))%P;for(int k=-1;n-k*(r-l)<=2*n;k--) res=(res+bin(2*n,n-k*(r-l)))%P;for(int k=0;n-k*(r-l)+r>=0;k++) res=(res-bin(2*n,n-k*(r-l)+r)+P)%P;for(int k=-1;n-k*(r-l)+r<=2*n;k--) res=(res-bin(2*n,n-k*(r-l)+r)+P)%P;return res;
}
int calc2(int n,int m){int ans=0;F(i,0,m) ans=(ans+solve(i,-1,n+1))%P;//(0,0)到(i,i)，不经过y=x-1和y=x+n+1return ans;
}
int main(){int n,m;read(n),read(m);comb(2*m);if(n>m){ puts("0");exit(0);}if(n<=1000) printf("%d\n",(calc1(n,2*m)-calc1(n-1,2*m)+P)%P);else printf("%d\n",(calc2(n,m)-calc2(n-1,m)+P)%P);return 0;
}