oj.uz

Submission #411960

# Submission time Handle Problem Language Result Execution time Memory
411960 2021-05-26T10:56:56 Z 반딧불(#7584) Semafor (COI20_semafor) C++17
0 / 100
 41 ms 624 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;
const int state[10] = {10, 2, 9, 7, 18, 21, 12, 3, 29, 23};
const ll comb[6] = {1, 5, 10, 10, 5, 1};

ll mpow(ll x, ll y){
    ll ret = 1;
    while(y){
        if(y%2) ret = (ret*x) % MOD;
        x = (x*x) % MOD;
        y/=2;
    }
    return ret;
}

struct Matrix{
    int n, m;
    vector<vector<ll> > mat;
    Matrix(){}
    Matrix(int _n, int _m){
        n = _n, m = _m;
        mat.resize(n);
        for(int i=0; i<n; i++) mat[i].resize(m);
    }
    Matrix(vector<vector<ll> > mat): mat(mat){}

    Matrix operator*(const Matrix &r)const{
        int o = r.m;
        assert(m == r.n);
        Matrix ret(n, o);
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                for(int k=0; k<o; k++){
                    ret.mat[i][k] += mat[i][j] * r.mat[j][k];
                    ret.mat[i][k] %= MOD;
                }
            }
        }
        return ret;
    }
};

Matrix Default(int _n){
    Matrix mat(_n, _n);
    for(int i=0; i<_n; i++) mat.mat[i][i] = 1;
    return mat;
}

Matrix matPow(Matrix mat, ll y){
    assert(mat.n == mat.m);
    Matrix ret = Default(mat.n);
    while(y){
        if(y%2) ret = ret * mat;
        mat = mat * mat;
        y/=2;
    }
    return ret;
}

int m; ll n, k; int x;
Matrix byKMat;
Matrix ans;

int score(int i, int j){
    return i*6+j;
}

Matrix distanceK(ll k){
    Matrix newMat (36, 36);
    for(int i=0; i<=5; i++){
        for(int j=0; j<=5; j++){
            if(i) newMat.mat[score(i, j)][score(i-1, j)] = i;
            if(j) newMat.mat[score(i, j)][score(i, j-1)] = j;
            if(i<5) newMat.mat[score(i, j)][score(i+1, j)] = 5-i;
            if(j<5) newMat.mat[score(i, j)][score(i, j+1)] = 5-i;
        }
    }

    Matrix powered = matPow(newMat, k);
    Matrix atFirst = Matrix(1, 36);
    atFirst.mat[0][0] = 1;

    Matrix result = atFirst * powered;
    Matrix ret = Matrix(100, 100);
    for(int i=0; i<100; i++){
        for(int j=0; j<100; j++){
            int dist1 = __builtin_popcount(state[i/10] ^ state[j/10]);
            int dist2 = __builtin_popcount(state[i%10] ^ state[j%10]);
            ret.mat[i][j] = result.mat[0][score(dist1, dist2)] * mpow(comb[dist1], MOD-2) % MOD * mpow(comb[dist2], MOD-2) % MOD;
        }
    }

    return ret;
}

int main(){
    scanf("%d %lld %lld %d", &m, &n, &k, &x);
    ans = matPow(distanceK(k), n/k) * distanceK(n%k);
    for(int i=0; i<100; i++) printf("%lld\n", ans.mat[x][i]);
}

Compilation message

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

Subtask #1
0 / 6.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 40.0

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