Submission #381629

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381629	2021-03-25T11:36:19 Z	VEGAnn	Semafor (COI20_semafor)	C++14	Compilation error	0 ms	0 KB

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

    matrix_sml cur = binpow_sml(base, k);

    for (int i = 0; i < 11; i++)
        cnt_ways[i] = cur.a[i][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;
        }

        base.a[i][j] = cnt_ways[dif];
    }

//    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;
//            }
//
//            base_nw.a[i][j] = cnt_ways[dif];
//        }
//
//        base_n = mat_mult_big(base_n, base_nw);
//    }

    for (int i = 0; i < 100; i++)
        cout << base_n.a[x][i] << '\n';

    return 0;
}

Compilation message

semafor.cpp: In function 'int main()':
semafor.cpp:287:17: error: 'base_n' was not declared in this scope; did you mean 'base_nw'?
  287 |         cout << base_n.a[x][i] << '\n';
      |                 ^~~~~~
      |                 base_nw