欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-12 16:00:28
...

[题库链接] 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;
}

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


#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;
}

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

相关标签: 矩阵快速幂