oj.uz

Submission #411832

# Submission time Handle Problem Language Result Execution time Memory
411832 2021-05-26T05:46:58 Z 장태환(#7564) Semafor (COI20_semafor) C++17
12 / 100
 33 ms 1740 KB 
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <string>
#include <assert.h>
#define int long long
#define MOD 1000000007
using namespace std;
struct matrix
{
	int N, M;
	vector<vector<int>>x;
	void init(int n,int m)//create a N*M matrix
	{
		N = n;
		M = m;
		vector<int>ne(M,0);
		vector<vector<int>>nne(N, ne);
		x = nne;
	}
};
matrix mul(matrix a, matrix b)// multiplying the matrix 
{
	assert(a.M == b.N);
	int i, j, k;
	matrix ne;
	ne.init(a.N, b.M);
	for (i = 0; i < a.N; i++)
	{
		for (j = 0; j < a.M; j++)
		{
			for (k = 0; k < b.M; k++)
			{
				ne.x[i][k] += a.x[i][j] * b.x[j][k];
				ne.x[i][k] %=1000000007;
			}
		}
	}
	return ne;
}
matrix pow(matrix a, int k)// powering the matrix 
{
	if (k == 1)
		return a;
	if (k % 2)
	{
		return mul(a, pow(a, k - 1));
	}
	matrix re = pow(a, k / 2);
	return mul(re, re);
}
int nums[10] = { 10,2,9,7,18,21,12,3,29,23 };//be cafeful to not make a hard-to-find mistake!
int	nums2[100];//table for 2-digits
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int M, N,K, X;
	cin >> M>>N>>K>>X;
	int i;
	for (i = 0; i < 100; i++)
	{
		nums2[i] = nums[i / 10] * 32 + nums[i % 10];
	}
	int bitcou=5*M;
	matrix ori;
	ori.init(1, bitcou+1);
	ori.x[0][0] = 1;
	matrix muori;//ori*(muori^K)=first layer of dp(how many cases for i bit change)
	muori.init(bitcou+1, bitcou+1);
	for (i = 0; i <= bitcou; i++)
	{
		if (i)
		{
			muori.x[i][i-1] += bitcou-i+1;
		}
		if (i < bitcou)
		{
			muori.x[i][i + 1] +=i+1;
		}
	}
	matrix firstdp = mul(ori, pow(muori, K));
	matrix remainderdp;//dp for last N%K
	if (N % K)
	{
		remainderdp = mul(ori, pow(muori, N%K));
	}
	int casecou = M * 90 - 80;
	matrix secondori;
	secondori.init(1, casecou);
	secondori.x[0][X] = 1;
	matrix secondmu; //secondori* (secondmu ^ (N/K) = second layer of dp(how many case to number j)
	secondmu.init(casecou, casecou);
	int j;
	for (i = 0; i < casecou; i++)
	{
		for (j = 0; j < casecou; j++)
		{
			int diff = 0;
			if (M == 1)
			{
				int k;
				for (k = 0; k < 5; k++)
				{
					if ((1<<k) & (nums[i] ^ nums[j]))
					{
						diff++;
					}
				}
			}
			else
			{
				int k;
				for (k = 0; k < 10; k++)
				{
					if ((1<<k) & (nums2[i] ^ nums2[j]))
					{
						diff++;
					}
				}
			}
			secondmu.x[i][j] = firstdp.x[0][diff];
		}
	}
	secondori = mul(secondori, pow(secondmu, N/K));
	for (i = 0; i < casecou; i++)
	{
		if (N % K == 0)
		{
			cout << secondori.x[0][i] << '\n';
		}
		else
		{
			for (j = 0; j < casecou; j++)
			{
				int diff = 0;
				if (M == 1)
				{
					int k;
					for (k = 0; k < 5; k++)
					{
						if ((1 & k) && (nums[i] ^ nums[j]))
						{
							diff++;
						}
					}
				}
				else
				{
					int k;
					for (k = 0; k < 10; k++)
					{
						if ((1 & k) && (nums2[i] ^ nums2[j]))
						{
							diff++;
						}
					}
				}
				cout << secondori.x[0][j] * remainderdp.x[j][i]%MOD<<'\n';
			}
		}
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 1 ms 460 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 1 ms 460 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 1740 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 1740 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 444 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Runtime error 33 ms 1740 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -