OI - 空之轨迹（NOIP模拟赛） | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 空之轨迹（NOIP模拟赛）

发表于 更新于 分类于 Valine：

没见过这种奇怪的状压DP，可以借鉴一下……

Part1. 题目

Part1/1. 简化版

Iri 正在玩一个游戏。游戏共有 $n$ 个章节（不包括序章），每完成一个章节就会获得一个“通过该章节”的存档 —— 当载入“通过第 $i$ 个章节”的存档时，会进入第 $i+1$ 个章节。

第 $i$ 个章节包含 $a_i$ 次战斗。

Iri 的游戏技术非常好，你可以认为他可以通过任意章节。他一开始有一个序章的存档（载入后会进入第 $1$ 章节）。他每一次会在已有的存档中 等概率地 随机载入一个存档（注意：可能同时存在多个同一章节的存档，比如说 如果他玩了 $3$ 次第二章，他就会有 $3$ 个第二章的存档，载入其中任意一个都可以进入第三章）。

Iri 现在想要玩 $m$ 次，他希望知道 自己玩的章节的战斗总数 的期望值。

Part1/2. 数据规模

对于 $100\%$ 的数据，保证 $1\leq m\leq21$，$m\leq n\leq10^5$，$0\leq a_i\leq10$。

Part2. 考场思路

Tab. 这个不是题解，Part3 才是

一开始其实题面并没有讲清楚，到底会不会存在“同一章有多个存档”的情况……

而且第 1,2 个样例对于两种理解方法，答案都是一样的……第 3 个样例太大了没法调 QwQ

因为如果“同一章只会有一个存档，先前的存档会被覆盖掉”，这道题就简单了许多，所以我就先这样考虑的。因为只有通过第 $i$ 关才能进入第 $i+1$ 关，且“同一章只有一个存档”，所以通过了多少关就有多少个存档，据此定义 f[i][j] 表示玩了 j 次，通过了 i 关的概率（这里定义成 概率 是从纪中那边学过来的……）。然后就解决了这个 理解错误 的问题……

当时代码都打完了，调试第 1,2 个样例调了一会，非常肯定地认为自己写了 AC 代码。然后测试到第 3 个样例就 WA 了，于是乎知道自己理解错题意了 ……

最后写了一个大暴力，惊喜地发现它跑得很快 awa；加上一个特判就挖了 50pt 跑了 ←_←

也想过状压的，也知道玩的章节的顺序没有影响，然而……咳

Part3. 正解

Part3/1. 两结论

定义一个可重集合表示当前 Iri 有的存档。比如 $\{0,1,1,2\}$ 就表示 Iri 有 $1$ 个序章(0)的存档、$2$ 个第 $1$ 章的存档和 $1$ 个第 $2$ 章的存档。因为 Iri 只能在完成第 $i$ 章后进入 $i+1$ 章，所以存档集合里的元素一定是连续的（结论1）。

不难发现，Iri ”获得这些存档的顺序、怎样获得这些存档“都不会影响后续的选择（结论2）。比如 Iri 当前有 $\{0,1,1\}$——无论他如何获得的这些存档：他有 $\frac13$ 的概率载入序章存档，从而进入第一章，获得第一章的存档，存档变为 $\{0,1,1,1\}$；有 $\frac23$ 的概率载入第一章存档，从而进入第二章，获得第二章的存档，变为 $\{0,1,1,2\}$。

Part3/2. 状压

根据以上的两个结论，对于存档集合 $A=\{a_1,a_2,…,a_n | \forall_{1\leq i<n}a_i\leq a_{i-1}\}$，我们可以把它变成另外一个集合 $B=\{a_2-a_1,a_3-a_2,…,a_n-a_{n-1}\}$。因为 $A$ 中相邻元素之差不超过 $1$，所以 $B$ 中的元素要么是 $0$，要么是 $1$；且 $A$ 与 $B$ 一一对应。因此，$A$ 能够被唯一表示为一个（带前导零的）二进制数，就可以状压。

定义 f[i][S] 表示玩了 i 次后，Iri 的存档为 S 的方案数。其中 S 就是上述转换成 集合$B$ 后的二进制数。

考虑刷表法（我为人人），例如从 f[i][S] 向其他 DP 值更新。根据 S，我们可以还原出当前存档的具体情况（即每个章节的存档有多少个）：

1
2
3
4
5
int mxj=0;Fcnt[0]=0; //Fcnt[i] 即第 i 章的存档有多少个
for(int j=0;j<=i;j++){
	if(S&(1<<j)) Fcnt[++mxj]=0;
	Fcnt[mxj]++;
}

