[DP] Codeforces 403D #236 (Div. 1) D. Beautiful Pairs of Numbers

DP] Codeforces 403D #236 (Div. 1) D. Beautiful Pairs of Numbers"/>

[DP] Codeforces 403D #236 (Div. 1) D. Beautiful Pairs of Numbers

考虑dp 令f_{i,j} 表示i个长度不同区间总长为j的方案数
转移有

• 区间全部长度加1 f_{i,j+i}
• 区间全部长度加1再加一个长度为1的区间 f_{i+1,j+i+1}

预处理完之后就可以乘个组合数搞一搞了
复杂度 O(n2n√) $O(n^2\sqrt n)$

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){char c=nc(),b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}const int P=1e9+7;
const int N=1005;
const int maxn=1000,maxk=50;int f[maxk+5][maxn+5],C[maxn+5][maxk+5];
int Ans[maxn+5][maxk+5];
ll fac[maxk+5];inline void add(int &x,int y){x+=y; if (x>=P) x-=P;
}inline void Pre(){C[0][0]=1;for (int i=1;i<=maxn;i++){C[i][0]=1;for (int j=1;j<=maxk;j++)C[i][j]=C[i-1][j-1],add(C[i][j],C[i-1][j]); }f[0][0]=1;for (int i=1;i<=maxk;i++)for (int j=i*(i+1)/2;j<=maxn;j++)if (j>=i)f[i][j]=f[i][j-i],add(f[i][j],f[i-1][j-i]);for (int i=1;i<=maxn;i++)for (int k=1;k<=maxk;k++)for (int j=k*(k+1)/2;j<=i;j++)add(Ans[i][k],(ll)C[i-j+k][k]*f[k][j]%P);fac[0]=1; for (int i=1;i<=maxk;i++) fac[i]=fac[i-1]*i%P;
}int main(){freopen("t.in","r",stdin);freopen("t.out","w",stdout);Pre();int Q,n,K; read(Q);while (Q--){read(n); read(K); if (K>maxk) { printf("0\n"); continue; }printf("%d\n",(ll)Ans[n][K]*fac[K]%P);}return 0;
}