1 条题解
-
0

#include <bits/stdc++.h> typedef int mat[3][3], (*pmat)[3]; typedef long long ll; typedef unsigned __int128 u128; const int N = 265400; int mod, pmod; int n, K, L, x, y, g; int c[N], u[N], v[N], w[N]; int res[N], ans[N]; int G[3][3]; inline void add(int &x, const int y) {x += y - mod, x += x >> 31 & mod;} inline int C(int r, int n) {return r * (r - 1ll) / 2 % n;} ll PowerMod(ll a, int n, ll c = 1) {for (; n; n >>= 1, a = a * a % mod) if (n & 1) c = c * a % mod; return c;} namespace NT { int cnt = 0, fac[54]; void factor(int n) { int i; cnt = 0; for (i = 2; i * i <= n; ++i) if (!(n % i)) {for (; !(n % i); n /= i); fac[cnt++] = i;} } int get_primitive_root(int p) { int g, i = 0; factor(p - 1); for (g = 2; i < cnt; ++g) for (i = 0; i < cnt && PowerMod(g, (p - 1) / fac[i]) != 1; ++i); return --g; } } namespace Solver { void matmul(pmat ret, pmat a, pmat b) { int i, j, k; mat tmp = {{0}}; for (i = 0; i < n; ++i) for (k = 0; k < n; ++k) if (a[i][k]) for (j = 0; j < n; ++j) tmp[i][j] = (tmp[i][j] + (ll)a[i][k] * b[k][j]) % mod; for (i = 0; i < n; ++i) memcpy(ret[i], tmp[i], n << 2); } void matPowerMod(pmat a, int n, pmat c) {for (; n; n >>= 1, matmul(a, a, a)) if (n & 1) matmul(c, a, c);} int main(int w) { int i, j; mat tr, res = {{0}}; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) tr[i][j] = (ll)w * G[j][i] % mod; for (i = 0; i < n; ++i) ++tr[i][i], ++res[i][i]; return matPowerMod(tr, L, res), res[y][x]; } } void conv(int n, int *a, int *b, int *ret) { int i, j; if (n < 25) { static u128 Ret[51]; memset(Ret, 0, (n * 2 + 1) << 4); for (i = 0; i <= n; ++i) for (j = 0; j <= n; ++j) Ret[i + j] += (ll)a[i] * b[j]; for (i = 0; i <= n * 2; ++i) ret[i] = Ret[i] % mod; } else { memset(ret, 0, (n * 2 + 1) << 2); int h = n / 2 + 1, u[h], v[h], w[2 * h - 1]; conv(h - 1, a, b, ret); conv(n - h, a + h, b + h, ret + h * 2); for (i = 0; i < h; ++i) u[i] = a[i], v[i] = -b[i]; for (i = 0; i <= n - h; ++i) u[i] -= a[i + h], v[i] += b[i + h]; for (i = 0; i < h; ++i) u[i] += u[i] >> 31 & mod, v[i] += v[i] >> 31 & mod; conv(h - 1, u, v, w); for (i = 2 * (n - h); i >= 0; --i) add(w[i], ret[i + h * 2]); for (i = 2 * (h - 1); i >= 0; --i) add(ret[i + h], w[i]), add(ret[i + h], ret[i]); } } void CZT(int n, int *f, int *g) { int i; for (i = 0; i < n; ++i) u[n - 1 - i] = (ll)w[(n - C(i, n)) % n] * f[i] % mod; for (i = 0; i < n * 2 - 1; ++i) v[i] = w[C(i, n)]; conv(2 * (n - 1), u, v, c); for (i = 0; i < n; ++i) g[i] = (ll)c[n - 1 + i] * w[(n - C(i, n)) % n] % mod; } int main() { int i, j; ll inv_K; scanf("%d%d%d%d%d%d", &n, &K, &L, &x, &y, &mod), --x, --y; g = NT::get_primitive_root(mod), w[1] = PowerMod(g, mod / K); for (*w = 1, i = 2; i < K; ++i) w[i] = (ll)w[i - 1] * w[1] % mod; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) scanf("%d", G[i] + j); for (i = 0; i < K; ++i) res[i] = Solver::main(w[i]); CZT(K, res, ans); std::reverse(ans + 1, ans + K), inv_K = PowerMod(K, mod - 2); for (i = 0; i < K; ++i) printf("%lld\n", inv_K * ans[i] % mod); return 0; }
- 1
信息
- ID
- 2401
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者