サブブロック+行列の高速べき乗

2204 ワード

http://acm.hdu.edu.cn/showproblem.php?pid=6395

P/iは同じ部分があるので、ブロックを分けたいです.これもよく使います.
$\begin{bmatrix} F(n)\\ F(n-1) \\ 1 \end{bmatrix}= \begin{bmatrix} d &c & x\\ 1&0 &0 \\ 0& 0 &1 \end{bmatrix}\begin{bmatrix} F2\\ F1\\ 1 \end{bmatrix}$

#include
#include 
#include 
#include 
#include  
#include   
#include   
#include   
#include   
#include    
#include      
#include      
using namespace std;

typedef long long ll;
const int Mod=1e9+7;
int A,B,C,D,n,P;

struct Mat
{
    int t[3][3];
    
    Mat(){memset(t,0,sizeof t);}
}I;

Mat operator * (Mat a,Mat b)
{
    Mat c;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        {
            ll t=0;
            for(int k=0;k<3;k++)
                t+=(ll)a.t[i][k]*b.t[k][j];
            c.t[i][j]=t%Mod;
        }
    return c;
}

Mat Pow(Mat a,int b)
{
    Mat c=I;
    while(b)
    {
        if(b&1)
            c=c*a;
        a=a*a;b>>=1;
    }
    return c;
}

void solve()
{
    scanf("%d%d%d%d%d%d",&A,&B,&C,&D,&P,&n);
    if(n==1)
    {
        cout<>t;
while(t-)
ソロ  
return 0;
)

buffloの最適な実践

ZOJ 1516 Ucle Tom's Inherited Land(2点マッチ最大マッチハンガリーですね)