oj.uz

Submission #977013

# Submission time Handle Problem Language Result Execution time Memory
977013 2024-05-07T10:23:16 Z efedmrlr Semafor (COI20_semafor) C++17
60 / 100
 500 ms 5628 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);
        Matrix ext(B);
        lli extra = n % K;
        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;

                        v = 0;
                        REP(k, extra + 1) {
                            v = add(v, mult(comb(extra, k), mult(dp[digit[i1]][k][digit[j1]], dp[digit[i2]][extra - k][digit[j2]])));                            
                        }
                        ext.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);
        ans = mult(ans, ext);
        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 348 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 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 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 348 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 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 5 ms 348 KB Output is correct
13 Correct 9 ms 348 KB Output is correct
14 Correct 15 ms 348 KB Output is correct
15 Correct 12 ms 348 KB Output is correct
16 Correct 13 ms 344 KB Output is correct
17 Correct 12 ms 348 KB Output is correct
18 Correct 1 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 7 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 7 ms 4700 KB Output is correct
2 Correct 14 ms 4700 KB Output is correct
3 Correct 77 ms 4900 KB Output is correct
4 Correct 87 ms 4948 KB Output is correct
5 Correct 88 ms 4948 KB Output is correct
6 Correct 97 ms 4972 KB Output is correct
7 Correct 118 ms 5204 KB Output is correct
8 Correct 111 ms 5020 KB Output is correct
9 Correct 87 ms 4928 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4700 KB Output is correct
2 Correct 96 ms 4788 KB Output is correct
3 Correct 150 ms 4780 KB Output is correct
4 Correct 190 ms 4696 KB Output is correct
5 Correct 180 ms 4948 KB Output is correct
6 Correct 174 ms 4700 KB Output is correct
7 Correct 185 ms 4700 KB Output is correct
8 Correct 179 ms 4776 KB Output is correct
9 Correct 184 ms 4780 KB Output is correct
10 Correct 173 ms 4696 KB Output is correct
11 Correct 21 ms 4700 KB Output is correct
12 Correct 10 ms 4700 KB Output is correct
13 Correct 185 ms 4780 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4700 KB Output is correct
2 Correct 96 ms 4788 KB Output is correct
3 Correct 150 ms 4780 KB Output is correct
4 Correct 190 ms 4696 KB Output is correct
5 Correct 180 ms 4948 KB Output is correct
6 Correct 174 ms 4700 KB Output is correct
7 Correct 185 ms 4700 KB Output is correct
8 Correct 179 ms 4776 KB Output is correct
9 Correct 184 ms 4780 KB Output is correct
10 Correct 173 ms 4696 KB Output is correct
11 Correct 21 ms 4700 KB Output is correct
12 Correct 10 ms 4700 KB Output is correct
13 Correct 185 ms 4780 KB Output is correct
14 Correct 75 ms 4944 KB Output is correct
15 Correct 214 ms 5000 KB Output is correct
16 Correct 240 ms 4956 KB Output is correct
17 Correct 257 ms 5012 KB Output is correct
18 Correct 261 ms 4872 KB Output is correct
19 Correct 234 ms 4972 KB Output is correct
20 Correct 224 ms 4996 KB Output is correct
21 Correct 176 ms 4700 KB Output is correct
22 Correct 184 ms 4780 KB Output is correct
23 Correct 250 ms 4944 KB Output is correct
24 Correct 351 ms 4956 KB Output is correct
25 Correct 320 ms 4952 KB Output is correct
26 Correct 12 ms 4576 KB Output is correct
27 Correct 17 ms 4800 KB Output is correct
28 Correct 265 ms 5016 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4700 KB Output is correct
2 Correct 14 ms 4700 KB Output is correct
3 Correct 77 ms 4900 KB Output is correct
4 Correct 87 ms 4948 KB Output is correct
5 Correct 88 ms 4948 KB Output is correct
6 Correct 97 ms 4972 KB Output is correct
7 Correct 118 ms 5204 KB Output is correct
8 Correct 111 ms 5020 KB Output is correct
9 Correct 87 ms 4928 KB Output is correct
10 Correct 38 ms 4700 KB Output is correct
11 Correct 96 ms 4788 KB Output is correct
12 Correct 150 ms 4780 KB Output is correct
13 Correct 190 ms 4696 KB Output is correct
14 Correct 180 ms 4948 KB Output is correct
15 Correct 174 ms 4700 KB Output is correct
16 Correct 185 ms 4700 KB Output is correct
17 Correct 179 ms 4776 KB Output is correct
18 Correct 184 ms 4780 KB Output is correct
19 Correct 173 ms 4696 KB Output is correct
20 Correct 21 ms 4700 KB Output is correct
21 Correct 10 ms 4700 KB Output is correct
22 Correct 185 ms 4780 KB Output is correct
23 Correct 75 ms 4944 KB Output is correct
24 Correct 214 ms 5000 KB Output is correct
25 Correct 240 ms 4956 KB Output is correct
26 Correct 257 ms 5012 KB Output is correct
27 Correct 261 ms 4872 KB Output is correct
28 Correct 234 ms 4972 KB Output is correct
29 Correct 224 ms 4996 KB Output is correct
30 Correct 176 ms 4700 KB Output is correct
31 Correct 184 ms 4780 KB Output is correct
32 Correct 250 ms 4944 KB Output is correct
33 Correct 351 ms 4956 KB Output is correct
34 Correct 320 ms 4952 KB Output is correct
35 Correct 12 ms 4576 KB Output is correct
36 Correct 17 ms 4800 KB Output is correct
37 Correct 265 ms 5016 KB Output is correct
38 Incorrect 500 ms 5628 KB Output isn't correct
39 Halted 0 ms 0 KB -