1 条题解
-
0

#include <cstdio> #include <cmath> const int M = 100005; const int MOD = 1e9+7; #define int long long int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,m,k,dp[500][M],fac[2*M],inv[2*M],ans; void init(int n) { fac[0]=inv[0]=inv[1]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD; for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD; for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%MOD; } int C(int n,int m) { if(n<m || m<0) return 0; return fac[n]*inv[m]%MOD*inv[n-m]%MOD; } int cal(int x) { return C(x+n-1,n-1); } signed main() { //freopen("perm.in","r",stdin); //freopen("perm.out","w",stdout); n=read();k=read();init(2e5); dp[0][0]=1;m=499; for(int i=1;i<=m;i++) { for(int j=i;j<=k;j++) { dp[i][j]=(dp[i-1][j-i]+dp[i][j-i])%MOD; if(j>=n+1) dp[i][j]=(dp[i][j]-dp[i-1][j-n-1])%MOD; } } for(int i=0;i<=m;i++) for(int j=0;j<=k;j++) { int f=(i%2?-1:1); ans=(ans+1ll*f*dp[i][k-j]*cal(j))%MOD; } printf("%lld\n",(ans+MOD)%MOD); }
- 1
信息
- ID
- 10455
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者