L. Poor God Water [ ACM-ICPC 2018 焦作赛区网络预赛 ]

[题库链接] https://nanti.jisuanke.com/t/31721

显然是矩阵快速幂的题，暴力枚举了系数，挺悲哀的。得到的4阶系数矩阵对前5项不成立。十分抱歉还没有理解这个转移的道理。

ACcode

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>

#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

typedef long long int LLI;

const int MOD = 1000000007;
const int N = 4;
LLI l,r,t,n;
struct Matrix {
    LLI mat[N][N];
    Matrix operator*(const Matrix& m)const {
        Matrix tmp;
        for(LLI i = 0 ; i < N ; i++) {
            for(LLI j = 0 ; j < N ; j++) {
                tmp.mat[i][j] = 0;
                for(LLI k = 0 ; k < N ; k++)
                    tmp.mat[i][j] = (tmp.mat[i][j] + mat[i][k]*m.mat[k][j])%MOD;
                tmp.mat[i][j] %= MOD;
            }
        }
        return tmp;
    }
};
Matrix m;
void print(Matrix d)
{
    LLI i,j;
    for (i=0;i<4;++i)
    {
        for (j=0;j<4;++j)
            printf("%4lld",d.mat[i][j]);
        printf("\n");
    }
    printf("\n");
}
Matrix tt;
LLI Pow() {
    Matrix ans;
    for (int i=0;i<4;++i) for (int j=0;j<4;++j) tt.mat[i][j]=m.mat[i][j]=0;

    m.mat[0][0]=2;
    m.mat[0][1]=-1;
    m.mat[0][2]=3;
    m.mat[0][3]=2;
    m.mat[1][0]=m.mat[2][1]=m.mat[3][2]=1;

    for (int i=0;i<4;++i)
        for (int j=0;j<4;++j)
        if (i==j) ans.mat[i][j]=1;
        else ans.mat[i][j]=0;

    tt.mat[0][0]=106;
    tt.mat[1][0]=46;
    tt.mat[2][0]=20;
    tt.mat[3][0]=9;

    n-=5;
    while(n) {
        if (n%2) ans = ans*m;
        //print(tt);
        n /= 2;
        m = m*m;
        //print(m);
    }

    ans=ans*tt;
    //print(ans);
    return ans.mat[0][0]%MOD;
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
            scanf("%lld",&n);
        for (LLI i=0; i<4; ++i) m.mat[0][i]=0;

        if (n==1) printf("3\n");
        else if (n==2) printf("9\n");
        else if (n==3) printf("20\n");
        else if (n==4) printf("46\n");
        else if (n==5) printf("106\n");
        else printf("%lld\n",Pow());
    }
    return 0;
}

打表：

#include <bits/stdc++.h>
#define rep(i,s,t) for (int i=s;i<t;++i)
using namespace std;
int a[17];
int s,t;
void check(int l)
{
    for (int i=1; i<l-1; ++i)
        if (a[i]==a[i-1]&&a[i]==a[i+1]) return;
        else if (a[i]==0)
        {
            if (a[i-1]+a[i+1]==3) return;
        }
        else
        {
            if (a[i-1]+a[i+1]==0) return;
        }
    s++;
}
void output(int l) {
    for (int i=0;i<l;++i) printf("%d ",a[i]);
    printf("\n");
}
void dfs(int len)
{

    while (true)
    {
        check(len);
        //output(len);
        int pos=len-1;
        if (a[pos]==2)
        {
            while (a[pos]==2&&pos>=0) pos--;
            if (pos<0) break;
            else
            {
                a[pos]++;
                rep(i,pos+1,len) a[i]=0;
            }
        }
        else
        {
            a[pos]++;
        }
    }
}
int main()
{
    rep(i,5,16)
    {
        memset(a,0,sizeof(a));
        s=0;
        dfs(i);
        printf("%d %d\n",i,s);
    }


    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int i,j,k,l;
int main()
{
    for (i=-20; i<20; ++i)
        for (j=-20; j<20; ++j)
            for (k=-20; k<20; ++k)
                for (l=-20;l<20;++l)
            {
                if (i*82416+j*35866+k*15610+l*6794==189384) {
                        printf("%d %d %d %d %d\n",i,j,k,l,i*189384+j*82416+k*35866+l*15610);
                }
            }

    return 0;
}