[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(n^2sqrt 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("0n"); continue; }
    printf("%dn",(ll)Ans[n][K]*fac[K]%P);
  }
  return 0;
}

最后

以上就是独特狗为你收集整理的[DP] Codeforces 403D #236 (Div. 1) D. Beautiful Pairs of Numbers的全部内容，希望文章能够帮你解决[DP] Codeforces 403D #236 (Div. 1) D. Beautiful Pairs of Numbers所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。