2020 CCPC 秦皇岛 H.Holy Sequence @ Wings            分类 ACM
发布于 星期五, 十二月 11 日, 2020 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

对于一个长度为$n$的正整数数列$a_n$, 他合法的条件是:

  1. $\forall i \in [1, n], a_i \in {1, 2, \dots, n}$;
  2. $\forall i \in [1, n], p_i - p_{i-1} \le 1 (p_k = max \{ a_1, a_2, \dots, a_k \}, p_0 = 0)$.

对于每一个 $t = 1, 2, \dots, n$, 求

$$\sum_{A \in S_n}cnt(A, t)^2$$

其中, $S_n$是所有长度为$n$的合法序列的集合, $cnt(A, t)$是$t$在数列$A$中出现的次数.

答案对$m$取模.

$T$组测试, 给出$n, m$

$1 \le T \le 10, 1 \le n \le 3000, 1 \le m \le 10^9$

题解

感谢zzs, 舍友书名号, 大佬jyz, 我终于理解了这道数数题.

直接求显然不合理, 我们需要从平方的组合意义上"拆贡献".

首先考虑$x^2$代表什么. 比如小明有$x$个数, 分别为$1, 2, \dots n$, 小红也有同样的$x$个数. 两人分别出一个数, 有序配对, 有多少中配对方法. 这个答案就是$x^2$.

这里只不过反过来, 把$x^2$拆成配对数, 如下:

$$cnt(A, t)^2 = \Big| \{ \left \langle i, j \right \rangle \mid a_i = a_j = t, 1 \le i, j \le n \} \Big|$$

所以有:

$$ \begin{aligned} &\sum_{A \in S_n}cnt(A, t)^2 \newline = &\sum_{A \in S_n}\Big| \{ \langle i, j \rangle \mid a_i = a_j = t, 1 \le i, j \le n \} \Big| \end{aligned} $$

这算的是"所有合法序列$A$中, 满足条件$a_i = a_j = t$的有序对$\langle i, j \rangle $有多少个". 可以转化成"对于满足条件$a_i = a_j = t$的所有有序对$\langle i, j \rangle$, 有多少个合法序列$A$"

即:

$$ \begin{aligned} &\sum_{A \in S_n} cnt(A, t)^2 \newline = &\sum_{A \in S_n} \Big| \{ \langle i, j \rangle \mid a_i = a_j = t, 1 \le i, j \le n \} \Big| \newline = &\sum_{1 \le i, j \le n} \Big| \{ A \in S_n \mid a_i = a_j = t \} \Big| \end{aligned} $$

计算有序对数量时, 如果$i \ne j$, 那么有序对数量可以用无序对数量乘以$2$表示; 如果$i=j$, 有序无序是一样的东西. 所以, 上述式子进一步可以写成:

$$ \begin{aligned} &\sum_{A \in S_n} cnt(A, t)^2 \newline = &\sum_{A \in S_n} \Big| \{ \langle i, j \rangle \mid a_i = a_j = t, 1 \le i, j \le n \} \Big| \newline = &\sum_{1 \le i, j \le n} \Big| \{ A \in S_n \mid a_i = a_j = t \} \Big| \newline = &\sum_{1 \le i < j \le n} 2 \cdot \Big| \{ A \in S_n \mid a_i = a_j = t \} \Big| + \sum_{1 \le i \le n} \Big| \{ A \in S_n \mid a_i = t \} \Big| \newline = &\sum_{1 \le i \le n} \Big| \{ A \in S_n \mid a_i = t \} \Big| + 2 \sum_{1 \le i < j \le n} \Big| \{ A \in S_n \mid a_i = a_j = t \} \Big| \end{aligned} $$

先来看如何求$\sum_{1 \le i \le n} \Big| \{ A \in S_n \mid a_i = t \} \Big|$.

枚举$i, a_i = t$, 只要能够快速知道合法的前缀和后缀各有多少, 然后相乘即可. 可以用$dp$求合法前缀和后缀. 设$f(i, j)$为最大值为$j$的长度为$i$的合法序列数量, 方程:

