ACM-マトリックス特集

前に行列のまとめを書いたことがあるが、その時はテーマが少なかった.クリックしてリンクを開く
今回はテーマを書いて、まとめを書いてリンクを開く
水の問題:
A.典型的なフィボナッチの繰返し構造
B.マトリクス構造とは、列ごとにプッシュすることである
C.水題
G.水題
結合/テクニックの問題:
C=A*B C^Nを計算する場合があります.この場合、A*Bの範囲が広いかもしれません.A*(B*A)^(N-1)*Bでいいです
E結合
H   S(N)=A+A^2+A^3+A^4+.....+A^Nの2つの方法は、Nが偶数S(N)=(A+A^2+…+A^(N/2)(E+A^(N/2))、奇数S(N)=(A+A^2+…+A^(N/2)+A^N、
もう一つは構造行列［S(N),An］である.
法則を探す:
1.a+bが知る、abはa^n+b^nを求める.f(n)=a^n+b^nとする.
f(n+1)=f(n)*(a+b)=a^(n+1)+b^(n+1)+ab(a^(n-1)+b^(n-1))
=(a+b)f(n)-abf(n-1)
2.Lという問題の法則は、時計を打って探しましょう.
3.M ceil((a+√b)^n)%mの結果を求める.タイトルで与えられたbの範囲を用いてceil((a+√b)^n+(a-√b)^n)%mと書くことができ,a^n+b^nと1と同じであることが分かった.
4.R F[0]=aF[1]=bF[n]=F[n]=F[n-1]*F[n-2](n>1)Fnを求め、この分割で発見
f(n)は、フィボナッチ数列のn番目の項F(n)=a^f(n-1)*b^f(n)である
そしてフェルマ小定理a^f(n-1)=a^(f(n-1)%1億006)(mod 100000007)b^f(n)=b^(f(n)%1億006)(mod 100000007)の2つの直接高速べき乗でよい
f(n)%1 0000000006これはマトリックスの高速べき乗で求めることができます
5.(f[1]+f[2]+...+f[n])=f[n+2]-1 
各行と各列の値が異なるようにマトリクスを構築する.行列の上三角はすべて"1"行列の下三角はすべて"-1"対角線"1","0"が交互である.n=4のように、対応行列は、1 1 1 1 1 1 1 0-1 1 1-1 0-1-1-1
マトリックステンプレート:

#include
#include
#include
#include
#include
using namespace std;
int MOD = 1000000007;
#define MaxSize 5
typedef long long type;
typedef long long LL;
LL n,k;
struct Mat{
    type arr[MaxSize][MaxSize];
    int r,l;
    Mat(int r=0,int l=0){
        this->r=r;
        this->l=l;
        memset(arr,0,sizeof(arr));
    }
    Mat operator * (const Mat &x){
        Mat ret(r,x.l);
        for(int i = 0;i0){
        if(n&1)
            ret = ret*basic;
        basic = basic*basic;
        n>>=1;
    }return ret;
}
LL solve(LL nn){
    LL ret;
    if(nn==1)
        return 1;
    Mat e(2,2);
    e.arr[0][0]=e.arr[0][1]=e.arr[1][0]=1;
    e = pow_mat(nn/2,e);
    ret = e.arr[0][0] * (LL)pow(nn/2,k) +1;
    ret = ret * solve(nn/2)%MOD;
    if(nn&1)
        ret = ret*(pow_mat(nn,e).arr[0][0])%MOD;
    return ret;
}
int main(){
    int cas=1;
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%I64d%d",&n,&MOD);
        printf("Case %d: ",cas++);
        Mat e(2,2);
        e.arr[0][0]=e.arr[0][1]=e.arr[1][0]=1;
        e = pow_mat(n,e);
        int ans = (e.arr[0][0] + e.arr[1][0]-1+MOD)%MOD;
        if(ans==0){
            puts("No");
            continue;
        }puts("Yes");
        for(int i = 0;i