求助 如题 代码完全相同,用c++11(clang)就能过,用c++14(g++5.4) 就是答案错误。
#include<bits/stdc++.h> using namespace std; #define ll long long const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const int N = 5e5 + 10; const ll mod = 998244353; struct Mat { int a[510][510]; int r, c; Mat(int _r, int _c) { r = _r, c = _c, memset(a, 0, sizeof(a)); } }; Mat operator * (Mat X, Mat Y) { Mat Z(X.r, Y.c); for (int i = 0; i < X.r; ++i) { for (int j = 0; j < Y.c; ++j) { for (int k = 0; k < X.c; ++k) { Z.a[i][j] = (Z.a[i][j] + 1ll * X.a[i][k] * Y.a[k][j] % mod) % mod; } } } return Z; } Mat mul(Mat X, Mat Y) { Mat Z(X.r, Y.c); for (int j = 0; j < Y.c; ++j) { for (int k = 0; k < X.c; ++k) { Z.a[0][j] = (Z.a[0][j] + 1ll * X.a[0][k] * Y.a[k][j] % mod) % mod; } } for (int i = 1; i < X.r; ++i) { for (int j = 0; j < Y.c; ++j) { Z.a[i][j] = Z.a[i - 1][(j - 1 + Y.c) % Y.c]; } } return Z; } Mat pow(Mat a, ll n) { Mat res(a.r, a.c); for (int i = 0; i < a.r; i++) res.a[i][i] = 1; while (n) { if (n & 1) res = mul(res, a); a = mul(a, a); n >>= 1; } return res; } int n; ll k; ll Pow(ll a, ll b) { ll res = 1ll; while (b) { if (b & 1)res = res * a%mod; a = a * a%mod; b >>= 1; } return res; } ll a, b, c, s; ll p1, p2, p3; int x[510]; ll ans[510]; int main() { scanf("%d%lld", &n, &k); scanf("%lld%lld%lld", &a, &b, &c); for (int i = 0; i < n; i++)scanf("%d", &x[i]); s = a + b + c; ll invs = Pow(s, mod - 2); p1 = a * invs%mod; p2 = b * invs%mod; p3 = c * invs%mod; Mat A(n, n); Mat f(n, 1); f.a[0][0] = 1; for (int i = 0; i < n; i++) { A.a[i][i] = p3; A.a[i][(i - 1 + n) % n] = p1; A.a[i][(i + 1) % n] = p2; } A = pow(A, k); f = A * f; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ans[(i + j) % n] = (ans[(i + j) % n] + f.a[j][0] * x[i] % mod) % mod; } } for (int i = 0; i < n; i++)printf("%lld%c", ans[i], " \n"[i == n - 1]); return 0; }
全部评论
(1) 回帖