#include <bits/stdc++.h>
#define i2 array<int,2>
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int PW = 5;
const int M = (1 << PW);
const int N = 100;
const int SN = 11;
const int md = int(1e9) + 7;
int digs[10];
bool mrk[M];
ll m, n, k, x;
struct matrix{
int a[M][M];
};
matrix base, base_k, base_nw;
int sum(int x, int y){
x += y;
if (x >= md)
x -= md;
return x;
}
int mult(int x, int y) { return (1ll * x * y) % md; }
matrix mat_mult(matrix a, matrix b){
matrix res;
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++) {
int nw = 0;
for (int k = 0; k < M; k++)
nw = sum(nw, mult(a.a[i][k], b.a[k][j]));
res.a[i][j] = nw;
}
return res;
}
matrix binpow(matrix a, ll po){
matrix res;
bool was = 0;
while (po > 0){
if (po & 1){
if (!was)
res = a;
else res = mat_mult(res, a);
was = 1;
}
a = mat_mult(a, a);
po >>= 1;
}
return res;
}
struct matrix_sml{
int a[SN][SN];
};
struct matrix_big{
int a[N][N];
};
int cnt_ways[SN];
matrix_sml mat_mult_sml(matrix_sml a, matrix_sml b){
matrix_sml res;
for (int i = 0; i < SN; i++)
for (int j = 0; j < SN; j++) {
int nw = 0;
for (int k = 0; k < SN; k++)
nw = sum(nw, mult(a.a[i][k], b.a[k][j]));
res.a[i][j] = nw;
}
return res;
}
matrix_sml binpow_sml(matrix_sml a, ll po){
matrix_sml res;
bool was = 0;
while (po > 0){
if (po & 1){
if (!was)
res = a;
else res = mat_mult_sml(res, a);
was = 1;
}
a = mat_mult_sml(a, a);
po >>= 1;
}
return res;
}
int get_mask(int x){
return (digs[x / 10] << PW) + digs[x % 10];
}
int P(ll n, ll k){
int res = 1;
for (ll x = 0; x < k; x++)
res = mult(res, (n - x) % md);
return res;
}
matrix_big mat_mult_big(matrix_big a, matrix_big b){
matrix_big res;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
int nw = 0;
for (int k = 0; k < N; k++)
nw = sum(nw, mult(a.a[i][k], b.a[k][j]));
res.a[i][j] = nw;
}
return res;
}
matrix_big binpow_big(matrix_big a, ll po){
matrix_big res;
bool was = 0;
while (po > 0){
if (po & 1){
if (!was)
res = a;
else res = mat_mult_big(res, a);
was = 1;
}
a = mat_mult_big(a, a);
po >>= 1;
}
return res;
}
void calc_cnt_ways(ll k){
matrix_sml base;
for (int i = 0; i < SN; i++){
for (int j = 0; j < SN; j++)
base.a[i][j] = 0;
if (i > 0)
base.a[i][i - 1] = 1;
if (i + 1 < SN)
base.a[i][i + 1] = 1;
}
matrix_sml cur = binpow_sml(base, k);
for (int i = 0; i < 11; i++)
cnt_ways[i] = cur.a[i][0];
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> m >> n >> k >> x;
digs[1] = 8;
digs[2] = 18;
digs[3] = 28;
digs[4] = 9;
digs[5] = 21;
digs[6] = 6;
digs[7] = 24;
digs[8] = 23;
digs[9] = 29;
digs[0] = 10;
if (m == 1){
for (int i = 0; i < 10; i++)
mrk[digs[i]] = 1;
for (int i = 0; i < M; i++){
for (int j = 0; j < PW; j++)
base.a[i][(i ^ (1 << j))] = 1;
}
base_k = binpow(base, k);
/// in base_k you need transitions only between digits
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++)
if (!mrk[i] || !mrk[j])
base_k.a[i][j] = 0;
base_k = binpow(base_k, n / k);
if (n % k > 0){
/// calc one more matirix pls
base_nw = binpow(base, n % k);
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++)
if (!mrk[i] || !mrk[j])
base_nw.a[i][j] = 0;
base_k = mat_mult(base_k, base_nw);
}
for (int i = 0; i < 10; i++)
cout << base_k.a[digs[x]][digs[i]] << '\n';
return 0;
}
calc_cnt_ways(k);
matrix_big base;
/// calc base (big)
for (int i = 0; i < 100; i++)
for (int j = 0; j < 100; j++){
int fi_msk = get_mask(i);
int se_msk = get_mask(j);
int dif = __builtin_popcount(fi_msk ^ se_msk);
if (dif > k){
base.a[i][j] = 0;
continue;
}
base.a[i][j] = cnt_ways[dif];
}
// matrix_big base_n = binpow_big(base, n / k);
//
// if (n % k > 0){
// calc_cnt_ways(n % k);
//
// matrix_big base_nw;
//
// for (int i = 0; i < 100; i++)
// for (int j = 0; j < 100; j++){
// int fi_msk = get_mask(i);
// int se_msk = get_mask(j);
//
// int dif = __builtin_popcount(fi_msk ^ se_msk);
//
// if (dif > k){
// base_nw.a[i][j] = 0;
// continue;
// }
//
// base_nw.a[i][j] = cnt_ways[dif];
// }
//
// base_n = mat_mult_big(base_n, base_nw);
// }
for (int i = 0; i < 100; i++)
cout << base_n.a[x][i] << '\n';
return 0;
}
Compilation message
semafor.cpp: In function 'int main()':
semafor.cpp:287:17: error: 'base_n' was not declared in this scope; did you mean 'base_nw'?
287 | cout << base_n.a[x][i] << '\n';
| ^~~~~~
| base_nw
