(补一下,直接用 `NumPy` 的矩阵乘法会(因为溢出?)而 WA 掉 #2)
by iwoeix @ 2023-07-25 14:22:28
更新后代码:
```python
import numpy as np
def popcount(x): return bin(x).count('1')
P = int(1e9 + 7)
class matrix:
def __init__(self, x): self.x = x
def __matmul__(self, other): return matrix(np.array([[np.sum(self.x[i] @ other.x[:, j] % P, dtype=np.int64) % P for j in range(other.x.shape[1])] for i in range(self.x.shape[0])], dtype=np.int64))
n, m, k = map(int, input().split())
b = matrix(np.zeros((1 << m, 1 << m), dtype=np.int64))
for i in range(1 << m):
if popcount(i) > k: continue
b.x[i >> 1][i] = 1
j = (i >> 1) | (1 << (m - 1))
if popcount(j) <= k:
b.x[j][i] = 1
res = matrix(np.identity(1 << m, dtype=np.int64))
while n:
if n & 1: res = res @ b
b = b @ b
n >>= 1
print(res.x.trace() % P)
```
by iwoeix @ 2023-07-25 14:28:32