Submission #977010

#	Time	Username	Problem	Language	Result	Execution time	Memory
977010		efedmrlr	Semafor (COI20_semafor)	C++17	33 / 100	118 ms	5116 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; // 100 for m = 2
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 {
    vector<vector<int> > x;
    Matrix(long unsigned int b) {
        x.assign(b, vector<int>(b, 0));
    }
    void print() {
        cout << "mat: \n";
        REP(i, x.size()) {
            REP(j, x.size()) {
                cout << x[i][j] << " ";
            }
            cout << "\n";
        }
    }
};
Matrix mult(Matrix &x, Matrix &y) {
    Matrix ret(x.x.size());
    REP(i, x.x.size()) {
        REP(j, x.x.size()) {
            REP(k, x.x.size()) {
                ret.x[i][j] = add(ret.x[i][j], mult(x.x[i][k], y.x[k][j]) );
            }
        }
    }
    return ret;
}
vector<int> mult(vector<int> &x, Matrix &y) {
    vector<int> ret(x.size());
    REP(i, x.size()) {
        REP(j, x.size()) {
            ret[j] = add(ret[j], mult(x[i], y.x[i][j]) );
        }
    }
    return ret;
}
Matrix fp(Matrix x, lli y) {
    Matrix ret(x.x.size());
    REP(i, x.x.size()) 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;
    if(m == 2) {
        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(B);
        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[digit[i1]][k][digit[j1]], dp[digit[i2]][K - k][digit[j2]])));
                        }
                        kmat.x[i1 * 10 + i2][j1 * 10 + j2] = v;
                    }
                }
            }
        }

        vector<int> ans(B);
        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";
        }
        return;
    }
    Matrix mat(N);
    REP(i, N) {
        REP(j, N) {
            if(__popcount(i ^ j) == 1) {
                mat.x[i][j] = 1;
            }
        }
    }
    // mat.print();
    // cout << "K:" << K << "\n";
    lli extra = n % K;
    Matrix ext = fp(mat, extra);
    mat = fp(mat, K);
    // mat.print();
    Matrix big(10), bigex(10);
    for(int i = 0; i < 10; i++) {
        vector<int> row(N, 0), rowex(N, 0);
        row[digit[i]] = rowex[digit[i]] = 1;
        row = mult(row, mat);
        rowex = mult(rowex, ext);
        for(int j = 0; j < 10; j++) {
            big.x[i][j] = row[digit[j]];
            bigex.x[i][j] = rowex[digit[j]];
        }
    }
    // big.print();
    vector<int> ans(10, 0);
    ans[x] = 1;
    big = fp(big, n / K);
    // big.print();
    ans = mult(ans, big);
    ans = mult(ans, bigex);
    REP(i, 10) {
        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();
}

Compilation message (stderr)

semafor.cpp: In member function 'void Matrix::print()':
semafor.cpp:9:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, n) for(int i = 0; (i) < (n); (i)++)
      |                                  ~~~~^~~~~
semafor.cpp:59:9: note: in expansion of macro 'REP'
   59 |         REP(i, x.size()) {
      |         ^~~
semafor.cpp:9:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, n) for(int i = 0; (i) < (n); (i)++)
      |                                  ~~~~^~~~~
semafor.cpp:60:13: note: in expansion of macro 'REP'
   60 |             REP(j, x.size()) {
      |             ^~~
semafor.cpp: In function 'Matrix mult(Matrix&, Matrix&)':
semafor.cpp:9:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, n) for(int i = 0; (i) < (n); (i)++)
      |                                  ~~~~^~~~~
semafor.cpp:69:5: note: in expansion of macro 'REP'
   69 |     REP(i, x.x.size()) {
      |     ^~~
semafor.cpp:9:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, n) for(int i = 0; (i) < (n); (i)++)
      |                                  ~~~~^~~~~
semafor.cpp:70:9: note: in expansion of macro 'REP'
   70 |         REP(j, x.x.size()) {
      |         ^~~
semafor.cpp:9:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, n) for(int i = 0; (i) < (n); (i)++)
      |                                  ~~~~^~~~~
semafor.cpp:71:13: note: in expansion of macro 'REP'
   71 |             REP(k, x.x.size()) {
      |             ^~~
semafor.cpp: In function 'std::vector<int> mult(std::vector<int>&, Matrix&)':
semafor.cpp:9:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, n) for(int i = 0; (i) < (n); (i)++)
      |                                  ~~~~^~~~~
semafor.cpp:80:5: note: in expansion of macro 'REP'
   80 |     REP(i, x.size()) {
      |     ^~~
semafor.cpp:9:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, n) for(int i = 0; (i) < (n); (i)++)
      |                                  ~~~~^~~~~
semafor.cpp:81:9: note: in expansion of macro 'REP'
   81 |         REP(j, x.size()) {
      |         ^~~
semafor.cpp: In function 'Matrix fp(Matrix, long long int)':
semafor.cpp:9:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define REP(i, n) for(int i = 0; (i) < (n); (i)++)
      |                                  ~~~~^~~~~
semafor.cpp:89:5: note: in expansion of macro 'REP'
   89 |     REP(i, x.x.size()) ret.x[i][i] = 1;
      |     ^~~

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