Codeforces 403D Beautiful Pairs of Numbers(组合数学DP)

组合数学DP)"/>

Codeforces 403D Beautiful Pairs of Numbers(组合数学DP)

Codeforces 403D Beautiful Pairs of Numbers(组合数学DP)

题目链接：D. Beautiful Pairs of Numbers

题意：

定义k对(a,b)搜索美丽的，当且仅当满足：
1 ≤ a 1 ≤ b 1 ≤ 1 ≤ a 2 ≤ b 2... ≤ a k ≤ b k ≤ n 1\leq a1\leq b1\le1\leq a2 \leq b2...\leq ak\leq bk \leq n 1≤a1≤b1≤1≤a2≤b2...≤ak≤bk≤n，,并且所有的 b i − a i bi-ai bi−ai都是唯一的
( 1 ≤ k ≤ n ≤ 1000 ) (1 ≤ k ≤ n ≤ 1000) (1 ≤ k ≤ n ≤ 1000)

题解：

1. 预处理数组 f [ ] [ ] f[][] f[][]

这题实际上可以看成是区间分配问题，即把一个大区间分配给 k k k个不同长度的区间，首先我们需要预处理一个数组 f [ i ] [ j ] f[i][j] f[i][j]表示 j j j个不同长度的区间，总长度为 i i i的方案数，状态转移方程：
1. f [ i + j ] [ i ] + = f [ i ] [ j ] 1.f[i+j][i]+=f[i][j] 1.f[i+j][i]+=f[i][j], 即将当前每个区间长度都增加 1 1 1,（因为每一个区间长度都得不一样，每个都 + 1 +1 +1，保持了其原有的长度唯一性）
2. f [ i + j + 1 ] + = f [ i ] [ j ] 2.f[i+j+1]+=f[i][j] 2.f[i+j+1]+=f[i][j]，即将当前每个区间长度都增加 1 1 1并且加入一个长度为 1 1 1的新区间.

2 对于给定 n , k n,k n,k进行求解

预处理完数组 f f f后我们可以对每次询问的 n , k n,k n,k进行求解：
每个 n , k n,k n,k对应的答案为 ∑ i = k n （ f [ i ] [ k ] ∗ C ( n − i + k , k ) ∗ k ! ） \sum_{i=k}^{n}（f[i][k]*C(n-i+k,k)*k!） ∑i=kn​（f[i][k]∗C(n−i+k,k)∗k!），其中 ∑ i = k n \sum_{i=k}^{n} ∑i=kn​表示我所有区间占用的总长度范围是 [ k , n ] [k,n] [k,n]， （ f [ i ] [ k ] ∗ C ( n − i + k , k ) ∗ k ! ） （f[i][k]*C(n-i+k,k)*k!） （f[i][k]∗C(n−i+k,k)∗k!）表示对于每个总长度 i i i，我分配区间长度的方案有 f [ i ] [ k ] f[i][k] f[i][k]种，其中我实际占用的区间有 k k k个,还有 n − i n-i n−i个没被占用的点可以作为长度为 1 1 1的区间插在我占用的区间之中，其总插入方案数为 C ( n − i + k , k ) C(n-i+k,k) C(n−i+k,k)，而因为我占用的区间之间的顺序也是不确定的，所有可以占用的区间的合法顺序有 k ! k! k!种，综合（乘）起来对于占用总长度为i的方案有 （ f [ i ] [ k ] ∗ C ( n − i + k , k ) ∗ k ! ） （f[i][k]*C(n-i+k,k)*k!） （f[i][k]∗C(n−i+k,k)∗k!）种。

3.代码实现

