https://codeforces.com/contest/1288/problem/C
思路1:
开始想着这个不降数单个的话是有组合意义的,但是双个的话不太会搞。
于是暴力dp。
dp[len][i][j]=Σdp[len-1][1~i][n~j]
对于后面的暴力总复杂度O(m*n^4)
分层前缀和。先跑一个n~j的前缀和,再累加到sum[j]里面
(开始以为这个分层前缀和是个二维前缀和...弱智了..
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e3+1000;
typedef int LL;
const LL mod=1e9+7;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL dp[11][maxn][maxn];
LL sum[maxn];
int main(void){
cin.tie(0);std::ios::sync_with_stdio(false);
LL n,m;cin>>n>>m;
for(LL i=1;i<=n;i++){
for(LL j=i;j<=n;j++){
dp[1][i][j]=1;
}
}
for(LL len=2;len<=m;len++){
memset(sum,0,sizeof(sum));
for(LL i=1;i<=n;i++){
LL temp=0;
for(LL j=n;j>=i;j--){
temp=(temp%mod+dp[len-1][i][j]%mod)%mod;
sum[j]=(sum[j+1]+temp)%mod;
dp[len][i][j]=sum[j]%mod;
}
}
}
long long ans=0;
for(LL i=1;i<=n;i++){
for(LL j=i;j<=n;j++){
ans=(ans%mod+dp[m][i][j]%mod)%mod;
}
}
cout<<ans<<"\n";
return 0;
}
思路2:
不降数的组合意义没法做嘛?由这个不能关系,其实b可以移到a后面,其实整体就是个2*m的不递减。
然后上不递减的组合意义
C(m,n+m-1)这里的m是2*m
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e3+1000;
typedef long long LL;
const LL mod=1e9+7;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL fac[maxn];
LL ksm(LL a,LL k){
LL res=1;
while(k>0){
if(k&1) res=res*a%mod;
k>>=1;
a=a*a%mod;
}return res%mod;
}
LL C(LL n,LL m){
if(n>m) return 0;
return fac[m]%mod*ksm(fac[n],mod-2)%mod*ksm(fac[m-n],mod-2)%mod;
}
int main(void){
cin.tie(0);std::ios::sync_with_stdio(false);
LL n,m;cin>>n>>m;
fac[0]=1;
for(LL i=1;i<maxn;i++) fac[i]=fac[i-1]*i%mod;
cout<<C(2*m,n+2*m-1)<<"\n";
return 0;
}