然后我们从中选择章节 i 的存档载入，则一共有 Fcnt[i] 个存档可以选择，即 Fcnt[i] 种方案。然后 Iri 就会进入第 $i+1$ 章，并获得一个 $i+1$ 章的存档：

1
2
3
4
5
6
7
8
9
10
for(int j=0;j<mxj;j++){ //枚举选择哪一个章节（不会进入一个新的章节）
	VS=(S>>Ecnt[j+1]);
	VS=(VS<<(Ecnt[j+1]+1))|(S^(VS<<Ecnt[j+1])); //更新二进制数，需要一些位运算技巧
	Ef[i+1][VS]=(Ef[i+1][VS]+1ll*Ef[i][S]*Fcnt[j]%MOD)%MOD; //统计方案数
	Eexi[i+1][VS]=true; //标识该方案是否存在
}
//进入新章节
VS=S|(1<<Ecnt[mxj]); //更新二进制数
Ef[i+1][VS]=(Ef[i+1][VS]+1ll*Ef[i][S]*Fcnt[mxj]%MOD)%MOD;
Eexi[i+1][VS]=true;

最后统计答案时，计算 ”所有方案的战斗次数之和 除以 总方案数“ 即可。总方案数是 $m!$，因为当 Iri 第 $i$ 次载入存档时，他有 $i$ 个存档，也就有 $i$ 种选择。

Part3/3. 另外

发现直接定义状态会 MLE……于是把第一维开成滚动数组。

然后这是一道万恶的卡常题，如果你定义数组的习惯好（不像我一样），你可能还不会被卡。因为状压的二进制数是很大的（$2^{m+1}$） ，一定要把 DP 数组定义成 f[i][S] 而不是 f[S][i] 的样子。这种卡常是 系统处理数据的方式 导致的。

Part4. 总结

当发现一个 元素顺序不影响且元素连续 的数列，就把它看成一个可重集合，并把这个可重集合 相邻两数之差 作为新的可重集合。从而可以状态压缩！

Part5. 源代码 <\>

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const ll MOD=998244353;
const int N=1e5,M=21;

int n,m;
int Ia[N+3],Ef[2][(1<<M+1)+3];
bool Eexi[2][(1<<M+1)+3];
int Ecnt[M+10],Fcnt[M+10];

ll QPow(ll Ca,ll Cb){
	ll Rt=1;
	while(Cb){
		if(Cb&1) Rt=Rt*Ca%MOD;
		Ca=Ca*Ca%MOD;
		Cb>>=1;
	}
	return Rt;
}
int main(){
	freopen("kiseki.in","r",stdin);
	freopen("kiseki.out","w",stdout);
	scanf("%d%d",&n,&m);
	ll fram=1;
	for(int i=1;i<=m;i++) fram=fram*i%MOD;
	for(int i=1;i<=n;i++) scanf("%d",&Ia[i]);
	Ef[0][0]=1;Eexi[0][0]=true;
	for(int i=0;i<m;i++){
		int I=i&1,J=!I;
		for(int S=0;S<(1<<m);S++){
			if(!Eexi[I][S]) continue;
			int mxj=0;Ecnt[0]=Fcnt[0]=0;
			for(int j=0;j<=i;j++){
				if(S&(1<<j)) Ecnt[++mxj]=Ecnt[mxj-1],Fcnt[mxj]=0;
				Ecnt[mxj]++;
				Fcnt[mxj]++;
			}
			int VS;
			for(int j=0;j<mxj;j++){
				VS=(S>>Ecnt[j+1]);
				VS=(VS<<(Ecnt[j+1]+1))|(S^(VS<<Ecnt[j+1]));
				Ef[J][VS]=(Ef[J][VS]+1ll*Ef[I][S]*Fcnt[j]%MOD)%MOD;
				Eexi[J][VS]=true;
			}
			VS=S|(1<<Ecnt[mxj]);
			Ef[J][VS]=(Ef[J][VS]+1ll*Ef[I][S]*Fcnt[mxj]%MOD)%MOD;
			Eexi[J][VS]=true;
			Ef[I][S]=Eexi[I][S]=0;
		}
	}
	ll Vans=0;
	for(int S=0;S<(1<<m+1);S++){
		if(!Eexi[m&1][S]) continue;
		int Ecnt[M+10]={},mxj=0;
		for(int j=0;j<=m;j++){
			if(S&(1<<j)) mxj++;
			Ecnt[mxj]++;
		}
		for(int j=1;j<=mxj;j++)
			Vans=(Vans+1ll*Ecnt[j]*Ia[j]%MOD*Ef[m&1][S]%MOD)%MOD;
	}
	printf("%lld\n",Vans*QPow(fram,MOD-2)%MOD);
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com，欢迎提问！