CF403D Beautiful Pairs of Numbers（计数，dp+组合数学）

组合数学）"/>

CF403D Beautiful Pairs of Numbers（计数，dp+组合数学）

首先做一个dp
f[i][j] f [ i ] [ j ] $f[i][j]$表示区间总长度为i，有j个区间，且任意两个区间的长度不同的方案数。两种转移：1、每个区间的长度都增加1， f[i][j]−>f[i+j][j] f [ i ] [ j ] − > f [ i + j ] [ j ] $f[i][j]->f[i+j][j]$
2、每个区间长度都增加1，并新增一个长度为1的区间, f[i][j]−>f[i+j+1][j+1] f [ i ] [ j ] − > f [ i + j + 1 ] [ j + 1 ] $f[i][j]->f[i+j+1][j+1]$

yy一下这样可以把所有方案都算且只算一遍。

然后考虑怎么算答案，
Ans[n][k]=∑i=knf[i][j]∗Ckn−i+k∗k! A n s [ n ] [ k ] = ∑ i = k n f [ i ] [ j ] ∗ C n − i + k k ∗ k ! $Ans[n][k]=\sum\limits_{i=k}^nf[i][j]*C_{n-i+k}^k*k!$
枚举区间总长度i，把每个区间缩成一个点，这样就有n-i+k个点，从中选出k个作为区间即可，另外这k个区间的大小顺序还没有定，还要乘上一个全排列

复杂度 O(10002+T∗n) O ( 1000 2 + T ∗ n ) $O(1000^2+T*n)$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 1010
#define mod 1000000007
inline char gc(){static char buf[1<<16],*S,*T;if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;}return *S++;
}
inline int read(){int x=0,f=1;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc();return x*f;
}
int f[N][N],ans[N][N],C[N][N],fac[N];
inline void inc(int& x,int y){x+=y;if(x>=mod) x-=mod;}
int main(){
//  freopen("a.in","r",stdin);int n=1000,K=1000;fac[0]=1;for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%mod;for(int i=0;i<=n;++i) C[i][0]=1;for(int i=1;i<=n;++i)for(int j=1;j<=i;++j)C[i][j]=(ll)(C[i-1][j]+C[i-1][j-1])%mod;f[1][1]=1;for(int i=1;i<=n;++i)for(int j=1;j<=i;++j){if(i+j<=n) inc(f[i+j][j],f[i][j]);if(i+j+1<=n) inc(f[i+j+1][j+1],f[i][j]);}int tst=read();while(tst--){n=read();K=read();if(ans[n][K]){printf("%d\n",ans[n][K]);continue;}for(int i=K;i<=n;++i)inc(ans[n][K],(ll)f[i][K]*C[n-i+K][K]%mod*fac[K]%mod);printf("%d\n",ans[n][K]);}return 0;
}