1 条题解
-
0
C++ :
#pragma GCC optimize ("O2") #include<cstdio> #define ll long long const int N=1e5+5,M=2e5+5,mo=1e9+7; int rn,n,m,i,j,ans; int fact[M],inv[M],fv[M]; void init(int n){ fact[0]=fact[1]=inv[1]=fv[0]=fv[1]=1; for (i=2;i<=n;i++){ fact[i]=(ll)fact[i-1]*i%mo; inv[i]=(ll)inv[mo%i]*(mo-mo/i)%mo; fv[i]=(ll)fv[i-1]*inv[i]%mo; } } int cal(int k){ int n=rn+k-1,m=rn-1; return (ll)fact[n]*fv[m]%mo*fv[n-m]%mo; } int sum,f[N],dp[N]; void solve(){ dp[0]=1;f[0]=1; for (i=1;i<=n;i++){ sum+=i;if (sum>m) break; for (j=m;j>=sum;j--){ dp[j]=-dp[j-i]; if (j>=n+1) dp[j]=(dp[j]+dp[j-n-1])%mo; } for (;j>=sum-i;j--) dp[j]=0; for (j=sum;j<=m;j++){ dp[j]=(dp[j]+dp[j-i])%mo; f[j]=(f[j]+dp[j])%mo; } } } int main(){ scanf("%d%d",&n,&m);rn=n; init(n+m);solve(); for (i=0;i<=m;i++) ans=(ans+(ll)f[i]*cal(m-i))%mo; printf("%d",(ans+mo)%mo); }
- 1
信息
- ID
- 1033
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者