题目描述
“A fight? Count me in!” 要打架了，算我一个。
“Everyone, get in here!” 所有人，都过来！
小Y是一个喜欢玩游戏的 OIer。一天，她正在玩一款游戏，要打一个 Boss。
虽然这个 Boss 有 $10^{100}$ 点生命值，但它只带了一个随从——一个只有 $m$ 点生命值的“恐怖的奴隶主”。
这个“恐怖的奴隶主”有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值 $\leq 0$），且 Boss 的随从数量小于上限 $k$，便会召唤一个新的具有 $m$ 点生命值的“恐怖的奴隶主”。
现在小Y可以进行 $n$ 次攻击，每次攻击时，会从 Boss 以及 Boss 的所有随从中的等概率随机选择一个，并扣减 $1$ 点生命值，她想知道进行 $n$ 次攻击后扣减 Boss 的生命值点数的期望。为了避免精度误差，你的答案需要对 $998244353$ 取模。
输入格式
输入第一行包含三个正整数 $T,m,k$ 表示询问组数，$m,k$ 的含义见题目描述。
接下来 $T$ 行，每行包含一个正整数 $n$，表示询问进行 $n$ 次攻击后扣减 Boss 的生命值点数的期望。
输出格式
输出共 $T$ 行，对于每个询问输出一行一个非负整数，表示该询问的答案对 $998244353$ 取模的结果。
可以证明，所求期望一定是一个有理数，设其为$p/q (\mathrm{gcd}(p,q) = 1)$ 那么你输出的数 $x$ 要满足 $p \equiv qx \mod 998244353$。
样例
输入
3 2 6
1
2
3
输出
499122177
415935148
471393168
数据范围与提示
在所有测试点中, $1\leq T \leq 1000, 1 \leq n \leq 10^{18}, 1 \leq m \leq 3, 1 \leq k \leq 8$
各个测试点的分值和数据范围如下：
| 测试点编号 | 分值 | $T=$ | $n \leq $ | $m=$ | $k=$ |
|---|---|---|---|---|---|
| 1 | 3 | 10 | 10 | 1 | 1 |
| 2 | 8 | 2 | 8 | ||
| 3 | 7 | $10^{18}$ | 3 | ||
| 4 | 12 | 7 | |||
| 5 | 30 | 20 | 3 | 5 | |
| 6 | 10 | 500 | 6 | ||
| 7 | 10 | 200 | 7 | ||
| 8 | 5 | 1000 | |||
| 9 | 10 | 100 | 8 | ||
| 10 | 5 | 500 |
题解
20pts
可以直接$DP$
同[BZOJ 4832] [Lydsy2017年4月月赛]抵制克苏恩
100pts
发现每次转移都是一样的
然后就可以矩阵快速幂了。
然而并不能过 2333
时间复杂度为$O(Tcnt^3log(n))$, $cnt$不会超过200。
我们还需要优化
我们可以将转移矩阵的 $k$ 次方全部预处理出来， 然后用一个 $1 \times cnt$ 的矩阵不断的去乘, 这样时间复杂度会被降到 $O(cnt^3log(n) + Tcnt^2log(n))$
就可以过了。
好像是道水题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline long long read()
{
long long x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MOD = 998244353;
struct Matrix
{
int a[200][200];
int n, m;
Matrix(int _n = 0, int _m = 0)
{
n = _n, m = _m;
memset (a, 0, sizeof (a));
}
Matrix operator * (const Matrix &b) const
{
Matrix ans(n, b.m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 1; k <= b.m; k++)
ans.a[i][k] = (ans.a[i][k] + 1ll * a[i][j] * b.a[j][k]) % MOD;
return ans;
}
}A[64];
long long pow_mod(long long a, int b)
{
long long ans = 1;
while (b)
{
if (b & 1) ans = ans * a % MOD;
b >>= 1;
a = a * a % MOD;
}
return ans;
}
int cnt[10][10][10], Index, IDans;
int main()
{
int T = read(), m = read(), k = read();
for (int i = 0; i <= k; i++)
for (int j = 0; j <= (m == 1 ? 0 : k); j++)
for (int l = 0; l <= ((m == 1 || m == 2) ? 0 : k); l++) if (i + j + l <= k)
cnt[i][j][l] = ++Index;
IDans = ++Index;
if (m == 1)
{
for (int i = 0; i <= k; i++)
{
if (i > 0) (A[0].a[cnt[i][0][0]][cnt[i - 1][0][0]] += i * pow_mod(i + 1, MOD - 2) % MOD) %= MOD;
(A[0].a[cnt[i][0][0]][cnt[i][0][0]] += pow_mod(i + 1, MOD - 2)) %= MOD;
(A[0].a[cnt[i][0][0]][IDans] += pow_mod(i + 1, MOD - 2)) %= MOD;
}
A[0].a[IDans][IDans] = 1;
}
else if (m == 2)
{
for (int j = 0; j <= k; j++)
for (int l = 0; l <= k; l++) if (l + j <= k)
{
if (l >= 1 && j + l + 1 <= k)
(A[0].a[cnt[j][l][0]][cnt[j + 1][l][0]] += pow_mod(j + l + 1, MOD - 2) * l % MOD) %= MOD;
if (l >= 1 && j + l + 1 > k)
(A[0].a[cnt[j][l][0]][cnt[j + 1][l - 1][0]] += pow_mod(j + l + 1, MOD - 2) * l % MOD) %= MOD;
if (j >= 1)
(A[0].a[cnt[j][l][0]][cnt[j - 1][l][0]] += pow_mod(j + l + 1, MOD - 2) * j % MOD) %= MOD;
(A[0].a[cnt[j][l][0]][cnt[j][l][0]] += pow_mod(j + l + 1, MOD - 2)) %= MOD;
(A[0].a[cnt[j][l][0]][IDans] += pow_mod(j + l + 1, MOD - 2)) %= MOD;
}
A[0].a[IDans][IDans] = 1;
}
else
{
for (int i = 0; i <= k; i++)
for (int j = 0; j <= k; j++)
for (int l = 0; l <= k; l++) if (i + j + l <= k)
{
if (i > 0)
(A[0].a[cnt[i][j][l]][cnt[i - 1][j][l]] += i * pow_mod(i + j + l + 1, MOD - 2) % MOD) %= MOD;
if (j > 0)
{
if (i + j + l + 1 <= k)
(A[0].a[cnt[i][j][l]][cnt[i + 1][j - 1][l + 1]] += j * pow_mod(i + j + l + 1, MOD - 2) % MOD) %= MOD;
else
(A[0].a[cnt[i][j][l]][cnt[i + 1][j - 1][l]] += j * pow_mod(i + j + l + 1, MOD - 2) % MOD) %= MOD;
}
if (l > 0)
{
if (i + j + l + 1 <= k)
(A[0].a[cnt[i][j][l]][cnt[i][j + 1][l]] += l * pow_mod(i + j + l + 1, MOD - 2) % MOD) %= MOD;
else
(A[0].a[cnt[i][j][l]][cnt[i][j + 1][l - 1]] += l * pow_mod(i + j + l + 1, MOD - 2) % MOD) %= MOD;
}
(A[0].a[cnt[i][j][l]][cnt[i][j][l]] += pow_mod(i + j + l + 1, MOD - 2)) %= MOD;
(A[0].a[cnt[i][j][l]][IDans] += pow_mod(i + j + l + 1, MOD - 2)) %= MOD;
}
A[0].a[IDans][IDans] = 1;
}
A[0].n = A[0].m = Index;
for (int i = 1; i <= 63; i++)
A[i] = A[i - 1] * A[i - 1];
while (T--)
{
Matrix B(1, Index);
B.a[1][cnt[m == 1][m == 2][m == 3]] = 1;
long long n = read();
for (int i = 0; i <= 63; i++)
if (n & (1ll << i))
B = B * A[i];
printf ("%d\n", B.a[1][IDans]);
}
}