행렬 연승 모듈

1200 단어
행렬 연승 템플릿 문제를 풀었다.
다시 복습을 했는데...
코드 붙여넣기
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
using namespace std;
struct matrix
{
    int m[3][3];
};
int n,p;
matrix one=
{
    1,0,0,
    0,1,0,
    0,0,1
};
matrix ans=
{
    1,1,0,
    1,0,1,
    1,0,0
};
matrix init=
{
    0,0,0,
    0,0,0,
    0,0,0,
};
matrix mul(matrix a,matrix b)
{
    matrix c=init;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        for(int k=0;k<3;k++)
        c.m[i][j]+=(a.m[i][k]*b.m[k][j])%p;
        c.m[i][j]%=p;
    }
    return c;
}
matrix matrixpow(int kn,matrix a)
{
    matrix c=one;
    while(kn>0)
    {
        if(kn&1)
        {
            c=mul(a,c);
        }
        kn=kn>>1;
        a=mul(a,a);
    }
    return c;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&p);
        matrix k;
        k=matrixpow(n-2,ans);
        int sum=k.m[1][0]+k.m[2][0]+k.m[0][0];
        printf("%d
",(sum)%p); } }

좋은 웹페이지 즐겨찾기