Submission #593197

#	Time	Username	Problem	Language	Result	Execution time	Memory
593197		jiahng	Semafor (COI20_semafor)	C++14	100 / 100	308 ms	1108 KiB

semafor

#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};

struct Matrix{
    int mat[100][100];
    int N;
    Matrix(int _N){
        N = _N;
        FOR(i,0,N-1) FOR(j,0,N-1) mat[i][j] = 0;
    }
    Matrix operator*(Matrix mat2){
        Matrix new_mat = Matrix(N);
        FOR(i,0,N-1) FOR(j,0,N-1) FOR(k,0,N-1) (new_mat.mat[i][j] += (mat[i][k] * mat2.mat[k][j]) % MOD) %= MOD;
        return new_mat;
    }
    void print(){
        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(mat.N);
    FOR(i,0,mat.N-1) ans.mat[i][i] = 1;
    while (b){
        if (b&1) ans = mat * ans;
        mat = mat * mat;
        b >>= 1;
    }
    return ans;
}
int32_t main(){
    fast;
    cin >> M >> N >> K >> X;
    
    Matrix mat1 = Matrix(5*M+1);
    FOR(i,0,5*M){
        if (i > 0) mat1.mat[i][i-1] = i;
        if (i < 5*M) mat1.mat[i][i+1] = 5*M-i;
    }
    //mat1.print(5*M);
    //cout << '\n';
    Matrix mat2 = qexp(mat1, K);
    //mat2.print();
    if (M == 1){    
        Matrix adj = Matrix(10);
        FOR(i,0,9) FOR(j,0,9){
            adj.mat[i][j] = mat2.mat[__builtin_popcount(numbers[i] ^ numbers[j])][0];
        }

        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){ // intermediate state
                int numdiff = __builtin_popcount(numbers[j] ^ numbers[i]);
                (ans += (mat3.mat[numdiff][0] * adj.mat[X][j]) % MOD) %= MOD;
            }
            cout << ans << '\n';
        }
    }else{
        Matrix adj = Matrix(100);
        FOR(i,0,9) FOR(i2,0,9) FOR(j,0,9) FOR(j2,0,9){
            adj.mat[i+10*i2][j+10*j2] = mat2.mat[__builtin_popcount(numbers[i] ^ numbers[j]) + __builtin_popcount(numbers[i2] ^ numbers[j2])][0];
        }
        adj = qexp(adj, N / K);

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

• Subtask 1: 6 / 6
• Subtask 2: 15 / 15
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40