oj.uz

Submission #367785

# Submission time Handle Problem Language Result Execution time Memory
367785 2021-02-18T10:07:39 Z arnold518 Semafor (COI20_semafor) C++14
45 / 100
 991 ms 33388 KB 
#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, PP;

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);
	 
		PP=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++)
			{
				PP[i][j]=B[MM[i]][MM[j]];
				Q[i][j]=C[MM[i]][MM[j]];
			}
		}
	 
	 
		R=mypow(PP, N/K)+Q;
	 
		for(int i=0; i<10; i++)
		{
			printf("%lld\n", R[X][i]);
		}
	}
}

Compilation message

semafor.cpp: In function 'int main()':
semafor.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |  scanf("%d%lld%lld%d", &M, &N, &K, &X);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Runtime error 37 ms 29164 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1004 KB Output is correct
2 Correct 41 ms 2284 KB Output is correct
3 Correct 305 ms 18156 KB Output is correct
4 Correct 346 ms 21248 KB Output is correct
5 Correct 349 ms 21504 KB Output is correct
6 Correct 386 ms 24684 KB Output is correct
7 Correct 443 ms 28780 KB Output is correct
8 Correct 442 ms 28708 KB Output is correct
9 Correct 328 ms 20460 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2156 KB Output is correct
2 Correct 208 ms 3948 KB Output is correct
3 Correct 295 ms 5612 KB Output is correct
4 Correct 394 ms 7148 KB Output is correct
5 Correct 364 ms 6636 KB Output is correct
6 Correct 355 ms 6636 KB Output is correct
7 Correct 371 ms 6892 KB Output is correct
8 Correct 359 ms 6540 KB Output is correct
9 Correct 355 ms 6636 KB Output is correct
10 Correct 353 ms 6636 KB Output is correct
11 Correct 43 ms 1388 KB Output is correct
12 Correct 17 ms 1132 KB Output is correct
13 Correct 371 ms 6636 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2156 KB Output is correct
2 Correct 208 ms 3948 KB Output is correct
3 Correct 295 ms 5612 KB Output is correct
4 Correct 394 ms 7148 KB Output is correct
5 Correct 364 ms 6636 KB Output is correct
6 Correct 355 ms 6636 KB Output is correct
7 Correct 371 ms 6892 KB Output is correct
8 Correct 359 ms 6540 KB Output is correct
9 Correct 355 ms 6636 KB Output is correct
10 Correct 353 ms 6636 KB Output is correct
11 Correct 43 ms 1388 KB Output is correct
12 Correct 17 ms 1132 KB Output is correct
13 Correct 371 ms 6636 KB Output is correct
14 Correct 251 ms 12908 KB Output is correct
15 Correct 631 ms 28140 KB Output is correct
16 Correct 676 ms 25324 KB Output is correct
17 Correct 731 ms 30700 KB Output is correct
18 Correct 638 ms 19852 KB Output is correct
19 Correct 601 ms 18156 KB Output is correct
20 Correct 606 ms 20588 KB Output is correct
21 Correct 355 ms 6636 KB Output is correct
22 Correct 389 ms 6636 KB Output is correct
23 Correct 676 ms 23916 KB Output is correct
24 Correct 991 ms 33388 KB Output is correct
25 Correct 927 ms 33388 KB Output is correct
26 Correct 22 ms 1132 KB Output is correct
27 Correct 35 ms 1388 KB Output is correct
28 Correct 769 ms 31008 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1004 KB Output is correct
2 Correct 41 ms 2284 KB Output is correct
3 Correct 305 ms 18156 KB Output is correct
4 Correct 346 ms 21248 KB Output is correct
5 Correct 349 ms 21504 KB Output is correct
6 Correct 386 ms 24684 KB Output is correct
7 Correct 443 ms 28780 KB Output is correct
8 Correct 442 ms 28708 KB Output is correct
9 Correct 328 ms 20460 KB Output is correct
10 Correct 76 ms 2156 KB Output is correct
11 Correct 208 ms 3948 KB Output is correct
12 Correct 295 ms 5612 KB Output is correct
13 Correct 394 ms 7148 KB Output is correct
14 Correct 364 ms 6636 KB Output is correct
15 Correct 355 ms 6636 KB Output is correct
16 Correct 371 ms 6892 KB Output is correct
17 Correct 359 ms 6540 KB Output is correct
18 Correct 355 ms 6636 KB Output is correct
19 Correct 353 ms 6636 KB Output is correct
20 Correct 43 ms 1388 KB Output is correct
21 Correct 17 ms 1132 KB Output is correct
22 Correct 371 ms 6636 KB Output is correct
23 Correct 251 ms 12908 KB Output is correct
24 Correct 631 ms 28140 KB Output is correct
25 Correct 676 ms 25324 KB Output is correct
26 Correct 731 ms 30700 KB Output is correct
27 Correct 638 ms 19852 KB Output is correct
28 Correct 601 ms 18156 KB Output is correct
29 Correct 606 ms 20588 KB Output is correct
30 Correct 355 ms 6636 KB Output is correct
31 Correct 389 ms 6636 KB Output is correct
32 Correct 676 ms 23916 KB Output is correct
33 Correct 991 ms 33388 KB Output is correct
34 Correct 927 ms 33388 KB Output is correct
35 Correct 22 ms 1132 KB Output is correct
36 Correct 35 ms 1388 KB Output is correct
37 Correct 769 ms 31008 KB Output is correct
38 Runtime error 37 ms 29164 KB Execution killed with signal 11
39 Halted 0 ms 0 KB -