Codeforces Contest 1151 F Sonya and Informatics —— 矩陣快速幂

This way

題意：

給你一串值包含1和0的數字，現在有一種操作：等機率的交換這個數組中任意兩個位置的數，這兩個位置不重複，問你經過k次這種操作之後這串數是非遞減的機率是多少。

題解：

他這個k很大有1e9，是以肯定不是普通的dp，但是可以用dp方程寫出來：假設我們開的下k這個數，假設總共有sumz個0，那我們用dp[i][j]表示到第i步的時候前面sumz個數中有j個0，那麼dp方程就是dp[i][j]=dp[i-1][j-1]*(?)+dp[i-1][j]*(?)+dp[i-1][j+1]*(?)這種形式。但是開不下，而且我們又把方程寫出來了，是以剩下一種可能就是矩陣快速幂。按照剛才的思路，前面sumz個位置中有j個0可以從j-1，j，j+1個0轉移過來，那麼就可以得出以下矩陣：

首先我們是枚舉0的個數，設它為i，那麼0在numz之前的有i個，0在numz之後的有numz-i個，

1在numz之前的有numz-i個，1在numz之後的有n-numz-numz-i個。

那麼+1的情況就是(numz-i)*(numz-i)

-1的情況就是i*(n-2*numz+i)

不增不減就是剩下的數。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=101;
const ll mod=1e9+7;
struct Matrix
{
    ll m[N][N];
    Matrix()
    {
        memset(m,0,sizeof(m));
    }
    Matrix  operator *(const Matrix &b)const
    {
        Matrix c;
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                for(int k=0; k<N; k++)
                {
                    c.m[i][j]=(c.m[i][j]+(m[i][k]*b.m[k][j])%mod)%mod;
                }
            }
        }
        return c;
    }
}m;
int a[N];
ll qpow(ll a,ll b)
{
    ll ans=1,ret=a;
    while(b)
    {
        if(b&1)
            ans=ans*ret%mod;
        ret=ret*ret%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    int n,k,numz=0,atz=0;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),numz+=a[i]==0;
    for(int i=1;i<=numz;i++)
        atz+=a[i]==0;
    Matrix ans;
    ans.m[0][atz]=1;
    for(int i=0;i<=numz;i++)
    {
        ll add=(numz-i)*(numz-i);
        ll dec=i*(n-2*numz+i);
        m.m[i][i]=(n-1)*n/2-add-dec;
        if(i)
            m.m[i][i-1]=dec;
        if(i<numz)
            m.m[i][i+1]=add;
    }
    ll inv=qpow(qpow((n-1)*n/2,k),mod-2);
    while(k)
    {
        if(k&1)
            ans=ans*m;
        m=m*m;
        k>>=1;
    }
    return 0*printf("%lld\n",ans.m[0][numz]*inv%mod);
}