Submission #976950

#	Time	Username	Problem	Language	Result	Execution time	Memory
976950		efedmrlr	Semafor (COI20_semafor)	C++17	0 / 100	21 ms	4700 KiB

semafor

#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 32;
const int KMX = 1505;
const int INF = 1e9 + 500;
const int B = 100;
const int MOD = 1e9 + 7;
array<pair<int, int>, B> msk;
array<int, 10> digit = {10, 2, 9, 7, 18, 21, 12, 3, 29, 23};
array<int, KMX> fac, ifac;
int add(int x, int y) {
    if(x + y >= MOD) return x + y - MOD;
    return x + y;
}
int subt(int x, int y) {
    if(x - y < 0) return x - y + MOD;
    return x - y;
}
int mult(int x, int y) {
    return (int)(1ll * x * y % MOD);
} 
int fp(int x, int y) {
    int ret = 1;
    while(y > 0) {
        if(y & 1) {
            ret = mult(ret, x);
        }
        x = mult(x, x);
        y >>= 1;
    }
    return ret;
}
int comb(int x, int y) {
    assert(x >= y);
    return mult(fac[x], mult(ifac[y], ifac[x - y]));
}
struct Matrix {
    array<array<int, B>, B> x;
    Matrix() {
        REP(i, B) REP(j, B) x[i][j] = 0;
    }
};
Matrix mult(Matrix &x, Matrix &y) {
    Matrix ret;
    REP(i, B) {
        REP(j, B) {
            REP(k, B) {
                ret.x[i][j] = add(ret.x[i][j], add(x.x[i][k], y.x[k][j]) );
            }
        }
    }
    return ret;
}
array<int, B> mult(array<int, B> &x, Matrix &y) {
    array<int, B> ret;
    REP(i, B) {
        REP(j, B) {
            ret[j] = add(ret[j], mult(x[i], y.x[i][j]) );
        }
    }
    return ret;
}
Matrix fp(Matrix x, lli y) {
    Matrix ret;
    REP(i, B) ret.x[i][i] = 1;
    while(y > 0ll) {
        if(y & 1ll) {
            ret = mult(ret, x);
        }
        y >>= 1ll;
        x = mult(x, x);
    }
    return ret;
}

array<array<array<int, N>, KMX>, N> dp; // from, step, to

void solve() {
    int m, x;
    lli  n, K;
    cin >> m >> n >> K >> x;
    for(auto d : digit) {
        dp[d][0][d] = 1;
        for(int i = 1; i <= K; i++) {
            fill(all(dp[d][i]), 0);
            for(int j = 0; j < N; j++) {
                for(int bt = 0 ; bt < 5; bt++) {
                    dp[d][i][j] = add(dp[d][i][j], dp[d][i - 1][j ^ (1 << bt)]);
                }
            }
        }
    }
    Matrix kmat;
    REP(i1, 10) {
        REP(i2, 10) {
            REP(j1, 10) {
                REP(j2, 10) {
                    int v = 0;

                    REP(k, K + 1) {
                        v = add(v, mult(comb(K, k), mult(dp[i1][k][j1], dp[i2][K - k][j2])));
                    }
                    kmat.x[i1 * 10 + i2][j1 * 10 + j2] = v;
                }
            }
        }
    }
    array<int, B> ans;
    fill(all(ans), 0);
    ans[x] = 1;
    kmat = fp(kmat, n / K);
    ans = mult(ans, kmat);
    for(int i = 0; i < B; i++) {
        cout << ans[i] << "\n";
    }
}


signed main() { 
    fac[0] = 1;
    for(int i = 1; i < KMX; i++) {
        fac[i] = mult(fac[i - 1], i);
    }
    ifac[KMX - 1] = fp(fac[KMX - 1], MOD - 2);
    for(int i = KMX - 2; i >= 0; i--) {
        ifac[i] = mult(ifac[i + 1], i + 1);
    }
    for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            msk[i * 10 + j] = MP(digit[i], digit[j]);
        }
    }
    fastio();
    solve();
}

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