[Niuke practice match 68] fans of Niuniu (matrix fast power cycle matrix optimization)

Topic link
Retention pit , Write tomorrow .

The question ：

There is one $n$ A ring of dots , Each point has an initial weight $x_i$.

The description that defines each round of adjustment is ： For the weight of each point on the ring , Yes $p_1$ The probability flows to the next point in a clockwise direction , Yes $p_2$ The probability flows to the next point counterclockwise , Yes $p_3$ The probability of stopping in place .（ among $p_1+p_2+p_3=1$）

ask $k$ After wheel adjustment , The expected weight of each point , The answer is based on the model 998244353.
（$3\le n\le 500,0\le k\le 10^{18}$）

Ideas ：

First, you can give the value of each point after a round of adjustment $X_i=p_1{x}_{i-1}+p_3{x}_i+p_2{x}_{i+1}$.

You can easily get the equation of solving the vector transfer once ：
$$\left[\begin{array}{ccccc}{p}_3& p_2& 0& 0& p_1\\ p_1& p_3& p_2& 0& 0\\ 0& p_1& p_3& p_2& 0\\ 0& 0& p_1& p_3& p_2\\ p_2& 0& 0& p_1& p_3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right]=\left[\begin{array}{c}{X}_1\\ X_2\\ X_3\\ X_4\\ X_5\end{array}\right]$$

So our answer is ：
$$\left[\begin{array}{c}{X}_1\\ X_2\\ X_3\\ X_4\\ X_5\end{array}\right]={\left[\begin{array}{ccccc}{p}_3& p_2& 0& 0& p_1\\ p_1& p_3& p_2& 0& 0\\ 0& p_1& p_3& p_2& 0\\ 0& 0& p_1& p_3& p_2\\ p_2& 0& 0& p_1& p_3\end{array}\right]}^k\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right]$$
Now? , It becomes a matrix fast power board problem , however $500\ast 500\ast 500\ast log10^{18}\approx 8e9$, time limit 1$s$ I can't go through it .

Then we should consider optimization .
And then it's up , And something like a cyclic matrix . For the fast power of a cyclic matrix , It can be optimized to $o(n^{2}logk)$ Of .

Cheese ：

Circulant matrix ：

When each row of a matrix is shifted to the right by one column from the previous row （ Move the last column to the first column ） obtain , We call such a matrix Circulant matrix .

nature ：

$FollowRingMomentfront+FollowRingMomentfront=FollowRingMomentfront$
$FollowRingMomentfront\times FollowRingMomentfront=FollowRingMomentfront$

purpose ：

One 、 According to the definition and properties of cyclic matrix , We're going to store a cyclic matrix , Just save the first line , The following line can be obtained from the first line .
Two 、 We To calculate a cyclic matrix , Just figure out the first line Just what it is , alike , The following lines can be obtained from the first line .
3、 ... and 、 The cyclic matrix is still a cyclic matrix through linear operation , So let's think The complexity of cyclic matrix multiplied by cyclic matrix , Because we just need to count the first line , therefore Matrix multiplication from the original $o(n^3)$ Turned into $o(n^2)$.

then , We find that the matrix of this problem is a cyclic matrix , So it can be optimized to $o(n^{2}logk)$ 了 .

Code ：

Retention pit , Knock again tomorrow

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;

ll fpow(ll a,ll n)
{
    
    ll sum=1,base=a;
    while(n!=0)
    {
    
        if(n%2)sum=sum*base%mod;
        base=base*base%mod;
        n/=2;
    }
    return sum;
}
ll inv(ll a)
{
    
    return fpow(a,mod-2);
}

struct Cmatrix
{
    
    ll mat[505];
}A;
ll len;
Cmatrix mul(Cmatrix A,Cmatrix B)
{
    
    Cmatrix tmp;
    for(ll i=0;i<len;i++)
    {
    
        tmp.mat[i]=0;
        for(int j=0;j<len;j++)
        {
    
            tmp.mat[i]=(tmp.mat[i]+A.mat[j]*B.mat[(len-j+i)%len])%mod;
        }
    }
    return tmp;
}
Cmatrix ffpow(Cmatrix A,ll n)
{
    
    Cmatrix sum;
    for(ll i=0;i<len;i++)sum.mat[i]=0;
    sum.mat[0]=1;
    while(n!=0)
    {
    
        if(n%2)sum=mul(sum,A);
        A=mul(A,A);
        n/=2;
    }
    return sum;
}

ll x[505],X[505];
int main()
{
    
    ll n,k;
    scanf("%lld%lld",&n,&k);
    len=n;
    ll a,b,c;
    scanf("%lld%lld%lld",&a,&b,&c);
    ll p1=a*inv(a+b+c)%mod;
    ll p2=b*inv(a+b+c)%mod;
    ll p3=c*inv(a+b+c)%mod;
    A.mat[0]=p3;A.mat[len-1]=p1;A.mat[1]=p2;
    A=ffpow(A,k);
    for(ll i=0;i<len;i++)scanf("%lld",&x[i]);
    for(ll i=0;i<len;i++)
    {
    
        X[i]=0;
        for(ll j=0;j<len;j++)
        {
    
            X[i]=(X[i]+x[j]*A.mat[(len-i+j)%len])%mod;
        }
    }
    for(ll i=0;i<len;i++)printf("%lld ",X[i]);
    putchar('\n');
    return 0;
}