Submission #312582

#	Time	Username	Problem	Language	Result	Execution time	Memory
312582		Lawliet	Semafor (COI20_semafor)	C++17	0 / 100	255 ms	1052 KiB

semafor

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXT = 30;
const int MAXN = 110;
const int MOD = 1000000007;

struct matrix
{
	int N;
	lli v[MAXN][MAXN];

	matrix(int n = 0) : N(n) { memset( v , 0 , sizeof(v) ); }

	matrix operator * (matrix a)
	{
		matrix ans( N );

		for(int i = 0 ; i < N ; i++)
		{
			for(int j = 0 ; j < N ; j++)
			{
				for(int k = 0 ; k < N ; k++)
				{
					ans.v[i][j] += v[i][k]*a.v[k][j];
					ans.v[i][j] %= MOD;
				}
			}
		}

		return ans;
	}
};

int m, x;
lli n, k;

lli dpFlips[MAXT];

int maskDigit[] = { 10 , 2 , 9 , 7 , 18 , 21 , 12 , 3 , 29 , 23 };

int getMaskNumber(int x)
{
	int ans = maskDigit[x%10];
	ans += 32*maskDigit[x/10];

	return ans;
}

matrix fastExpo(matrix& a, lli e)
{
	matrix ans( a.N );

	for(int i = 0 ; i < a.N ; i++)
		ans.v[i][i] = 1;

	for(int i = 50 ; i >= 0 ; i--)
	{
		ans = ans*ans;
		if( e & (1LL << i) ) ans = ans*a;
	}

	return ans;
}

void getDPFlips(lli e)
{
	matrix exp( 5*m + 1 );

	for(int t = 0 ; t <= 5*m + 1 ; t++)
	{
		if( t - 1 >= 0 ) exp.v[t - 1][t] = t;
		if( t + 1 <= 5*m + 1 ) exp.v[t + 1][t] = 5*m - t;
	}

	matrix ans = fastExpo( exp , e );

	for(int t = 0 ; t <= 5*m + 1 ; t++)
		dpFlips[t] = ans.v[0][t];
}

int main()
{
	scanf("%d %lld %lld %d",&m,&n,&k,&x);

	getDPFlips( k );

	int maxValue = 10;
	if( m == 2 ) maxValue *= 10;

	matrix adj( maxValue );

	for(int U = 0 ; U < maxValue ; U++)
	{
		for(int V = 0 ; V < maxValue ; V++)
		{
			int x = getMaskNumber(U)^getMaskNumber(V);
			x = __builtin_popcount(x);

			adj.v[U][V] = dpFlips[x];
		}
	}

	matrix finalResult = fastExpo( adj , n/k );

	getDPFlips( n%k );

	for(int U = 0 ; U < maxValue ; U++)
	{
		for(int V = 0 ; V < maxValue ; V++)
		{
			int x = getMaskNumber(U)^getMaskNumber(V);
			adj.v[U][V] = dpFlips[x];
		}
	}	

	finalResult = finalResult*adj;

	for(int i = 0 ; i < maxValue ; i++)
		printf("%lld\n",finalResult.v[x][i]);
}

Compilation message (stderr)

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

• Subtask 1: 0 / 6
• Subtask 2: 0 / 15
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40