#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[digit[i1]][k][digit[j1]], dp[digit[i2]][K - k][digit[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();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
4732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
