oj.uz

Submission #977010

# Submission time Handle Problem Language Result Execution time Memory
977010 2024-05-07T10:19:29 Z efedmrlr Semafor (COI20_semafor) C++17
33 / 100
 118 ms 5116 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 5 ms 504 KB Output is correct
13 Correct 9 ms 348 KB Output is correct
14 Correct 13 ms 492 KB Output is correct
15 Correct 12 ms 492 KB Output is correct
16 Correct 13 ms 348 KB Output is correct
17 Correct 12 ms 344 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 13 ms 348 KB Output is correct
21 Correct 8 ms 348 KB Output is correct
22 Correct 6 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4696 KB Output is correct
2 Correct 13 ms 4700 KB Output is correct
3 Correct 79 ms 5116 KB Output is correct
4 Correct 87 ms 4948 KB Output is correct
5 Correct 88 ms 4948 KB Output is correct
6 Correct 100 ms 4952 KB Output is correct
7 Correct 115 ms 4956 KB Output is correct
8 Correct 118 ms 4976 KB Output is correct
9 Correct 88 ms 4876 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4696 KB Output is correct
2 Correct 13 ms 4700 KB Output is correct
3 Correct 79 ms 5116 KB Output is correct
4 Correct 87 ms 4948 KB Output is correct
5 Correct 88 ms 4948 KB Output is correct
6 Correct 100 ms 4952 KB Output is correct
7 Correct 115 ms 4956 KB Output is correct
8 Correct 118 ms 4976 KB Output is correct
9 Correct 88 ms 4876 KB Output is correct
10 Incorrect 37 ms 4700 KB Output isn't correct
11 Halted 0 ms 0 KB -