牛客练习赛68 D.牛牛的粉丝

考察循环矩阵快速幂
一些练习题：
http://acm.fzu.edu.cn/problem.php?pid=1692
http://acm.hdu.edu.cn/showproblem.php?pid=2276

参考题解:https://blog.csdn.net/weixin_43785386/article/details/108288417
很详细

分析：每一轮调整对于后的值：
那么转移矩阵为：

注释部分是一般的矩阵快速幂 (会TLE)。当转移矩阵是循环矩阵时，可以用当前板子进行优化加速---

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

const int N=505;
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int maxn=2005;

ll tmp[N][N];
// https://ac.nowcoder.com/acm/contest/7079/D
/*
void multi( ll a[][N],ll b[][N] , int n )
{

    memset(tmp,0,sizeof(tmp));
    for( int i=0;i<n;i++ )
    {
        for( int j=0;j<n;j++ )
        {
            for( int k=0;k<n;k++ )
            {
                tmp[i][j]+=a[i][k]*b[k][j];
                tmp[i][j]%=mod;
            }
        }
    }
    for(int i=0;i<n;i++ )
    {
        for( int j=0;j<n;j++ ) a[i][j]=tmp[i][j];
    }
    // a[i][j] 矩阵相乘得结果矩阵 
}
*/

void multi(ll a[N][N],ll b[N][N],ll n )
{
    ll d[N];
    for(int j=0;j<n;j++)
    {
        d[j]=0;
        for(int k=0;k<n;k++)
            d[j]=(d[j]+(ll)a[0][k]*b[k][j])%mod;
    }
    for( int i=0;i<n;i++ ) a[0][i]=d[i];
    for( int i=1;i<n;i++ )
        for( int j=0;j<n;j++ )
            a[i][j] = j==0 ? a[i-1][n-1] :a[i-1][j-1];
}


ll res[N][N];  // pow 的结果矩阵 

void poww( ll a[][N],ll y ,ll n )
{
    memset(res,0,sizeof(res));
    for( int i=0;i<N;i++ ) res[i][i]=1;
    while( y )
    {
        if( y&1 ) multi(res,a,n);
        multi(a,a,n);
        y>>=1;
    }
}

ll qpow( ll x,ll y )
{
    ll res=1;
    while( y )
    {
        if( y&1 ) res=res*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return res;
}

ll L[505][505],p[505][505];
ll ans[505];

int main()
{
    int n;ll k;
    scanf("%d%lld",&n,&k);
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);

    ll s=a+b+c;
    s=qpow(s,mod-2);
    ll f1=a*s%mod,f2=b*s%mod,f3=c*s%mod;
    swap(f2,f3);

    // now=f1*pre+f2*now+f3*next
    for( int i=0;i<n;i++ ) scanf("%lld",&L[0][i]);

    for( int i=0,j=n-1;i<n;i++ )
    {
        int k=j;
        p[i][k]=f1;
        k=(k+1)%n;
        p[i][k]=f2;
        k=(k+1)%n;
        p[i][k]=f3;
        j=(j+1)%n;
    }

    poww(p,k,n);

    for( int i=0;i<n;i++ )
    {
        for( int j=0;j<n;j++ )
        {
            ans[i]=( ans[i]+(ll)res[i][j]*L[0][j]%mod )%mod; 
        }
    }

    for( int i=0;i<n;i++ ) printf("%lld ",ans[i]);


}