[清华集训]小 Y 和恐怖的奴隶主

时间：2023-03-08 17:55:22

题面在这里

题意

有一个\(Boss\)和他血量为\(m\)的随从奴隶主,每当奴隶主受到攻击且不死，并且\(Boss\)的随从个数\(<k\)时，就会新召唤一个血量为\(m\)的奴隶主。每次攻击\(Boss\)和每个奴隶主的概率是相同的，求\(n\)步后期望对\(Boss\)造成的伤害。

\(T\le1000,n\le10^{18},m\le3,k\le8\)

sol

看到\(m<=3,k<=8\)的良心数据肯定是状压啦

通过暴搜可以得出状态最多只会有\(164\)种

并且两个状态之间的转移是固定的

因此我们考虑矩阵快速幂

但是...时间复杂度为\(O(T164^3logn)\)跑得过？

因此，优化这种矩乘的方法横空出世:

由于一个向量乘上一个矩阵的复杂度是\(O(n^2)\)的，因此我们把\(2^i\)的矩阵全部预处理出来，

最后再使用倍增的手段进行合并

时间复杂度变成了\(O(164^3logn+T164^2logn)\)，非常需要卡常。。。

下面代码不保证能一次通过

代码

#include<bits/stdc++.h>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<iomanip>

#include<cstring>

#include<complex>

#include<vector>

#include<cstdio>

#include<string>

#include<bitset>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

#define mp make_pair

#define pb push_back

#define RG register

#define il inline

using namespace std;

typedef unsigned long long ull;

typedef vector<int>VI;

typedef long long ll;

typedef double dd;

const dd eps=1e-10;

const int mod=998244353;

const int N=50010;

il ll read(){

	RG ll data=0,w=1;RG char ch=getchar();

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();

	return data*w;

}

il void file(){

	//freopen("a.in","r",stdin);

	//freopen("a.out","w",stdout);

}

ll poww(ll a,ll b){

	RG ll ret=1;

	for(a%=mod;b;b>>=1,a=a*a%mod)

		if(b&1)ret=ret*a%mod;

	return ret;

}

ll n,Tim,m,k,ans,tot;

int a[4],t[4];

int b[9][9][9];

struct node{

	int x,y,z,id,p;

	il void print(){printf("x=%d,y=%d,z=%d,id=%d,p=%d\n",x,y,z,id,p);}

};

vector<node>sol;

int S[170],z[170];

struct matrix{

	int a[170][170];

	il void clear(){memset(a,0,sizeof(a));}

	il void print(){

		for(RG int i=1;i<=tot;i++,puts(""))

			for(RG int j=1;j<=tot;j++)

				printf("%d ",a[i][j]);

		puts("");

	}

	int* operator [](int x){return a[x];}

}T[61],P;

il void dfs(int s[]){

	int p[4];

	b[s[1]][s[2]][s[3]]=++tot;

	P[b[s[1]][s[2]][s[3]]][b[s[1]][s[2]][s[3]]]=poww(s[1]+s[2]+s[3]+1,mod-2)%mod;

	sol.pb((node){s[1],s[2],s[3],tot,poww(s[1]+s[2]+s[3]+1,mod-2)});

	for(RG int i=1;i<=3;i++)

		if(s[i]){//枚举要打的是哪一个

			for(RG int j=1;j<=3;j++)p[j]=s[j];

			if(s[1]+s[2]+s[3]<k){if(i!=1){p[m]++;p[i-1]++;}p[i]--;}

			else{p[i]--;if(i!=1)p[i-1]++;}

			RG int add=1ll*s[i]*poww(s[1]+s[2]+s[3]+1,mod-2)%mod;

			if(!b[p[1]][p[2]][p[3]])dfs(p);

			(P[b[s[1]][s[2]][s[3]]][b[p[1]][p[2]][p[3]]]+=add)%=mod;

		}

}

il matrix times1(RG matrix x,RG matrix y){

	RG matrix z;z.clear();

	for(RG int i=1;i<=tot;i++)

		for(RG int j=1;j<=tot;j++)

			for(RG int k=1;k<=tot;k++)

				z[i][k]=(z[i][k]+1ll*x[i][j]*y[j][k]%mod)%mod;

	return z;

}

il void times2(RG matrix y){

	memset(z,0,sizeof(z));

	for(RG int j=1;j<=tot;j++)

		for(RG int k=1;k<=tot;k++)

			z[k]=(z[k]+1ll*S[j]*y[j][k]%mod)%mod;

	for(RG int i=1;i<=tot;i++)S[i]=z[i];

}

il void DP(ll n){

	ans=0;memset(S,0,sizeof(S));S[1]=1;

	for(RG ll i=1;(((ll)1)<<(i-1))<=n;i++)

		if((n&(((ll)1)<<(i-1)))==(((ll)1)<<(i-1)))

			times2(T[i]);

	ans=S[tot];

}

int main()

{

	file();Tim=read();m=read();k=read();a[m]=1;dfs(a);tot++;

	for(RG int i=1;i<=tot-1;i++)P[i][tot]=sol[i-1].p;P[tot][tot]=1;

	T[1]=P;for(RG int i=2;i<=60;i++)T[i]=times1(T[i-1],T[i-1]);

	while(Tim--){n=read();DP(n);printf("%lld\n",ans);}

	return 0;

}

相关文章