You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
60 lines
1.5 KiB
C++
60 lines
1.5 KiB
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
typedef long long mat[6][6];
|
|
const int mod = 123456789;
|
|
const size_t sz = sizeof(long long) * 36;
|
|
void mul(mat a, mat b)
|
|
{
|
|
mat c;
|
|
memset(c, 0, sz);
|
|
for (int i = 0; i < 6; i++)
|
|
for (int j = 0; j < 6; j++)
|
|
for (int k = 0; k < 6; k++)
|
|
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
|
|
memcpy(a, c, sz);
|
|
}
|
|
void fpow(mat ret, mat a, long long b)
|
|
{
|
|
memset(ret, 0, sz);
|
|
for (int i = 0; i < 6; i++) ret[i][i] = 1;
|
|
for (; b; b >>= 1, mul(a, a))
|
|
if (b & 1)
|
|
mul(ret, a);
|
|
}
|
|
int main()
|
|
{
|
|
int T;
|
|
long long n;
|
|
scanf("%d", &T);
|
|
while (T--)
|
|
{
|
|
scanf("%lld", &n);
|
|
if (n <= 2)
|
|
printf("%lld\n", n);
|
|
else
|
|
{
|
|
mat b = {
|
|
{1, 0, 0, 0, 0, 0},
|
|
{2, 0, 0, 0, 0, 0},
|
|
{8, 0, 0, 0, 0, 0},
|
|
{4, 0, 0, 0, 0, 0},
|
|
{2, 0, 0, 0, 0, 0},
|
|
{1, 0, 0, 0, 0, 0}};
|
|
mat a = {
|
|
{0, 1, 0, 0, 0, 0},
|
|
{2, 1, 1, 3, 3, 1},
|
|
{0, 0, 1, 3, 3, 1},
|
|
{0, 0, 0, 1, 2, 1},
|
|
{0, 0, 0, 0, 1, 1},
|
|
{0, 0, 0, 0, 0, 1}};
|
|
mat ret;
|
|
fpow(ret, a, n - 2);
|
|
mul(ret, b);
|
|
printf("%lld\n", ret[1][0]);
|
|
}
|
|
}
|
|
return 0;
|
|
}
|