各種フィボナッチ行列乗算高速べき乗

T1
f[1]=1; f[2]=1; f[n]=f[n-1]+f[n-2]; f[n]を求める
n<2^32
構想
暴力は明らかにだめだ.マトリクス乗算というより強い方法が必要になります.
行列[f[n-1],f[n]*A=[f[n],f[n-1]+f[n]]を考慮して行列A[0,1][1,1]を押し出す
行列乗算は結合則を満たすため[f[1],f[2]*A^n-1=[f[n-1],f[n]]
高速べき乗でA^n-1を求める
では、水はコードを貼らないでください.
T2
f[1]=1; f[2]=1; f[n]=f[n-1]+f[n-2]+1; f[n]を求める
構想
行列［f［n−1］,f［n］,1］＊A＝［f［n］,f［n−1］＋f［n］＋1,1］を考慮した.
得られた行列A[0,1,0][1,1,0][0,1,1]
コード#コード#

#include
#include
#include
using namespace std;
const int x=3,mod=9973;
int a[x][x]={{0,1,0},{1,1,0},{0,1,1}},b[x]={1,1,1},c[x][x],n;
void power(int t)
{
    if(t==1) return;
    int d[x][x];
    memset(d,0,sizeof(d));
    for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) d[i][j]=a[i][j];
    memset(c,0,sizeof(c));
    for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++)
    {
        for(int k=0; kfor(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) a[i][j]=c[i][j];
    memset(c,0,sizeof(c));
    power(t/2);
    memset(c,0,sizeof(c));
    if(t%2)
    {
        for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++)
        {
            for(int k=0; kfor(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) a[i][j]=c[i][j];
    }
}
int main()
{
    scanf("%d",&n);
    n--;
    power(n);
    memset(c,0,sizeof(c));
    for(int j=0; j<=x-1; j++) for(int k=0; k<=x-1; k++)
    {
        c[0][j]=(c[0][j]+b[j]*a[k][j])%mod;
    }
    printf("%d",c[0][0]);
}

T3
列f[n]=f[n-2]+f[n-1]+n+1のN番目の項を求める、ここでf[1]=1、f[2]=1である.
構想
実はそれほど悪くない
行列［f［n−1］,f［n］,n＋1,1］＊A＝［f［n］,f［n−1］＋f［n］＋1＋n,n＋1,1］を考慮した.
Aを得る
[0,1,0,0] [1,1,0,0] [0,1,1,0] [0,1,1,1]
コード#コード#

#include
#include
#include
using namespace std;
const int x=4,mod=9973;
int a[x][x]={{0,1,0,0},{1,1,0,0},{0,1,1,0},{0,1,1,1}},b[x]={1,1,3,1},c[x][x],n;
void power(int t)
{
    if(t==1) return;
    int d[x][x];
    memset(d,0,sizeof(d));
    for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) d[i][j]=a[i][j];
    memset(c,0,sizeof(c));
    for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++)
    {
        for(int k=0; kfor(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) a[i][j]=c[i][j];
    memset(c,0,sizeof(c));
    power(t/2);
    memset(c,0,sizeof(c));
    if(t%2)
    {
        for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++)
        {
            for(int k=0; kfor(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) a[i][j]=c[i][j];
    }
}
int main()
{
    scanf("%d",&n);
    n--;
    power(n);
    memset(c,0,sizeof(c));
    for(int j=0; j<=x-1; j++) for(int k=0; k<=x-1; k++)
    {
        c[0][j]=(c[0][j]+b[k]*a[k][j])%mod;
    }
    printf("%d",c[0][0]);
}

T4
ある日、幼稚园児の生徒が数学の勉强をしていると、びっくりして泣き出して、一つの问题もできなかった.これで困ったことに、彼はすぐに最下位の0点になるだろう.彼の期待も高くなく、最も簡単な第1題を作るだけで十分な問題はこのようにして、F(n)=((ルート番号5+1)/2)^(n-1)を定義して、もちろん問題の簡単さを明らかにするために当然小数点数あるいは理不尽数ではありませんて、F(x)はそのため上へ整理する必要があって、もちろんF(n)を求めるのはとても難しいです!だから幼稚園の園長の頭皮は簡単に決めて、F(x)の前のn項和を求めればいいです.
テーマの大意
数列f[n]=f[n-1]+f[n-2],f[1]=f[2]=1の前n項とs[n]の高速求め方
構想
sigma(i=1,i<=n,f[i])をs[n]とする
行列[f[n−1],f[n],s[n−1]*A=[f[n],f[n−1]＋f[n],s[n−1]＋f[n],s[n−1]＋f[n].
Aを得る
[0,1,0] [1,1,1] [0,0,1]

#include
#include
#include
using namespace std;
const int x=3,mod=1000000007;
long long a[x][x]={{0,1,0},{1,1,1},{0,0,1}},b[x]={1,1,1},c[x][x],n;
void power(int t)
{
    if(t<=1) return;
    int d[x][x];
    memset(d,0,sizeof(d));
    for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) d[i][j]=a[i][j];
    memset(c,0,sizeof(c));
    for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++)
    {
        for(int k=0; kfor(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) a[i][j]=c[i][j];
    memset(c,0,sizeof(c));
    power(t/2);
    memset(c,0,sizeof(c));
    if(t%2)
    {
        for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++)
        {
            for(int k=0; kfor(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) a[i][j]=c[i][j];
    }
}
int main()
{
    scanf("%d",&n);
    n--;
    if(!n)
    {
        printf("1");return 0;
    }
    power(n);
    memset(c,0,sizeof(c));
    for(int j=0; j<=x-1; j++) for(int k=0; k<=x-1; k++)
    {
        c[0][j]=(c[0][j]+b[k]*a[k][j])%mod;
    }
    printf("%d",c[0][2]);
}

T5
この日、霧水のLZHさんが試験場で泣いていたとき、そばのYMWはとっくに野菜を切るようにcutが簡単極まりない第1題を落としていた.決して負けないで、彼はAKがあなたのテーマが味噌紫であることを見ることができて、f(n)-f(3)-f(4)-f(5)-f(n-3)-f(n-2)=(n+4)(n-1)/2、f(1)=1、f(2)=1 f(n)の前のn項と
テーマの大意
数列f[n]=f[n-1]+f[n-2]+n+1,f[1]=f[2]=1の前n項とs[n]の高速求め方
構想
[f[n-1],f[n],s[n-1],n+1,1]*A=[f[n],f[n-1]+f[n]+n+1,s[n-1]+f[n],n+1,1]
A= [0,1,0,0,0] [1,1,1,0,0] [0,0,1,0,0] [0,1,0,1,0] [0,1,0,1,1]
コード#コード#

#include
#include
#include
using namespace std;
const int x=5,mod=1000000007;
long long a[x][x]={{0,1,0,0,0},
                   {1,1,1,0,0},
                   {0,0,1,0,0},
                   {0,1,0,1,0},
                   {0,1,0,1,1}},b[x]={1,1,1,3,1},c[x][x],n;
void power(int t)
{
    if(t<=1) return;
    int d[x][x];
    memset(d,0,sizeof(d));
    for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) d[i][j]=a[i][j];
    memset(c,0,sizeof(c));
    for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++)
    {
        for(int k=0; kfor(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) a[i][j]=c[i][j];
    memset(c,0,sizeof(c));
    power(t/2);
    memset(c,0,sizeof(c));
    if(t%2)
    {
        for(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++)
        {
            for(int k=0; kfor(int i=0; i<=x-1; i++) for(int j=0; j<=x-1; j++) a[i][j]=c[i][j];
    }
}
int main()
{
    scanf("%d",&n);
    n--;
    if(!n)
    {
        printf("1");return 0;
    }
    power(n);
    memset(c,0,sizeof(c));
    for(int j=0; j<=x-1; j++) for(int k=0; k<=x-1; k++)
    {
        c[0][j]=(c[0][j]+b[k]*a[k][j])%mod;
    }
    printf("%d",c[0][2]);
}