Submission #976998

#TimeUsernameProblemLanguageResultExecution timeMemory
976998efedmrlrSemafor (COI20_semafor)C++17
12 / 100
121 ms5076 KiB
#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"; mat = fp(mat, K); // mat.print(); Matrix big(10); for(int i = 0; i < 10; i++) { vector<int> row(N, 0); row[digit[i]] = 1; row = mult(row, mat); for(int j = 0; j < 10; j++) { big.x[i][j] = row[digit[j]]; } } // big.print(); vector<int> ans(10, 0); ans[x] = 1; big = fp(big, n / K); // big.print(); ans = mult(ans, big); 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;
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...