oj.uz

Submission #593165

# Submission time Handle Problem Language Result Execution time Memory
593165 2022-07-10T14:06:38 Z jiahng Semafor (COI20_semafor) C++14
0 / 100
 101 ms 920 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,ll> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200100
#define INF (ll)1e14
#define MOD 1000000007
#define getchar_unlocked _getchar_nolock


int M,N,K,X;
int numbers[10] = {0b01010, 0b01000, 0b10010,0b11100,0b01001,0b10101,0b00110, 0b11000, 0b10111, 0b11101};
int num[10]; // the number of ways to do K operations and flip x bits

struct Matrix{
    int mat[100][100];
    Matrix(){
        FOR(i,0,99) FOR(j,0,99) mat[i][j] = 0;
    }
    Matrix operator*(Matrix mat2){
        Matrix new_mat = Matrix();
        FOR(i,0,99) FOR(j,0,99) FOR(k,0,99) (new_mat.mat[i][j] += (mat[i][k] * mat2.mat[k][j]) % MOD) %= MOD;
        return new_mat;
    }
    void print(int N){
        FOR(i,0,N-1){
            FOR(j,0,N-1) cout << mat[i][j] << ' ';
            cout << '\n';
        }
    }
};
Matrix qexp(Matrix mat, int b){
    Matrix ans = Matrix();
    FOR(i,0,99) ans.mat[i][i] = 1;
    while (b){
        if (b&1) ans = ans * mat;
        mat = mat * mat;
        b >>= 1;
    }
    return ans;
}
int32_t main(){
    fast;
    cin >> M >> N >> K >> X;
    
    Matrix mat1 = Matrix();
    FOR(i,0,5*M-1){
        if (i > 0) mat1.mat[i][i-1] = i;
        if (i < 5*M-1) mat1.mat[i][i+1] = 5*M-i;
    }
    //mat1.print(5*M);
    //cout << '\n';
    Matrix mat2 = qexp(mat1, K);
    //mat2.print(5*M);
    FOR(i,0,5*M-1) num[i] = mat2.mat[i][0];

    Matrix adj = Matrix();
    FOR(i,0,9) FOR(j,0,9){
        adj.mat[i][j] = num[__builtin_popcount(numbers[i] ^ numbers[j])];
    }
    //adj.print(10);
    adj = qexp(adj, N/K);
    // N%K operations left

    Matrix mat3 = qexp(mat1, N%K);
    FOR(i,0,9){ //final state
        int ans = 0;
        FOR(j,0,9){
            int numdiff = __builtin_popcount(numbers[j] ^ numbers[i]);
            (ans += (mat3.mat[numdiff][0] * adj.mat[X][j]) % MOD) %= MOD;
        }
        cout << ans << '\n';
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 852 KB Output is correct
2 Correct 34 ms 852 KB Output is correct
3 Correct 46 ms 852 KB Output is correct
4 Incorrect 34 ms 852 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 852 KB Output is correct
2 Correct 34 ms 852 KB Output is correct
3 Correct 46 ms 852 KB Output is correct
4 Incorrect 34 ms 852 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 40.0

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