牛客练习赛68d

D展开全文即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>  pll;
#define fi first
#define se second
#define pk push_back
#define mk make_pair

const ll N=5e2+10, mod=998244353, inf=0x3f3f3f3f3f3f3f3f;

ll peo[N], prof[N], pro[N], tmp[N], ans[N], a, b, c, n, k;

ll qmi(ll a,ll b,ll m=mod){
    ll res=1;
    while(b){
        if(b&1) res=res*a%m;
        b>>=1, a=a*a%m;
    }
    return res;
}

void mul(ll a[], ll b[],ll res[]){
    for(ll i=0;i<n;i++) res[i]=0;
    for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
            res[(i+j)%n]+=a[i]*b[j]%mod, res[(i+j)%n]%=mod;
    return ;
}

void atob(ll a[], ll b[]) {
    for(ll i=0;i<n;i++)
        b[i]=a[i];
}
void work(){
    cin>>n>>k;
    cin>>a>>b>>c;
    for(ll i=0;i<n;i++) scanf("%lld",&peo[i]);
    ll s=a+b+c, p1=a*qmi(s,mod-2)%mod, p2=b*qmi(s,mod-2)%mod, p3=c*qmi(s,mod-2)%mod;
    prof[0]=p3, prof[1]=p1, prof[n-1]=p2; pro[0]=1;
    while(k){
        if(k&1) mul(pro,prof,tmp), atob(tmp, pro);
        mul(prof,prof,tmp), atob(tmp, prof);puts("");
        k>>=1;
    }
    for(ll i=0;i<n;i++)
        for(ll j=0;j<n;j++)
            ans[(i+j)%n]+=peo[i]*pro[j]%mod, ans[(i+j)%n]%=mod;
    for(ll i=0;i<n;i++)
        printf("%lld ",ans[i]);

    return ;
}
int main() {
//    ll t;
//    for(cin>>t;t--;)
        work();
    return 0;
}

点个赞吧，谢谢对本博客的支持，进入博客可以看系列