oj.uz

Submission #411914

# Submission time Handle Problem Language Result Execution time Memory
411914 2021-05-26T08:47:59 Z 조영욱(#7630) Semafor (COI20_semafor) C++17
0 / 100
 4 ms 756 KB 
#include <bits/stdc++.h>
using namespace std;

long long n,k;
int m,x;
int bit[10]={10,2,9,7,18,21,12,3,29,23};
long long dp[1501][1024];
const int mod=1e9+7;
int sbit,sbit1;

struct Matrix {
    long long arr[32][32];
};

Matrix multi(Matrix a,Matrix b) {
    Matrix ret;
    memset(ret.arr,0,sizeof(ret.arr));
    for(int i=0;i<32;i++) {
        for(int j=0;j<32;j++) {
            for(int l=0;l<32;l++) {
                ret.arr[i][j]+=a.arr[i][l]*b.arr[l][j];
                ret.arr[i][j]%=mod;
            }
        }
    }
    return ret;
}

Matrix fastpow(Matrix a,long long b) {
    if (b==1) {
        return a;
    }
    if (b%2==1) {
        return multi(fastpow(a,b-1),a);
    }
    Matrix half=fastpow(a,b/2);
    return multi(half,half);
}

int main(void) {
    scanf("%d %lld %lld %d",&m,&n,&k,&x);
    sbit=bit[x/10];
    sbit1=bit[x%10];
    Matrix mat;
    memset(mat.arr,0,sizeof(mat.arr));
    for(int i=0;i<32;i++) {
        for(int bit=0;bit<5;bit++) {
            mat.arr[i][i^(1<<bit)]=1;
        }
    }
    Matrix base0=fastpow(mat,k);
    Matrix base;
    memset(base.arr,0,sizeof(base.arr));
    for(int i=0;i<32;i++) {
        bool flag=false;
        for(int ii=0;ii<10;ii++) {
            if (bit[ii]==i) {
                flag=true;
            }
        }
        if (!flag) {
            continue;
        }
        for(int j=0;j<32;j++) {
            bool flag=false;
            for(int ii=0;ii<10;ii++) {
                if (bit[ii]==j) {
                    flag=true;
                }
            }
            if (!flag) {
                continue;
            }
            base.arr[i][j]=base0.arr[i][j];
        }
    }
    Matrix ret;
    if (n<k) {
        ret=fastpow(mat,n);
    }
    else {
        ret=fastpow(base,n/k);
        if (n%k!=0)
            ret=multi(ret,fastpow(mat,n%k));
    }
    for(int i=0;i<10;i++) {
        for(int j=0;j<10;j++) {
            printf("%lld\n",(ret.arr[sbit][bit[i]]*ret.arr[sbit1][bit[j]])%mod);
        }
    }
}

Compilation message

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -