C++14(g++5.4) 解法, 执行用时: 319ms, 内存消耗: 504K, 提交时间: 2020-08-29 01:20:31

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int Mod = 998244353;
const int MAXN = 5e2 + 5;
int E[MAXN], t[MAXN], ret[MAXN], F[MAXN]; 
int n, a, b, c;
using LL = long long;
LL k;
LL mpow(LL x, LL b) {
	LL r = 1;
	for (; b; b >>= 1, x = x * x % Mod) 
		if (b & 1) r = r * x % Mod;
	return r;
} 
void mul(int *A, int *B) {
	memset(t, 0, sizeof(t));
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			t[i] = (t[i] + (long long)A[j] * B[(n + i - j) % n] % Mod) % Mod;
	for (int i = 0; i < n; i++) 
		A[i] = t[i];
}
signed main() {
	cin >> n >> k >> a >> b >> c;
	
	for (int i = 0; i < n; i++) scanf("%lld", F + i);
	LL s = a + b + c;
	LL p1 = a * mpow(s, Mod - 2) % Mod;
	LL p2 = b * mpow(s, Mod - 2) % Mod;
	LL p3 = c * mpow(s, Mod - 2) % Mod;
	E[n - 1] = p2, E[0] = p3, E[1] = p1;
	ret[0] = 1;
	for (; k; k >>= 1, mul(E, E)) 
		if (k & 1) mul(ret, E);
	mul(F, ret);
	for (int i = 0; i < n; i++) 
		printf("%lld%c", F[i], " \n"[i == n - 1]);
	return 0;
}
/*
https://www.cnblogs.com/Saurus/p/6127478.html
*/

/*
5 10000000000
1 1 2
34 2 23424 4 156
*/

C++ 解法, 执行用时: 424ms, 内存消耗: 536K, 提交时间: 2022-01-18 16:29:29

#include<bits/stdc++.h>
using namespace std;

long long a[510],b[510],mod=998244353;
long long n,K,aa,bb,cc,s;
long long ny;

void mul(long long c[],long long a[],long long b[]){
    long long temp[510]={0};
    for(int i=1;i<=n;i++){
        for(int k=1;k<=n;k++){
            temp[(i+k-2)%n+1]=(temp[(i+k-2)%n+1]+a[i]*b[k])%mod;
        }
    }
    memcpy(c,temp,sizeof temp);
}

void getny(){
    long long res=1,ds=s,p=mod-2;
    while(p){
        if(p&1) res=res*ds%mod;
        ds=ds*ds%mod;
        p>>=1;
    }
    ny=res;
}

int main(){
    cin>>n>>K;
    cin>>aa>>bb>>cc;
    s=aa+bb+cc;
    for(int i=1;i<=n;i++) cin>>a[i];
    getny();
    b[1]=cc*ny%mod,b[2]=aa*ny%mod,b[n]=bb*ny%mod;
    while(K){
        if(K&1) mul(a,a,b);
        mul(b,b,b);
        K>>=1;
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}