「LibreOJ2325」「清华集训 2017」小Y和恐怖的奴隶主 - 状态压缩+矩阵快速幂 | Bill Yang's Blog

「LibreOJ2325」「清华集训 2017」小Y和恐怖的奴隶主 - 状态压缩+矩阵快速幂

题目大意

    小Y是一个喜欢玩游戏的OIer。一天,她正在玩一款游戏,要打一个Boss。
    虽然这个Boss有$10^{100}$点生命值,但它只带了一个随从——一个只有$m$点生命值的“恐怖的奴隶主”。
    这个“恐怖的奴隶主”有一个特殊的技能:每当它被扣减生命值但没有死亡(死亡即生命值$\leq0$),且Boss的随从数量小于上限$k$,便会召唤一个新的具有$m$点生命值的“恐怖的奴隶主”。
    现在小Y可以进行$n$次攻击,每次攻击时,会从Boss以及Boss的所有随从中的等概率随机选择一个,并扣减$1$点生命值,她想知道进行$n$次攻击后扣减Boss的生命值点数的期望。为了避免精度误差,你的答案需要对$998244353$取模。


题目分析

注意到随从的血量和个数都很小,不妨将随从及其血量压入状态。
通过搜索统计总状态数为$165$个(包括无随从)。

可以预处理出从每个状态可以转移到什么状态,建立DAG表示转移关系,边权为概率。此时就可以使用矩阵快速幂统计概率。

但是要求的是期望而不是概率。
$E=p\times v$,$p$已知,而$v$不好求出,不妨使用期望的线性性质,考虑每一次转移对期望的贡献。
每一个状态转移的时候均有$\frac1{num}$的概率攻击Boss,故此时对期望的贡献为$\frac1{num}\times1=\frac1{num}$,那么期望就是每个状态的贡献相加,也就是概率之和。
因此不妨在DAG上新建一个汇点用于统计期望,每个状态均向汇点连边,边权为概率。
做矩阵快速幂即可求出期望。

注意到当前时间复杂度为$O(T166^3\log n)$,会超时。
因此优化一下,预处理$2^i$步后的矩阵,每次回答询问的时候只需要构造一个向量,让向量乘上对应的矩阵即可。
向量对矩阵的幂次计算是$O(166^2\log n)$的。
故时间复杂度为$O(165k+166^3\log n+T166^2\log n)$。

另:本题是一道毒瘤卡常数题。
卡常技巧:

  1. 矩阵快速幂时不立即取模,而是设定一个$mod$的倍数的阈值,在阈值外再取模,每次矩阵快速幂计算完一个元素后再对其取模。
    期望将取模次数从$O(166^3)$降低到$O(166^2)$。
  2. 除了矩阵快速幂以外地方少取模。
  3. 四进制状压。
  4. 循环变量自加i++改为++i(似乎无卵用)
  5. FastIO(似乎无卵用)

代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef unsigned long long LL;
namespace FastIO {
const int L=1<<15;
char buf[L],*S,*T;
char getchar() {
if(S==T) {T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
return *S++;
}
LL Get_Int() {
LL res=0;
int bj=1;
char c=getchar();
while(!isdigit(c)) {if(c=='-')bj=-1;c=getchar();}
while(isdigit(c)) {res=res*10+c-'0';c=getchar();}
return res*bj;
}
}
using FastIO::Get_Int;
const int maxn=170;
const LL mod=998244353,limit=16940360401038606353ull;
LL t,m,k,a[1005],Max=0;
void add(LL& x,LL v) {
x+=v;
if(x>=mod)x-=mod;
}
void add2(LL& x,LL v) {
x+=v;
if(x>=limit)x-=limit;
}
struct Matrix {
LL n,m,a[maxn][maxn];
Matrix(LL n=0,LL m=0) {
this->n=n;
this->m=m;
memset(a,0,sizeof(a));
}
LL* operator [] (const LL x) {
return a[x];
}
Matrix operator * (Matrix b) {
Matrix c(n,b.m);
for(int i=1; i<=n; ++i)
for(int j=1; j<=b.m; ++j) {
for(int k=1; k<=m; ++k)
add2(c[i][j],a[i][k]*b[k][j]);
c[i][j]%=mod;
}
return c;
}
} Mul[65];
int cnt=0,status=0,S[255],M[1<<16],bit[25],tmp[15];
void Dfs(int Now,int last) {
if(Now>k) {
S[++cnt]=status;
M[status]=cnt;
return;
}
for(int i=last; i<=m; ++i) {
status|=i<<bit[Now];
Dfs(Now+1,i);
status^=i<<bit[Now];
}
}
LL Quick_Pow(LL a,LL b) {
LL ans=1;
for(; b; b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
return ans;
}
LL inv(LL x) {
return Quick_Pow(x,mod-2);
}
int main() {
t=Get_Int();
m=Get_Int();
k=Get_Int();
for(int i=1; i<=k; i++)bit[i]=(i-1)<<1;
Dfs(1,0);
int Start=M[m<<bit[k]],End=cnt+1;
Matrix A(cnt+1,cnt+1);
for(int i=1; i<=cnt; ++i) {
int status=S[i],pos=k+1;
for(int j=1; j<=k; ++j)
if(status>>bit[j]&3) {
pos=j;
break;
}
LL p=inv(k-pos+2);
for(int j=pos; j<=k; ++j) {
int Next=0,num=status>>bit[j]&3;
for(int x=1; x<=k; ++x)tmp[x]=status>>bit[x]&3;
tmp[j]--;
sort(tmp+1,tmp+k+1);
for(int x=1; x<=k; ++x)Next^=tmp[x]<<bit[x];
if(num>1&&pos>1)Next=(Next>>2)^(m<<bit[k]);
add(A[i][M[Next]],p);
}
add(A[i][i],p);
add(A[i][End],p);
}
A[End][End]=1;
for(int i=1; i<=t; ++i)a[i]=Get_Int(),Max=max(Max,a[i]);
Mul[0]=A;
for(int i=1; Max; ++i,Max>>=1)Mul[i]=Mul[i-1]*Mul[i-1];
for(int i=1; i<=t; ++i) {
LL n=a[i];
Matrix Ans(1,cnt+1),tmp(1,cnt+1);
Ans[1][Start]=1;
for(int p=0; n; ++p,n>>=1) {
if(n&1) {
for(int x=1; x<=cnt+1; ++x)tmp[1][x]=Ans[1][x],Ans[1][x]=0;
for(int x=1; x<=cnt+1; ++x)
for(int y=1; y<=cnt+1; ++y)
Ans[1][y]=(Ans[1][y]+tmp[1][x]*Mul[p][x][y]%mod)%mod;
}
}
printf("%lld\n",Ans[1][End]);
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%