D

题解

初始人数分布可以看作初始状态，有一定概率转移到别的位置，视为状态转移，因此矩阵快速幂可以解决。但是直接使用矩阵快速幂的时间复杂度为，超时。需要改进矩阵乘法，观察到状态转移矩阵是一个循环矩阵，循环矩阵与循环矩阵相乘仍然为循环矩阵，因此，只需要保存矩阵的第一行，两个矩阵相乘时，通过两个矩阵第一行的元素，可以求得结果矩阵的第一行元素，即结果矩阵可得。时间复杂度.

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f

const ll mod=998244353;
ll n,k;
ll a,b,c,s;
vector<ll> trans,state0;
ll pow_mod(ll a, ll x, ll p)
{
    ll ret = 1;
    while (x)
    {
        if (x & 1)  ret = ret * a % p;
        a = a * a % p;
        x >>= 1;
    }
    return ret;
}

vector<ll> mul(vector<ll> &a,vector<ll> &b)
{
    vector<ll> res(n);
    for(int i=0;i<n;++i)
    {
        ll now=0;
        for(int j=0;j<n;++j)
            now=(now+a[(i+n-j)%n]*b[j]%mod)%mod;
        res[i]=now;
    }
    return res;
}

int main(void)
{
    cin>>n>>k>>a>>b>>c;
    s=a+b+c;
    ll inverses=pow_mod(s,mod-2,mod);
    ll p1=a*inverses%mod;
    ll p2=b*inverses%mod;
    ll p3=c*inverses%mod;
    state0.resize(n);
    trans.resize(n,0);
    for(int i=0;i<n;++i)
        cin>>state0[i];
    trans[0]=p3,trans[1]=p1,trans[n-1]=p2;
    vector<ll> tmp(n,0);
    tmp[0]=1;
    while(k)
    {
        if(1&k) tmp=mul(tmp,trans);
        trans=mul(trans,trans);
        k>>=1;
    }
    vector<ll> ans=mul(state0,tmp);
    for(auto x:ans)
        cout<<x<<" ";
    cout<<endl;
    return 0;
}