题意
给定 \(n, m\)。
求：
- \(a_1 + a_2 + ... + a_m = n\)
- \(1 ^ {a_1} \times 2 ^ {a_2} \times ... \times m ^ {a_m} \equiv x (\bmod m)\)
对于 \(x \in [1, m)\) 满足上述条件的方案数。
Sol
注意到下面的式子等价于：
\(1 \times 1 \times 1 ... \times 2 \times 2 ... \times... \times m\)
那么问题就变成，在 \(n\) 个格子中，插入 \([1, m]\)，使得序列单调不降，乘积与 \(x\) 在膜 \(m\) 意义下，同余的方案数。
注意到我们并不关心 \(n\)，考虑使用类似倍增的方法优化。
设 \(f_{i, l, r, k}\) 表示第 \(2 ^ i\) 个位置，值域的上下界为 \([l, r]\)，乘积膜 \(m\) 等于 \(k\)。
转移是 \(trivial\) 的。
\(f_{i, l, r, k} = \sum_{m1 = 1} ^ r \sum_{m2 = m1} ^ r\sum_{l = 0} ^ x f_{i - 1, l, m1} \times f_{i - 1, m2, r}\)
然后我们发现这个玩意可以前缀和优化。
设 \(g_{i, l, r, k} = \sum_{m1 = 1} ^ {r} g_{i, m1, r, k}\)。
复杂度为 \(O(m ^ 5 \times log(n))\)，可以通过。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <ctime>
#include <cstring>
/* #define int long long */
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int M = 41, mod = 1e9 + 7;
int _m;
void Mod(int &x) {
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
struct Matrix {
int f[M][M][M];
Matrix(int flg) {
memset(f, 0, sizeof(f));
}
friend Matrix operator *(Matrix x, Matrix y) {
for (int r = 0; r < _m; r++)
for (int k = 0; k < _m; k++)
for (int l = r - 1; ~l; l--)
y.f[l][r][k] += y.f[l + 1][r][k], Mod(y.f[l][r][k]);
Matrix ans(0);
for (int l = 0; l < _m; l++)
for (int mid = l; mid < _m; mid++)
for (int k1 = 0; k1 < _m; k1++) {
if (!x.f[l][mid][k1]) continue;
for (int r = mid; r < _m; r++)
for (int k2 = 0; k2 < _m; k2++) {
if (!y.f[mid][r][k2]) continue;
int k = k1 * k2 % _m;
ans.f[l][r][k] += 1ll * x.f[l][mid][k1] * y.f[mid][r][k2] % mod;
Mod(ans.f[l][r][k]);
}
}
return ans;
}
friend Matrix operator ^(Matrix x, int k) {
Matrix ans(0);
ans.f[0][0][1] = 1;
while (k) {
if (k & 1) ans = ans * x;
x = x * x;
k >>= 1;
}
return ans;
}
};
array <int, M> ans;
int main() {
#ifdef ONLINE_JUDGE
freopen("seq.in", "r", stdin);
freopen("seq.out", "w", stdout);
#endif
int n = read(), m = read();
_m = m;
Matrix T(0);
for (int i = 0; i < m; i++)
T.f[i][i][i] = 1;
T = T ^ n;
for (int i = 0; i < m; i++)
for (int j = i; j < m; j++)
for (int k = 0; k < m; k++)
ans[k] += T.f[i][j][k], Mod(ans[k]);
for (int i = 0; i < m; i++)
write(ans[i]), puts("");
cerr << clock() << endl;
return 0;
}