# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
312581 |
2020-10-13T19:29:41 Z |
Lawliet |
Semafor (COI20_semafor) |
C++17 |
|
252 ms |
1144 KB |
#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[] = { 0 , 2 , 9 , 7 , 18 , 21 , 12 , 3 , 29 , 23 , 10 };
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
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
1024 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
1024 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
242 ms |
1144 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
252 ms |
1144 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
252 ms |
1144 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
242 ms |
1144 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |