1 条题解

  • 0
    @ 2026-1-16 23:08:31

    #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
    上传者