「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（似乎无卵用）

---

代码

#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;
}