#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[55][6][6], dp2[55][100][100], dp3[100][100];
int fact[12];
int mod=1e9+7;
/*
void f(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}*/
int sum(int a, int b){
return (a+b);
}
int mul(int a, int b){
return (a*b)%mod;
}
int poww(int a, int b){
if(b==0) return 1;
int t=poww(a, b/2);
t=mul(t, t);
if(b&1) return mul(a, t);
return t;
}
int cc(int x){
return mul(fact[5], poww(mul(fact[x], fact[5-x]), mod-2));
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
//f();
int m, n, k, x; cin >> m >> n >> k >> x;
k = min(k, n);
for(int i = 0; i < 6; i++){
if(i>0) dp[0][i][i-1] = i;
if(i<10) dp[0][i][i+1] = 5-i;
}
for(int l=1; l<55; l++){
for(int i=0; i<6; i++){
for(int j=0; j<6; j++){
for(int k=0; k<6; k++){
dp[l][i][k] = sum(dp[l][i][k], mul(dp[l-1][i][j], dp[l-1][j][k]));
}
}
}
}
//1<<x hamlede 3 tekten 4 teke geçiş
vector<int> p(6);
p[0]=1;
for(int i=54; i>=0; i--){
if(!(k&(1ll<<i))) continue;
vector<int> sp(6);
for(int l=0; l<6; l++){
for(int j=0; j<6; j++){
//if(j==5) cout<<dp[i][l][j];
sp[j]=sum(sp[j], mul(p[l], dp[i][l][j]));
}
}
swap(sp, p);
}
fact[0]=1;
for(int i=1; i<6; i++){
fact[i] = mul(fact[i-1], i);
}
for(int i=0; i<6; i++){
p[i]=mul( p[i], poww(cc(i) , mod-2));
}
array<int, 10> c;
array<int, 100> d;
c={10, 8, 18, 28, 9, 31, 6, 24, 23, 29};
for(int i=0; i<10; i++){
for(int l=0; l<10; l++){
d[i*10+l] = c[i]*32+c[l];
}
}
if(m==1){
for(int i = 0; i<10; i++){
for(int l=0; l<10; l++){
int pf=0;
for(int t=0; t<10; t++){
if((c[i]&(1<<t))!=(c[l]&(1<<t))) pf++;
}
dp2[0][i][l] = p[pf];
//if(i==5) cout<<dp2[0][i][l]<<" "<<l<<"\n";
}
}
for(int i=1; i<55; i++){
for(int l=0; l<10; l++){
for(int j=0; j<10; j++){
for(int k=0; k<10; k++){
dp2[i][l][k] = sum(dp2[i][l][k], mul(dp2[i-1][l][j], dp2[i-1][j][k]));
}
}
}
}
vector<int> aa(10);
aa[x] = 1;
for(int i=54; i>=0; i--){
if(k*(1ll<<i)<=n){
int s=n/(k*(1ll<<i));
n-=s*(k*(1ll<<i));
for(int l=0; l<s; l++){
vector<int> sf(10);
for(int j=0; j<10; j++){
for(int kk=0; kk<10; kk++){
sf[kk] = sum(sf[kk], mul(dp2[i][j][kk], aa[j]));
}
}
swap(aa, sf);
}
}
}
vector<int> hm(6);
hm[0]=1;
for(int i=54; i>=0; i--){
if(!(n&(1ll<<i))) continue;
vector<int> sp(6);
for(int l=0; l<6; l++){
for(int j=0; j<6; j++){
sp[j]=sum(sp[j], mul(hm[l], dp[i][l][j]));
}
}
swap(sp, hm);
}
vector<int> ans(10);
for(int i=0; i<6; i++){
hm[i]=mul(hm[i], poww(cc(i), mod-2));
}
for(int l=0; l<10; l++){
for(int i=0; i<10; i++){
int g=0;
for(int t=0; t<10; t++){
if((c[i]&(1<<t))!=(c[l]&(1<<t))) g++;
}
ans[i]=sum(ans[i], hm[g]*aa[i]);
}
}
for(auto i: ans) cout<<i<<" ";
}
}
Compilation message
semafor.cpp: In function 'int main()':
semafor.cpp:45:26: warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
45 | if(i<10) dp[0][i][i+1] = 5-i;
| ~~~~~~~~~~~~~~^~~~~
semafor.cpp:43:19: note: within this loop
43 | for(int i = 0; i < 6; i++){
| ~~^~~
semafor.cpp:45:24: warning: array subscript 6 is above array bounds of 'long long int [6]' [-Warray-bounds]
45 | if(i<10) dp[0][i][i+1] = 5-i;
| ~~~~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
964 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
964 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
