oj.uz

Submission #411956

# Submission time Handle Problem Language Result Execution time Memory
411956 2021-05-26T10:50:58 Z 반딧불(#7584) Semafor (COI20_semafor) C++17
21 / 100
 2 ms 332 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;

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

    Matrix powered = matPow(newMat, k);
    Matrix atFirst = Matrix(1, 6);
    atFirst.mat[0] = vector<ll> {1, 0, 0, 0, 0, 0};

    Matrix result = atFirst * powered;
    Matrix ret = Matrix(10, 10);
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            int dist = __builtin_popcount(state[i] ^ state[j]);
            ret.mat[i][j] = result.mat[0][dist] * mpow(comb[dist], 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<10; i++) printf("%lld\n", ans.mat[x][i]);
}

Compilation message

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 292 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 292 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -