| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 367784 | arnold518 | Semafor (COI20_semafor) | C++14 | 0 ms | 0 KiB |
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;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> Mat;
const int MAXN = 1500;
const ll MOD = 1e9+7;
const int MM[10]={12, 8, 5, 25, 10, 19, 20, 9, 23, 27};
int M, X;
ll N, K;
Mat operator + (const Mat &p, const Mat &q)
{
Mat ret;
int sz=p.size();
ret=vector<vector<ll>>(sz, vector<ll>(sz));
for(int i=0; i<sz; i++)
{
for(int j=0; j<sz; j++)
{
ret[i][j]=0;
for(int k=0; k<sz; k++)
{
ret[i][j]+=p[i][k]*q[k][j]%MOD;
ret[i][j]%=MOD;
//if(ret[i][j]>=MOD) ret[i][j]-=MOD;
}
}
}
return ret;
}
Mat mypow(Mat x, ll y)
{
if(y==0)
{
int sz=x.size();
Mat ret=vector<vector<ll>>(sz, vector<ll>(sz, 0));
for(int i=0; i<sz; i++) ret[i][i]=1;
return ret;
}
if(y%2) return mypow(x, y-1)+x;
Mat ret=mypow(x, y/2);
return ret+ret;
}
Mat A, B, C;
Mat P[MAXN+10], Q, R, S;
ll comb[MAXN+10][MAXN+10];
ll ans[100];
int main()
{
scanf("%d%lld%lld%d", &M, &N, &K, &X);
comb[0][0]=1;
for(int i=1; i<=K; i++)
{
for(int j=0; j<=i; j++)
{
if(j==0 || j==i) comb[i][j]=1;
else comb[i][j]=(comb[i-1][j]+comb[i-1][j-1])%MOD;
}
}
A=vector<vector<ll>>(32, vector<ll>(32));
for(int i=0; i<32; i++)
{
for(int j=0; j<32; j++)
{
if(__builtin_popcount(i^j)==1) A[i][j]=1;
}
}
if(M==2)
{
P[0]=mypow(A, 0);
for(int i=1; i<=K; i++)
{
P[i]=P[i-1]+A;
}
Q=vector<vector<ll>>(100, vector<ll>(100));
for(int i=0; i<=K; i++)
{
for(int p=0; p<100; p++)
{
for(int q=0; q<100; q++)
{
Q[p][q]+=P[i][MM[p/10]][MM[q/10]]*P[K-i][MM[p%10]][MM[q%10]]%MOD*comb[K][i]%MOD;
Q[p][q]%=MOD;
}
}
}
R=vector<vector<ll>>(100, vector<ll>(100));
for(int i=0; i<=N%K; i++)
{
for(int p=0; p<100; p++)
{
for(int q=0; q<100; q++)
{
R[p][q]+=P[i][MM[p/10]][MM[q/10]]*P[N%K-i][MM[p%10]][MM[q%10]]%MOD*comb[N%K][i]%MOD;
R[p][q]%=MOD;
}
}
}
S=mypow(Q, N/K)+R;
for(int i=0; i<100; i++)
{
printf("%lld\n", S[X][i]);
}
return 0;
}
else
{
B=mypow(A, K);
C=mypow(A, N%K);
P=vector<vector<ll>>(10, vector<ll>(10));
Q=vector<vector<ll>>(10, vector<ll>(10));
for(int i=0; i<10; i++)
{
for(int j=0; j<10; j++)
{
P[i][j]=B[MM[i]][MM[j]];
Q[i][j]=C[MM[i]][MM[j]];
}
}
R=mypow(P, N/K)+Q;
for(int i=0; i<10; i++)
{
printf("%lld\n", R[X][i]);
}
}
}