题解：CF403D Beautiful Pairs of Numbers

CF Duel 到的，极限拿下了。

题目大意

有

t

个询问，每个询问给定

n

，

k

，求满足以下条件的长度为

k

的二元组序列个数：

$1 \leq a_{1} \leq b_{1} < a_{2} \leq b_{2} < \ldots < a_{k} \leq b_{k} \leq n$ 。
所有数 $b_{1}-a_{1}$ ， $b_{2}-a_{2}$ ， $\ldots$ ， $b_{k}-a_{k}$ 两两不同。

分析

首先

b

与

a

的差两两不同，且

a

、

b

都不降，说明

a

、

b

增长很快，

k

太大时答案都是

0

，构造一下，最坏情况下是

(1,1),(2,4),(5,8),(9,13)...

算一下 $k$ 大于 $50$ 答案就肯定是 $0$ 。

此时可以

O(n^2k)

了，尽量往上靠。

然后可以把

(a_i,b_i)

看成一个区间

[a_i,b_i]

，此时我们只需要知道区间总长度

s

，那么这个总长度贡献的答案就是 $\frac{(k+n-s)!}{(n-s)!}$ （每个区间的左端点 和 不在任何区间里的点 的任意一种排列方法都对应一种方案，除掉的是 不在任何区间里的点 的内部顺序）。

此时就很像 DP 了，先确定两个状态：目前加入了几个区间、此时区间总长度。

现在考虑第二个限制，转化后就是区间长度两两不同，这个两两不同十分不好处理，所以我们可以考虑按长度从小到大加入区间，并保证每种长度之加入一次。

此时状态就完全出来了：

f_{i,j,k}

表示目前加入了

i

个区间，目前只加入了了长度

\le j

的区间，总长度为

k

的方案数。

转移：

f_{i,j,k}=f_{i,j-1,k}+f_{i-1,j-1,k-j}

：分别对应加入/不加入长度为

j

的区间。

最后统计答案时枚举最终区间总长度并用刚刚那个式子贡献就行了。

注意

开不下

O(50n^2)

的数组，开太小又会 RE，所以要把询问离线下来，对

k

作扫描线（也就是把

k

相等的统一处理）。

code

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll read()
{
	ll ret = 0 ,f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -f : f) ,ch = getchar();
	while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0' ,ch = getchar();
	return ret * f;
}

const int mod = 1e9 + 7;
const int N = 1010 ,K = 50 ,T = 2e5 + 10;
ll f[2][N][N]; //滚动优化空间 
ll fac[N] ,inv[N] ,ans[T];

struct Q{
	int n ,id;
};
vector<Q> que[K];

ll qpow(ll a ,ll b)
{
	ll ret = 1;
	while (b)
	{
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}

int main()
{
	fac[0] = inv[0] = 1;
	for (int i = 1;i < N;i++) fac[i] = fac[i - 1] * i % mod;
	inv[N - 1] = qpow(fac[N - 1] ,mod - 2);
	for (int i = N - 2;i >= 1;i--) inv[i] = inv[i + 1] * (i + 1) % mod; //预处理阶乘及其逆元 
	
	int t = read();
	
	for (int i = 1;i <= t;i++)
	{
		int n = read() ,k = read();
		
		ll now = 0;
		bool f = false;
		for (int j = 0;j < k;j++)
		{
			now++ ,now += j;
			if (now > n) { ans[i] = 0; f = true; break; } //判答案为 0 
		}
		if (!f) que[k].push_back({n ,i}); //把答案不为0的询问离线下来 
	}
	
	for (int i = 0;i < N;i++) f[0][i][0] = 1;
	for (int i = 1 ,nw = 1;i < K;i++ ,nw ^= 1)
	{
		memset(f[nw] ,0 ,sizeof(f[nw])); 
		for (int j = 1;j < N;j++)
			for (int k = 0;k < N;k++)
			{
				f[nw][j][k] = f[nw][j - 1][k];
				if (k >= j) f[nw][j][k] = (f[nw][j][k] + f[nw ^ 1][j - 1][k - j]) % mod; //转移 
			}
		
		for (auto q : que[i])
		{
			int id = q.id ,n = q.n;
			for (int j = 1;j <= n;j++)
				ans[id] = (ans[id] + f[nw][n][j] * fac[i + n - j] % mod * inv[n - j] % mod) % mod; //贡献答案 
		}
	}
	
	for (int i = 1;i <= t;i++) printf("%lld\n",ans[i]);
	
	return 0;
}

题解：CF403D Beautiful Pairs of Numbers

文章操作

题目大意

分析

注意

code

相关推荐

评论

题解：CF403D Beautiful Pairs of Numbers