This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
inline int add(int a, int b){return (a+b>=MOD)?a+b-MOD:a+b;}
inline void inc(int& a, int b){a = add(a, b);}
inline int sub(int a, int b){return (a-b<0)?a-b+MOD:a-b;}
inline void dec(int &a, int b){a = sub(a, b);}
inline int mul(int a, int b){return 1ll*a*b%MOD;}
inline void grow(int &a, int b){a = mul(a, b);}
int bpow(int a, int b){
int res = 1;
while(b > 0){
if(b&1) grow(res, a);
grow(a, a);
b >>= 1;
}
return res;
}
int inv(int a){return bpow(a, MOD-2);}
struct Matrix{
int n, m;
vector<vector<int>> mat;
Matrix(){}
Matrix(int _n, int _m){
n = _n, m = _m;
mat.assign(n, vector<int>(m, 0));
}
void setID(){
assert(n == m);
for(int i = 0; i<n; i++)
mat[i][i] = 1;
}
Matrix operator * (const Matrix &o) const{
Matrix res(n, o.m);
for(int i = 0; i<n; i++)
for(int j = 0; j<o.m; j++)
for(int k = 0; k<m; k++)
inc(res.mat[i][j], mul(mat[i][k], o.mat[k][j]));
return res;
}
};
Matrix matpow(Matrix a, int b){
assert(a.n == a.m);
Matrix res(a.n, a.n); res.setID();
while(b > 0){
if(b&1) res = res*a;
a = a*a;
b >>= 1;
}
return res;
}
int n_mask[10] = {10, 2, 9, 7, 18, 21, 12, 3, 29, 23};
int m, n, k, x;
Matrix help, g, tmp_help;
int comb[15][15];
Matrix trans, ans, tmp_trans;
void solveHelp(int siz){
help = Matrix(1, siz+1);
help.mat[0][0] = 1;
g = Matrix(siz+1, siz+1);
for(int i = 0; i<siz; i++)
g.mat[i][i+1] = mul(mul(comb[siz][i], siz-i), inv(comb[siz][i+1])),
g.mat[i+1][i] = mul(mul(comb[siz][i+1], i+1), inv(comb[siz][i]));
tmp_help = help*matpow(g, n%k);
help = help*matpow(g, k);
}
signed main(){
// freopen("a.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> m >> n >> k >> x;
comb[0][0] = 1;
for(int i = 1; i<=10; i++){
comb[i][0] = comb[i][i] = 1;
for(int j = 1; j<i; j++)
comb[i][j] = add(comb[i-1][j-1], comb[i-1][j]);
}
solveHelp(m*5);
if(m == 1){
trans = Matrix(10, 10);
tmp_trans = Matrix(10, 10);
ans = Matrix(1, 10);
for(int i = 0; i<10; i++)
for(int j = 0; j<10; j++)
trans.mat[i][j] = help.mat[0][__builtin_popcount(n_mask[i]^n_mask[j])],
tmp_trans.mat[i][j] = tmp_help.mat[0][__builtin_popcount(n_mask[i]^n_mask[j])];
ans.mat[0][x] = 1;
ans = ans*matpow(trans, n/k);
ans = ans*tmp_trans;
for(int i = 0; i<10; i++)
cout << ans.mat[0][i] << '\n';
} else{
trans = Matrix(100, 100);
tmp_trans = Matrix(100, 100);
ans = Matrix(1, 100);
for(int a = 0; a<10; a++)
for(int b = 0; b<10; b++)
for(int c = 0; c<10; c++)
for(int d = 0; d<10; d++)
trans.mat[a+10*b][c+10*d] =
help.mat[0][__builtin_popcount(n_mask[a]^n_mask[c])+__builtin_popcount(n_mask[b]^n_mask[d])],
tmp_trans.mat[a+10*b][c+10*d] =
tmp_help.mat[0][__builtin_popcount(n_mask[a]^n_mask[c])+__builtin_popcount(n_mask[b]^n_mask[d])];
ans.mat[0][x] = 1;
ans = ans*matpow(trans, n/k);
ans = ans*tmp_trans;
for(int i = 0; i<100; i++)
cout << ans.mat[0][i] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |