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

题目链接：D. Beautiful Pairs of Numbers

题意：

定义k对(a,b)搜索美丽的，当且仅当满足：
$1\le a1\le b1\le 1\le a2\le b\mathrm{2...}\le ak\le bk\le n$，,并且所有的$bi-ai$都是唯一的
$(1\le k\le n\le 1000)$

题解：

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

Humble Numbers 简单DP

rar 0星 超过10%的资源 49KB

下载

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

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

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

3.代码实现

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
	#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(mmp;
struct comp{
	public:
		bool operator()(elemt v1,elemt v2){
			return v1.v --小顶堆  less --大顶堆  
priority_queue,comp>q;

	set::iterator it=st.begin();
*/
//emplace_back()  等于push_back(),但效率更高,传输pair时emplace_back(i,j)==push_back({i,j}) 
// vector>edge; 二维虚拟储存坐标 
//-----------------------------------------------------------------------------------------------------------------*/
//mt19937 rnd(time(0));//高质量随机化函数，直接调用rnd()即可
//mapmp[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<
/*cout<
	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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156