Submission #381540

#	Time	Username	Problem	Language	Result	Execution time	Memory
381540		VEGAnn	Semafor (COI20_semafor)	C++14	21 / 100	17 ms	492 KiB

semafor

#include <bits/stdc++.h>
#define i2 array<int,2>
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int PW = 5;
const int M = (1 << PW);
const int md = int(1e9) + 7;
int digs[10];
bool mrk[M];
ll m, n, k, x;

struct matrix{
    int a[M][M];
};

matrix base, base_k, base_nw;

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

int mult(int x, int y) { return (1ll * x * y) % md; }

matrix mat_mult(matrix a, matrix b){
    matrix res;

    for (int i = 0; i < M; i++)
    for (int j = 0; j < M; j++) {
        int nw = 0;

        for (int k = 0; k < M; k++)
            nw = sum(nw, mult(a.a[i][k], b.a[k][j]));

        res.a[i][j] = nw;
    }

    return res;
}

matrix binpow(matrix a, ll po){
    matrix res;
    bool was = 0;

    while (po > 0){
        if (po & 1){
            if (!was)
                res = a;
            else res = mat_mult(res, a);

            was = 1;
        }

        a = mat_mult(a, a);
        po >>= 1;
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> m >> n >> k >> x;

    assert(m == 1);

    digs[1] = 8;
    digs[2] = 18;
    digs[3] = 28;
    digs[4] = 9;
    digs[5] = 21;
    digs[6] = 6;
    digs[7] = 24;
    digs[8] = 23;
    digs[9] = 29;
    digs[0] = 10;

    for (int i = 0; i < 10; i++)
        mrk[digs[i]] = 1;

    for (int i = 0; i < M; i++){
        for (int j = 0; j < PW; j++)
            base.a[i][(i ^ (1 << j))] = 1;
    }

    base_k = binpow(base, k);

    /// in base_k you need transitions only between digits

    for (int i = 0; i < M; i++)
    for (int j = 0; j < M; j++)
        if (!mrk[i] || !mrk[j])
            base_k.a[i][j] = 0;

    base_k = binpow(base_k, n / k);

    if (n % k > 0){
        /// calc one more matirix pls

        base_nw = binpow(base, n % k);

        for (int i = 0; i < M; i++)
        for (int j = 0; j < M; j++)
            if (!mrk[i] || !mrk[j])
                base_nw.a[i][j] = 0;

        base_k = mat_mult(base_k, base_nw);
    }

    for (int i = 0; i < 10; i++)
        cout << base_k.a[digs[x]][digs[i]] << '\n';

    return 0;
}

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