$$f(i, j) = j \cdot f(i-1, j) + f(i-1, j-1)$$

解释如下:

f(i, j)的转移

设$g(i, j)$为(强行)**$a_1 = j$**时, 前缀最大值增加不超过$1$, 长度为$i$的合法序列数量.

为什么要这么定义呢? 因为已经枚举了$a_i = t$, 后面的序列也满足前缀最大增加量不超过$1$, 首先得把$t$考虑进来, 然后还要考虑后面有多少个数. 这样的定义是没问题的. 难点在于方程转移:

$$g(i, j) = j \cdot g(i-1, j) + g(i-1, j+1)$$

解释如下:

g(i, j)的转移

枚举$t$第一次出现的位置$i$, 选择两个$t$配对, 有下面这些情况:

  1. 选的两个$t$相同, 都是$a_i$, 贡献为$f(i-1, t-1) \cdot g(n - i + 1, t)$
  2. 选的两个$t$不同, 第一个是$a_i$, 第二个是后面某一个$a_j = t$, 贡献为$2 \cdot f(i-1, t-1) \cdot (n-i)g(n-i, t)$(还是插入法, 在$n-1$个元素的合法后缀之间插入一个$t$, 就相当于"枚举"到了这个$a_j = t$, 有序, 乘以$2$)
  3. 选的两个$t$相同, 是后面某一个$a_j = t$, 贡献为$f(i-1, t-1) \cdot (n-1) \cdot g(n-i, t)$
  4. 选的两个$t$不同, 都在$i$后面, 贡献为$2 \cdot \tbinom{n-i}{2} f(i-1, t-1) \cdot g(n-i-1, t)$

注意到$a_i = t$的一个必要条件是$t \le i$, 在推$f$和$g$的时候需要注意.

边界条件很简单, 略.

还需注意, 在枚举$i$的过程中, 如果后面的个数不足, 则不能转移.

复杂度$O(n^2)$

代码
const int maxn = 3e3+10;

int t, n, P;

LL Plus(LL a, LL b) {
	return a + b >= P ? (a + b) % P : a + b;
}

LL Mult(LL a, LL b) {
	return a * b >= P ? a * b % P : a * b;
}

LL f[maxn][maxn], g[maxn][maxn], ans[maxn];

int main() {
	scanf("%d", &t);
	for (int kase = 1; kase <= t; kase++) {
		scanf("%d%d", &n, &P);
		memset(f, 0, sizeof(f));
		memset(g, 0, sizeof(g));
		memset(ans, 0, sizeof(ans));
		f[0][0] = 1;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= i; j++)
				f[i][j] = Plus(f[i-1][j-1], Mult(j, f[i-1][j]));
		for (int j = 1; j <= n; j++)
			g[1][j] = 1;
		for (int i = 2; i <= n; i++)
			for (int j = (n - i + 1); j; j--)
				g[i][j] = Plus(g[i-1][j+1], Mult(j, g[i-1][j]));

		// 对每个t, 枚举其第一次出现的位置i, 由**题目**可知i >= t
		for (int t = 1; t <= n; t++)
			for (int i = t; i <= n; i++) {
				// 两次选i这个位置的t
				ans[t] = Plus(ans[t], Mult(f[i-1][t-1], g[n-i+1][t]));
				// 第一次选i这个位置的t, 第二次选后面某一个t
				// 由于有序, 所以乘以2
				if (i < n)
					ans[t] = Plus(ans[t], Mult(Mult(2, f[i-1][t-1]), Mult(n-i, g[n-i][t])));
				// 两次选后面同一个t
				if (i < n)
					ans[t] = Plus(ans[t], Mult(f[i-1][t-1], Mult(n-i, g[n-i][t])));
				// 两次选后面不同的t
				if (i + 1 < n)
					ans[t] = Plus(ans[t], Mult(Mult(f[i-1][t-1], n-i), Mult(n-i-1, g[n-i-1][t])));
			}
		printf("Case #%d:\n", kase);
		for (int t = 1; t <= n; t++)
			printf("%lld ", ans[t]);
		puts("");
	}
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球
  • 三阶速拧20s

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch