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>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define int long long
int Cnk[11][11];
const int mod = (int)1e9 + 7;
const ll mod2 = 1ll * mod * mod;
template<typename T>
void md(T &a){
if(a >= mod)
a-=mod;
}
template<typename T>
void md2(T &a){
if(a >= mod2)
a-=mod2;
}
int B;
struct mat{
vector<vector<int>>a;
int n , m;
mat(){
n = m = B;
a.resize(n , vector < int > (m));
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
a[i][j]=0;
}
mat(int _n, int _m){
n = _n , m = _m;
a.resize(n , vector < int > (m));
for(int i=0;i<n;++i)
for(int j=0;j<m;++j){
a[i][j] = 0;
}
}
};
mat operator*(const mat&a , const mat&b){
mat c(a.n, b.m);
assert(a.m == b.n);
for(int i = 0; i < a.n; ++i){
for(int j = 0; j < b.m;++j){
ll f = 0;
for(int k = 0; k < a.m; ++k){
f += (1ll * a.a[i][k] * b.a[k][j]);
md2(f);
}
c.a[i][j] = f % mod;
}
}
return c;
}
mat one(int f){
mat c(f , f);
for(int i = 0; i < f; ++i)
c.a[i][i] = 1;
return c;
}
mat binpow(const mat &a , ll b){
if(b == 0)
return one(a.n);
mat ans = binpow(a , b / 2);
ans = ans * ans;
if(b & 1)
ans = ans * a;
return ans;
}
int binpow_num(int a , int b){
if(b == 0)
return 1;
int ans = binpow_num(a , b / 2);
ans = (1ll * ans * ans) % mod;
if(b & 1)
ans = (1ll * ans * a) % mod;
return ans;
}
int INV(int x){
return binpow_num(x , mod - 2);
}
signed main(){
ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
/// n a b c d e
/// 0 0 1 0 1 0
/// 1 0 1 0 0 0
/// 2 1 0 0 1 0
/// 3 1 1 1 0 0
/// 4 0 1 0 0 1
/// 5 1 0 1 0 1
/// 6 0 0 1 1 0
/// 7 1 1 0 0 0
/// 8 1 0 1 1 1
/// 9 1 1 1 0 1
string st[10];
st[0] ="01010";
st[1] ="01000";
st[2]="10010";
st[3]= "11100";
st[4]= "01001";
st[5]= "10101";
st[6]= "00110";
st[7]= "11000";
st[8]= "10111";
st[9]= "11101";
vector<int> id(10), f;
for(int i = 0; i < 10; ++i){
id[i] = 0;
for(int j = 0; j < 5; ++j){
if(st[i][j] == '1')
id[i] += (1 << j);
}
}
f = id;
sort(all(f));
f.erase(unique(all(f)), f.end());
assert(sz(f) == 10);
int m, x;
ll n ,k ;
cin >> m >> n >> k >> x;
B = m * 5;
auto get_msk = [&](int f){
int msk = 0;
if(m == 1){
msk = id[f];
}else{
msk = ((id[f / 10])<<5)|(id[f%10]);
}
return msk;
};
vector < int > get(100);
vector < int > cnt(10);
for(int i = 0; i < 11; ++i){
Cnk[i][0]=1;
for(int j = 1; j <= i; ++j){
Cnk[i][j] = Cnk[i - 1][j] + Cnk[i - 1][j - 1];
md(Cnk[i][j]);
}
}
mat trans(B,B);
for(int i = 0; i < B; ++i){
for(int j = 0; j < B; ++j){
if(abs(i - j) > 1)
continue;
if(i == j)
continue;
if(i + 1 == j)
trans.a[i][j] = 1ll * (B - i)% mod;
else
trans.a[i][j] = 1ll * i % mod;
}
}
mat trans1 = trans;
trans = binpow(trans1 , k);
int states = 10;
if(m == 2)states *= 10;
mat ST(states , states);
mat init(1 , B);
init.a[0][0] = 1;
trans = init * trans;
for(int i = 0; i < states; ++i) {
for(int j = 0 ; j < states; ++j){
int t = __builtin_popcount(get_msk(i) ^ get_msk(j));
ST.a[i][j] = (1ll * trans.a[0][t] * INV(Cnk[B][t])) % mod;
}
}
//
// for(int i = 0; i < states; ++i){
// for(int j = 0; j < states; ++j){
// cout << ST.a[i][j] << ' ';
// }
// cout << '\n';
// }
mat INIT(1 , states);
INIT.a[0][x] = 1;
ST = INIT * binpow(ST , n / k);
trans =trans1;
trans = binpow(trans , n % k);
//
// for(int i = 0; i < 10; ++i)
// cout << ST.a[0][i] << ' ';
// cout << endl;
vector < int > ans(states);
for(int i = 0; i < states; ++i) {
for(int j = 0 ; j < states; ++j){
int t = __builtin_popcount(get_msk(i) ^ get_msk(j));
ans[j] += 1ll * ST.a[0][i] * 1ll * trans.a[0][t] % mod * INV(Cnk[B][t]) % mod;
md(ans[j]);
}
}
for(int i = 0; i < states; ++i){
cout << ans[i] << '\n';
}
return 0;
}
# | 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... |