救救孩子QAQ
查看原帖
救救孩子QAQ
221551
Bker_楼主2022/8/17 10:31

为什么得到的比正确答案大一QAQ

#include <iostream>
using namespace std;
#define maxn 15
const long long mod = 1000000007 ;
long long t ;
long long b[2][1];

struct P {
    long long g[maxn][maxn] ;
};

P a , ans ;

 inline P mul(P a , P b){
    P ans ;
    for(register int i = 1 ; i <= 2 ; i++)
        for(register int j = 1 ; j <= 2 ; j++)
            ans.g[i][j] = 0 ;
    for(register int i = 1 ; i <= 2 ; i ++)
        for(register int j = 1 ; j <= 2; j++)
            for(register int k = 1 ; k <= 2 ; k++)
                ans.g[i][j] = (ans.g[i][j]) % mod +(a.g[i][k] * b.g[k][j]) % mod ;
    return ans ;
 }

 inline P qpow(P a , long long  x){
     for(int i = 1 ; i <= 2 ; i++)
            ans.g[i][i] = 1 ;
     while(x){
        if(x & 1)   ans = mul(ans , a) ;
        a = mul(a , a) ;
        x >>= 1;
     }
     return ans ;
 }

int main(){
    cin>>t;
    if(1 == t || 2 == t){
        cout<<1 ;
        return 0 ;
    }
    a.g[1][1] = 1 , a.g[1][2] = 1 , a.g[2][1] = 1 , a.g[2][2] = 0 ;
    b[1][1] = b[2][1] = 1 ;
    ans = qpow(a , t - 2) ;
    for(register int i = 1 ; i <= 2 ; i++)
       for(register int j = 1 ; j <= 2 ; j++)
            for(register int k = 1 ; k <= 2 ; k++)
               b[i][j] = (b[i][j]) % mod + (ans.g[i][k] * b[k][j]) % mod;

    cout<<(b[1][1]) % mod<<" ";

    return 0 ;
}

2022/8/17 10:31
加载中...