题解 P5945 【[POI2002]协议】
Great_Influence
2020-01-21 14:46:44
可以发现，我们要求的答案是:
$$\log_2(cnt^{\frac{n}{m}})$$
其中 $cnt$ 是合法的数据包种类数。
我们就只需要求 $cnt$ 就行了。
考虑用 $dp$ 来求解这个问题。
列出 $dp$ 转移式:
$$dp[i][j] = dp[i - 1][j - 1]$$
$$dp[i][1] = (k - 1)\sum_{j = 1}^{l - 1}dp[i - 1][j]$$
时间复杂度 $O(ml)$ 。
随便一顿乱打提交， 获得 $0$ 分的好成绩。 仔细一看， 发现 $cnt$ 的数据范围过大， c++ 的 __int128 直接被爆好几圈。
因此， 我们将视线转到另一个先天支持高精度的语言: python 。
我们用 python 再将上面的 $dp$ 实现一遍即可。时间复杂度不变，但鉴于 python 的乘法复杂度为 $O((\log w)^{1.585})$ , 总时间复杂度为 $O(ml(\log ans)^{1.585})$ 。 最大的数据算出来 $\log ans \approx 3321$ 。
代码:
```python3
from math import *
import sys
k, n, m, l = map(int, input().split())
n = n // m
dp = [[], [0] * l]
dp[1][1] = k;
for i in range(2, m + 1):
dp[i & 1] = [0] * l
for j in range(2, l):
dp[i & 1][j] = dp[~ i & 1][j - 1]
for j in range(1, l):
dp[i & 1][1] += dp[~ i & 1][j]
dp[i & 1][1] *= k - 1
ans = 0
for i in range(1, l):
ans += dp[m & 1][i]
ans = ans ** n
ass = -1
while ans > 0:
ass = ass + 1
ans >>= 1
print(ass)
```