Solution - P9035 「KDOI-04」Pont des souvenirs

Posted on Edited on

P9035 「KDOI-04」Pont des souvenirs

题意

给定正整数 n,kn,k，求有多少个长度为 nn 的正整数序列 aa 满足：

  • 0<a1≤a2≤a3≤⋯≤an≤k0<a_1\le a_2\le a_3\le\cdots\le a_n\le k；
  • ∀ i≠j\forall\ i\not=j，ai+aj≤k+1a_i+a_j\le k+1。

题解

首先发现第二个条件实际上不是很强，因为 {a}\{a\} 是单调不降的，所以只需满足 an−1+an≤ka_{n-1} + a_{n} \leq k 就好了。

而第一个条件很像一个组合数能算的东西。那么我们不妨定义 f(x,y)f(x,y) 表示满足 0<a1≤a2≤a3≤⋯≤ax≤y0<a_1\le a_2\le a_3\le\cdots\le a_x\le y 的数列个数。由于第二个条件只作用于最后两个数，我们不妨枚举 ana_n。当 an=xa_n=x 时，有 an−1≤k+1−xa_{n-1}\leq k+1-x 和 an−1≤xa_{n-1}\leq x 同时成立，那么答案为：

∑x=1kf(n−1,min⁡{x,k−x+1})\sum_{x=1}^{k} f(n-1,\min\{x,k-x+1\})

观察式子发现，函数的第二维是先递增再递减的。我们不妨把它拆开。当 kk 为奇数时：

∑x=1k+12f(n−1,x)   +∑x=1k−12f(n−1,x)\sum_{x=1}^{\frac{k+1}{2}} f(n-1,x)\ \ \ +\sum_{x=1}^{\frac{k-1}{2}} f(n-1,x)

当 kk 为偶数时：

2⋅∑x=1k2f(n−1,x)2\cdot\sum_{x=1}^{\frac{k}{2}} f(n-1,x)

接下来考虑如何求得 f(x,y)f(x,y)。

首先有一个非常明显的递推式：我们依然枚举最后一位，那么前面 x−1x-1 位是随便选的，就得出了：

f(x,y)=∑i=1yf(x−1,i)f(x,y) = \sum_{i=1}^{y} f(x-1,i)

这个式子看起来一点用都没有，但实际上它可以优化之前我们得出的答案式子。答案就变为了，kk 为奇数时：

f(n,k+12)+f(n,k−12)f(n,\frac{k+1}{2})+f(n,\frac{k-1}{2})

kk 为偶数时：

2⋅f(n,k2)2\cdot f(n, \frac{k}{2})

这下看起来简洁多了。由于第一个条件十分简洁，我们不妨考虑用组合数直接求出 f(x,y)f(x,y)。

由于数列是单调不下降的，前面的数的选择会影响到后面的数的选择。这很不方便。于是我们采取一个常见的套路：把问题转化为一开始有 xx 个 11，有 y−1y-1 次 +1+1 的机会（原先已经有 11 了），每次可以选择一个数，让这个数和后面所有数都 +1+1。然而特殊地，我们可以不用完所有机会，于是把浪费掉的 +1+1 机会定义为给 x+1x+1 个数 +1+1。（同样的，我们也可以借助差分的思想，把原数列差分后转化为给 y−1y-1 个差分数组里的数 +1+1。）

无论如何，现在我们将问题转化为了插板法的模型：把 +1+1 看作板，数看作球，那么就转化为了在 x+1x+1 个空隙中插入 y−1y-1 块板，可以在同一空隙插入多块板。那么我们不妨再增加 y−2y-2 个空隙，那么就成了 x+y−1x+y-1 个空隙插入 y−1y-1 块板，答案是 Cx+y−1y−1C_{x+y-1}^{y-1}。（如果你交换板和球，也将得到同样的答案）

或者说更加直观一点，我们把 +1+1 也看成是数，那么就是合并一个有 xx 个元素的数组和有 y−1y-1 个元素的数组，每个数组中的元素相同（11 和 +1+1），两个数组之间的元素不相同。很显然，最后得到的数组有 x+y−1x+y-1 个元素，其中要选 xx 个 11（或者选 y−1y-1 个 +1+1 ），答案是 Cx+y−1y−1C_{x+y-1}^{y-1}。

我们也可以通过变形 f(x,y)f(x,y) 的递推式，得出 f(x,y)=f(x−1,y)+f(x,y−1)f(x,y) = f(x-1,y) + f(x,y-1)，和组合数的递推式进行对比得出通式。

多种方法殊途同归，最后我们得出 f(x,y)=Cx+y−1y−1f(x,y) = C_{x+y-1}^{y-1}。可以 O(n)O(n) 预处理 O(1)O(1) 回答。

参考代码

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
#include<bits/stdc++.h>
#define gc getchar
#define pc putchar
#define F(i,x,y) for(int i=x;i<=y;++i)
#define R(i,x,y) for(int i=x;i>=y;--i)
typedef long long LL;
inline int read(){
	int x=0;char ch=gc();bool p=1;
	while (!isdigit(ch)) ch=='-'?p=0:0,ch=gc();
	while ( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^'0'),ch=gc();
	return p?x:-x;
}
const int N=2e7,MOD=1e9+7;
int n,k,jc[N+1],nc[N+1];
inline int fpow(int a,int b){
	int s=1;
	while (b){
		if (b&1) s=(LL)s*a%MOD;
		a=(LL)a*a%MOD,b>>=1;
	}
	return s;
}
inline void INIT(){
	jc[0]=1;
	F(i,1,N) jc[i]=(LL)jc[i-1]*i%MOD;
	nc[N]=fpow(jc[N],MOD-2);
	R(i,N,1) nc[i-1]=(LL)nc[i]*i%MOD;
}
inline int C(int x,int y){
	return (LL)jc[x]*nc[y]%MOD*nc[x-y]%MOD;
}
inline int f(int x,int y){
	return C(x+y-1,y-1);
}
signed main(){
	int T=read();
	INIT();
	while (T--){
		n=read(),k=read();
		if (k&1){
			int p=(k+1)/2;
			printf("%d\n",(f(n,p)+f(n,p-1))%MOD);
		}else{
			int p=(k+1)/2;
			printf("%d\n",(f(n,p)+f(n,p))%MOD);
		}
	}
	return 0;
}