Submission #71813

#	Time	Username	Problem	Language	Result	Execution time	Memory
71813		chobo (#119)	Cross on the Grid (FXCUP3_cross)	C++17	100 / 100	4 ms	604 KiB

cross

#include <stdio.h>
#include <algorithm>
#define LL long long
#define MOD 1000000007
using namespace std;

struct mat{
    LL x[16][16];

    mat operator*(const mat &p)const{
        mat ret;
        for(int i=0;i<16;i++){
            for(int j=0;j<16;j++){
                ret.x[i][j]=0;
                for(int k=0;k<16;k++) ret.x[i][j]=(ret.x[i][j]+x[i][k]*p.x[k][j])%MOD;
            }
        }
        return ret;
    }
}it;

int dx[]={0,1,0,-1,0};
int dy[]={0,0,1,0,-1};

bool collapse(int a,int b,int y){
    if(!a || !b) return 0;

    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if(a+dx[i]!=b+dx[j]) continue;
            if(dy[i]!=y+dy[j]) continue;
            return 1;
        }
    }

    return 0;
}

mat pw(mat x,int p){
    mat ret=it;

    while(p){
        if(p&1) ret=ret*x;
        x=x*x; p>>=1;
    }

    return ret;
}

int main(){
    int n;

    scanf("%d",&n);

    mat x;
    for(int i=0;i<16;i++){
        for(int j=0;j<16;j++){
            x.x[i][j]=0;
            if(i/4==j%4){
                if(collapse(j/4,i%4,2)) continue;
                if(collapse(j%4,i%4,1)) continue;
                x.x[i][j]=1;
            }
        }
    }

    for(int i=0;i<16;i++) it.x[i][i]=1;
    x=pw(x,n-3);

    int ans=0;
    for(int i=0;i<16;i++){
        for(int j=0;j<4;j++) ans=(ans+x.x[i][j])%MOD;
    }

    printf("%d",ans);

    return 0;
}

Compilation message (stderr)

cross.cpp: In function 'int main()':
cross.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 35 / 35
• Subtask 3: 43 / 43