【BZOJ3240】[NOI2013]矩陣遊戲

題目連結

題目描述

求一個矩陣的第n行m列

遞推式

F[1][1]=1F[i,j]=a∗F[i][j−1]+b(j!=1)F[i,1]=c∗F[i−1][m]+d(i!=1) F [ 1 ] [ 1 ] = 1 F [ i , j ] = a ∗ F [ i ] [ j − 1 ] + b ( j ! = 1 ) F [ i , 1 ] = c ∗ F [ i − 1 ] [ m ] + d ( i ! = 1 )

對10^9+7 取模

n m巨大 10^1000000

Sol

先把轉移到行尾的矩陣給他幂出來

然後乘上一個到下一行的轉移矩陣,在幂個n-1次,然後在乘上轉移到行尾的矩陣

這題就秒了

然而資料比較惡心

O(數的長度)轉二進制? 不存在的

聽說可以強行手動推式子用歐拉定理降幂?

推了一大堆後放棄(菜 TAT)

居然可以直接歐拉定理降次數後遞推?

遞推次數也能取模?(Orz)

于是就一臉懵逼地過了

原理?大概是因為最後的式子也是很多個幂相加的形式,是以就可以取模?(霧)

注意歐拉定理要求互質,是以當a或c等于1的話不能 modϕ(p) m o d ϕ ( p ) 而要直接 modp m o d p ,因為此時是線性相加的東西,這個取模的正确性還比較顯然…

代碼:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstdlib>
#include<set>
#define Set(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod=+;
struct matrix{
    int a[][];
    inline void clear(){Set(a,);return;}
    inline int* operator [](int x){return a[x];}
    inline matrix operator *(matrix b){
        matrix c;c.clear();
        for(register int k=;k<;++k)
            for(register int i=;i<;++i)
                for(register int j=;j<;++j)
                    c[i][j]=(c[i][j]+l*a[i][k]*b[k][j]%mod)%mod;
        return c;
    }
}S,T1,T2;
const int N=+;
char sn[N],sm[N];
int ln,lm;
int n,m;
int a,b,c,d;
inline matrix matrix_POW(matrix A,ll k)
{
    if(k==) return A;
    matrix c;c.clear();
    c[][]=c[][]=;
    while(k>){
        if(k&) c=c*A;
        A=A*A;
        k>>=;
    }
    return c;
}
inline void Turn(char s[],int len,int &to,int MO)
{
    to=;
    for(register int i=;i<=len;++i) to=(l*to*+s[i]-'0')%MO;
}
int main()
{
    scanf("%s",sn+);scanf("%s",sm+);
    ln=strlen(sn+);lm=strlen(sm+);
    scanf("%d %d %d %d",&a,&b,&c,&d);
    if(a==) Turn(sn,ln,n,mod);else Turn(sn,ln,n,mod-);
    if(c==) Turn(sm,lm,m,mod);else Turn(sm,lm,m,mod-);
    T1[][]=a;T1[][]=b;T1[][]=;
    T2[][]=c;T2[][]=d;T2[][]=;
    S[][]=;S[][]=;
    T1=matrix_POW(T1,m-);
    T2=T1*T2;T2=matrix_POW(T2,n-);
    S=(S*T2)*T1;
    printf("%d\n",S[][]);
}