Submission #381592

#	Time	Username	Problem	Language	Result	Execution time	Memory
381592		VEGAnn	Semafor (COI20_semafor)	C++14	21 / 100	46 ms	760 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 N = 100;
const int SN = 11;
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;
}

struct matrix_sml{
    int a[SN][SN];
};

struct matrix_big{
    int a[N][N];
};

int cnt_ways[SN];

matrix_sml mat_mult_sml(matrix_sml a, matrix_sml b){
    matrix_sml res;

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

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

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

    return res;
}

matrix_sml binpow_sml(matrix_sml a, ll po){
    matrix_sml res;
    bool was = 0;

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

            was = 1;
        }

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

    return res;
}

int get_mask(int x){
    return (digs[x / 10] << PW) + digs[x % 10];
}

int P(ll n, ll k){
    int res = 1;

    for (ll x = 0; x < k; x++)
        res = mult(res, (n - x) % md);

    return res;
}

matrix_big mat_mult_big(matrix_big a, matrix_big b){
    matrix_big res;

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

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

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

    return res;
}

matrix_big binpow_big(matrix_big a, ll po){
    matrix_big res;
    bool was = 0;

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

            was = 1;
        }

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

    return res;
}

void calc_cnt_ways(ll k){
    matrix_sml base;

    for (int i = 0; i < SN; i++){
        for (int j = 0; j < SN; j++)
            base.a[i][j] = 0;

        if (i > 0)
            base.a[i][i - 1] = 1;

        if (i + 1 < SN)
            base.a[i][i + 1] = 1;
    }

    for (int i = 0; i <= 10; i++){
        if (i == k){
            cnt_ways[i] = 1;
            continue;
        }

        if (i > k){
            cnt_ways[i] = 0;
            continue;
        }

        matrix_sml cur = binpow_sml(base, k - i);

        /// parity

        cnt_ways[i] = cur.a[0][0];
    }
}

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;

    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;

    if (m == 1){
        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;
    }

    calc_cnt_ways(k);

    matrix_big base;

    /// calc base (big)

    for (int i = 0; i < 100; i++)
    for (int j = 0; j < 100; j++){
        int fi_msk = get_mask(i);
        int se_msk = get_mask(j);

        int dif = __builtin_popcount(fi_msk ^ se_msk);

        if (dif > k){
            base.a[i][j] = 0;
            continue;
        }

        int beg = P(k, dif);

        beg = mult(beg, cnt_ways[dif]);

        base.a[i][j] = beg;
    }

    matrix_big base_n = binpow_big(base, n / k);

    if (n % k > 0){
        calc_cnt_ways(n % k);

        matrix_big base_nw;

        for (int i = 0; i < 100; i++)
        for (int j = 0; j < 100; j++){
            int fi_msk = get_mask(i);
            int se_msk = get_mask(j);

            int dif = __builtin_popcount(fi_msk ^ se_msk);

            if (dif > k){
                base_nw.a[i][j] = 0;
                continue;
            }

            int beg = P(k, dif);

            beg = mult(beg, cnt_ways[dif]);

            base_nw.a[i][j] = beg;
        }

        base_n = mat_mult_big(base_n, base_nw);
    }

    for (int i = 0; i < 100; i++)
        if (base_n.a[x][i] != 0)
//            cout << i << " " << base_n.a[x][i] << '\n';
        cout << base_n.a[x][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