OI - 空之轨迹(NOIP模拟赛)


没见过这种奇怪的状压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,欢迎提问!

0%