#include<iostream>
#include<stack>
#include<list>
#include<set>
#include<vector>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<map>
#include<cstring>
#include<queue>
#include<iomanip>
#include<cmath>
#include<ctime>
#include<random>
#include<queue>
#include <bitset>
#include<unordered_map>#ifndef local#define endl '\n'
#endif */
#define mkp make_pair
using namespace std;
using std::bitset;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll MAXN=1e4+10;
const ll INF=1e18;
const ll N=2e5+100;
const ll mod=1e9+7;
const ll hash_p1=1610612741;
const ll hash_p2=805306457;
const ll hash_p3=402653189;
//-----------------------------------------------------------------------------------------------------------------*/
// ll head[MAXN],net[MAXN],to[MAXN],edge[MAXN]/*流量*/,cost[MAXN]//费用;
/* 
void add(ll u,ll v,ll w,ll s){to[++cnt]=v;net[cnt]=head[u];edge[cnt]=w;cost[cnt]=s;head[u]=cnt;to[++cnt]=u;net[cnt]=head[v];edge[cnt]=0;cost[cnt]=-s;head[v]=cnt;
}
struct elemt{int p,v;
};
-----------------------------------
求[1,MAXN]组合式和逆元 
ll mi(ll a,ll b){ll res=1;while(b){if(b%2){res=res*a%mod;}	a=a*a%mod;b/=2;}return res;
}
ll fac[MAXN+10],inv[MAXN+10];
void init(){fac[0]=1;inv[0]=1;for(ll i=1;i<=MAXN;i++){fac[i]=(fac[i-1]*i)%mod;inv[i]=mi(fac[i],mod-2);}
}
ll C(int m,int n){//组合式C(m,n); if(!n){return 1;}if(m<n){return 0;}return fac[m]*(inv[n]*inv[m-n]%mod)%mod;
}
ll lucas(int m,int n){//求C(m,n).一般用于m，n很大而mod很小，或者n，m不大但大于mod的情况(一般为mod不确定时用)return n?C(m%mod,n%mod)*lucas(m/mod,n/mod)%mod:1;
}
---------------------------------unordered_map<int,int>mp;
struct comp{public:bool operator()(elemt v1,elemt v2){return v1.v<v2.v;}
};
//优先队列默认小顶堆 ， greater<int> --小顶堆  less<int> --大顶堆  
priority_queue<elemt,vector<elemt>,comp>q;set<int>::iterator it=st.begin();
*/
//emplace_back()  等于push_back(),但效率更高,传输pair时emplace_back(i,j)==push_back({i,j}) 
// vector<vector<int>>edge; 二维虚拟储存坐标 
//-----------------------------------------------------------------------------------------------------------------*/
//mt19937 rnd(time(0));//高质量随机化函数，直接调用rnd()即可
//map<int,bool>mp[N]; 
//emplace_back() 
/*
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
*/
ll mi(ll a,ll b){ll res=1;while(b){if(b%2){res=res*a%mod;}	a=a*a%mod;b/=2;}return res;
}
ll fac[MAXN+10],inv[MAXN+10];
void init(){fac[0]=1;inv[0]=1;for(ll i=1;i<=MAXN;i++){fac[i]=(fac[i-1]*i)%mod;inv[i]=mi(fac[i],mod-2);}
}
ll C(int m,int n){//组合式C(m,n); if(!n){return 1;}if(m<n){return 0;}return fac[m]*(inv[n]*inv[m-n]%mod)%mod;
}
ll f[2100][2100];//长度为i的区间分成j个不同长度区间的方案数
int main(){
/*cout<<setiosflags(ios::fixed)<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（不含整数部分）*/
/*cout<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（含整数部分）*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//同步流init();f[1][1]=1;for(int i=1;i<=1000;i++){for(int j=1;i+j<=1000;j++){(f[i+j][j]+=f[i][j])%=mod;//每个区间都+1(f[i+j+1][j+1]+=f[i][j])%=mod;//每个区间都+1，再加入一个长度为1的新区间}}int t;cin>>t;while(t--){int n,k;cin>>n>>k;ll ans=0;for(int i=k;i<=n;i++){ll tmp=f[i][k]*C(n-i+k,k)%mod*fac[k]%mod;ans=(ans+tmp)%mod;}cout<<ans<<endl;}return 0;
}