QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #314857 | #8173. T Tile Placement Counting | ucup-team1447# | AC ✓ | 247ms | 3880kb | C++14 | 22.4kb | 2024-01-26 13:25:49 | 2024-01-26 13:25:50 |
Judging History
answer
// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
const int MOD = 998244353;
struct mint
{
unsigned v;
mint(unsigned v = 0) : v(v) {}
mint operator-() const { return v ? MOD - v : v; }
mint &operator+=(const mint &X) { return (v += X.v) >= MOD ? v -= MOD : v, *this; }
mint &operator-=(const mint &X) { return (v += MOD - X.v) >= MOD ? v -= MOD : v, *this; }
mint &operator*=(const mint &X) { return v = 1llu * v * X.v % MOD, *this; }
mint &operator/=(const mint &X) { return *this *= X.inv(); }
mint pow(long long B) const
{
B %= MOD - 1;
if (B < 0)
B += MOD - 1;
mint res = 1, A = *this;
while (B)
{
if (B & 1)
res *= A;
B >>= 1;
A *= A;
}
return res;
}
mint inv() const { return pow(MOD - 2); }
friend mint operator+(const mint &A, const mint &B) { return mint(A) += B; }
friend mint operator-(const mint &A, const mint &B) { return mint(A) -= B; }
friend mint operator*(const mint &A, const mint &B) { return mint(A) *= B; }
friend mint operator/(const mint &A, const mint &B) { return mint(A) /= B; }
friend std::istream &operator>>(std::istream &A, mint &B) { return A >> B.v; }
friend std::ostream &operator<<(std::ostream &A, const mint &B) { return A << B.v; }
explicit operator bool() const { return v; }
friend bool operator==(const mint &A, const mint &B) { return A.v == B.v; }
} ans[10005];
std::map<std::pair<int, int>, mint> dp[2];
bool now = true, lst = false;
int n;
long long m;
std::vector<mint> BM(const std::vector<mint> &x)
{
std::vector<mint> cur(1), lst(1);
cur[0] = lst[0] = 1;
int lp = 0;
mint lt = 0;
for (int i = 0; i < (int)x.size(); ++i)
{
mint t = 0;
for (int j = 0; j < (int)cur.size(); ++j)
{
t += x[i - j] * cur[j];
}
if (t == 0)
continue;
if ((int)cur.size() == 1)
{
cur.resize(i + 2);
lp = i, lt = t;
continue;
}
mint tmp = -t / lt;
std::vector<mint> c(i - lp);
for (mint v : lst)
c.push_back(tmp * v);
if (c.size() < cur.size())
c.resize(cur.size());
else
lst = cur, lp = i, lt = t;
for (int j = 0; j < (int)cur.size(); ++j)
c[j] += cur[j];
cur = c;
}
return cur;
}
std::vector<mint> mul(const std::vector<mint> &A, const std::vector<mint> &B, const std::vector<mint> &C)
{
std::vector<mint> res(A.size() + B.size() - 1);
for (std::size_t i = 0; i != A.size(); ++i)
for (std::size_t j = 0; j != B.size(); ++j)
res[i + j] += A[i] * B[j];
while (res.size() >= C.size())
{
mint v = res.back() / C.back();
for (std::size_t i = 1; i <= C.size(); ++i)
res.end()[-i] -= v * C.end()[-i];
res.pop_back();
}
return res;
}
std::vector<mint> power(std::vector<mint> A, long long B, std::vector<mint> C)
{
std::vector<mint> res = {1};
while (B)
{
if (B & 1)
res = mul(res, A, C);
A = mul(A, A, C);
B >>= 1;
}
return res;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin >> n >> m;
if (n > 0)
{
if (n == 4)
{
std::vector<mint> F = {1, 0, 0, 0, 2, 0};
std::vector<mint> G = {0, 998244350, 0, 0, 0, 1};
std::vector<mint> H = power({0, 1}, m, G);
mint res = 0;
for (std::size_t i = 0; i != H.size(); ++i)
res += H[i] * F[i];
std::cout << res << std::endl;
}
else if (n == 8)
{
std::vector<mint> F = {1, 0, 0, 0, 6, 0, 0, 0, 84, 0};
std::vector<mint> G = {0, 27, 0, 0, 0, 998244337, 0, 0, 0, 1};
std::vector<mint> H = power({0, 1}, m, G);
mint res = 0;
for (std::size_t i = 0; i != H.size(); ++i)
res += H[i] * F[i];
std::cout << res << std::endl;
}
else if (n == 12)
{
std::vector<mint> F = {1, 0, 0, 0, 18, 0, 0, 0, 1182, 0, 0, 0, 78696, 0, 0, 0, 5253822, 0};
std::vector<mint> G = {0, 6561, 0, 0, 0, 998238170, 0, 0, 0, 1440, 0, 0, 0, 998244266, 0, 0, 0, 1};
std::vector<mint> H = power({0, 1}, m, G);
mint res = 0;
for (std::size_t i = 0; i != H.size(); ++i)
res += H[i] * F[i];
std::cout << res << std::endl;
}
else if (n == 16)
{
std::vector<mint> F = {1, 0, 0, 0, 54, 0, 0, 0, 16644, 0, 0, 0, 5253822, 0, 0, 0, 669847183, 0, 0, 0, 386282067, 0, 0, 0, 157705668, 0, 0, 0, 324635103, 0, 0, 0, 664730403, 0, 0, 0, 590548248, 0, 0, 0, 718440881, 0};
std::vector<mint> G = {0, 777398099, 0, 0, 0, 993042623, 0, 0, 0, 872103036, 0, 0, 0, 220412365, 0, 0, 0, 787564831, 0, 0, 0, 12637412, 0, 0, 0, 204075342, 0, 0, 0, 992505153, 0, 0, 0, 82899, 0, 0, 0, 998243825, 0, 0, 0, 1};
std::vector<mint> H = power({0, 1}, m, G);
mint res = 0;
for (std::size_t i = 0; i != H.size(); ++i)
res += H[i] * F[i];
std::cout << res << std::endl;
}
else if (n == 20)
{
std::vector<mint> F = {1, 0, 0, 0, 162, 0, 0, 0, 234390, 0, 0, 0, 350950482, 0, 0, 0, 386282067, 0, 0, 0, 205367370, 0, 0, 0, 255040961, 0, 0, 0, 69335800, 0, 0, 0, 674099389, 0, 0, 0, 175409900, 0, 0, 0, 230058619, 0, 0, 0, 339713735, 0, 0, 0, 331852207, 0, 0, 0, 320637159, 0, 0, 0, 52920411, 0, 0, 0, 597074996, 0, 0, 0, 134213796, 0, 0, 0, 72615600, 0, 0, 0, 419434807, 0, 0, 0, 336803919, 0, 0, 0, 650878305, 0, 0, 0, 392233640, 0, 0, 0, 920770685, 0, 0, 0, 606525473, 0, 0, 0, 447023422, 0, 0, 0, 359314458, 0, 0, 0, 126883463, 0};
std::vector<mint> G = {0, 45859325, 0, 0, 0, 285953640, 0, 0, 0, 362764437, 0, 0, 0, 83805446, 0, 0, 0, 449193509, 0, 0, 0, 19853701, 0, 0, 0, 919781370, 0, 0, 0, 691261093, 0, 0, 0, 950476435, 0, 0, 0, 850853084, 0, 0, 0, 738550348, 0, 0, 0, 895774127, 0, 0, 0, 690599068, 0, 0, 0, 819847271, 0, 0, 0, 960371162, 0, 0, 0, 966586332, 0, 0, 0, 782394099, 0, 0, 0, 308246889, 0, 0, 0, 337564622, 0, 0, 0, 790390483, 0, 0, 0, 572890332, 0, 0, 0, 120873888, 0, 0, 0, 431818412, 0, 0, 0, 604388611, 0, 0, 0, 3831360, 0, 0, 0, 998241126, 0, 0, 0, 1};
std::vector<mint> H = power({0, 1}, m, G);
mint res = 0;
for (std::size_t i = 0; i != H.size(); ++i)
res += H[i] * F[i];
std::cout << res << std::endl;
}
else if (n == 24)
{
std::vector<mint> F = {1, 0, 0, 0, 486, 0, 0, 0, 3300852, 0, 0, 0, 486390401, 0, 0, 0, 157705668, 0, 0, 0, 255040961, 0, 0, 0, 270067615, 0, 0, 0, 890091610, 0, 0, 0, 989425911, 0, 0, 0, 102959090, 0, 0, 0, 332786435, 0, 0, 0, 7344551, 0, 0, 0, 407542708, 0, 0, 0, 740090735, 0, 0, 0, 792716305, 0, 0, 0, 972768743, 0, 0, 0, 929945472, 0, 0, 0, 552042418, 0, 0, 0, 528849708, 0, 0, 0, 241351746, 0, 0, 0, 145812033, 0, 0, 0, 362307018, 0, 0, 0, 770413105, 0, 0, 0, 132137727, 0, 0, 0, 965675567, 0, 0, 0, 437111021, 0, 0, 0, 393854140, 0, 0, 0, 154806537, 0, 0, 0, 520666325, 0, 0, 0, 758511492, 0, 0, 0, 63190804, 0, 0, 0, 997761380, 0, 0, 0, 68775801, 0, 0, 0, 983862923, 0, 0, 0, 348139782, 0, 0, 0, 601697518, 0, 0, 0, 694773102, 0, 0, 0, 262099573, 0, 0, 0, 323944493, 0, 0, 0, 242942457, 0, 0, 0, 577899150, 0, 0, 0, 459307391, 0, 0, 0, 141608461, 0, 0, 0, 687954833, 0, 0, 0, 67838204, 0, 0, 0, 445862587, 0, 0, 0, 552128591, 0, 0, 0, 191163345, 0, 0, 0, 150617231, 0, 0, 0, 864930342, 0, 0, 0, 482426583, 0, 0, 0, 992917425, 0, 0, 0, 948564843, 0, 0, 0, 770280173, 0, 0, 0, 502861291, 0, 0, 0, 640241744, 0, 0, 0, 996999147, 0, 0, 0, 459196583, 0, 0, 0, 903737659, 0, 0, 0, 179597071, 0, 0, 0, 334992270, 0, 0, 0, 602412103, 0, 0, 0, 935447114, 0, 0, 0, 683452878, 0, 0, 0, 576044932, 0, 0, 0, 579934613, 0, 0, 0, 498682083, 0, 0, 0, 787773343, 0, 0, 0, 762519279, 0, 0, 0, 947571943, 0, 0, 0, 712066540, 0, 0, 0, 467225835, 0, 0, 0, 9689671, 0, 0, 0, 129498453, 0, 0, 0, 53472868, 0, 0, 0, 779012096, 0, 0, 0, 195925896, 0, 0, 0, 708593523, 0, 0, 0, 107836848, 0, 0, 0, 550584296, 0, 0, 0, 59298190, 0, 0, 0, 251935884, 0, 0};
std::vector<mint> G = {0, 297786270, 0, 0, 0, 988817875, 0, 0, 0, 389595163, 0, 0, 0, 248913314, 0, 0, 0, 916246371, 0, 0, 0, 991141013, 0, 0, 0, 674879494, 0, 0, 0, 675721278, 0, 0, 0, 39406199, 0, 0, 0, 647340492, 0, 0, 0, 69897769, 0, 0, 0, 424427266, 0, 0, 0, 913569308, 0, 0, 0, 508224026, 0, 0, 0, 971240503, 0, 0, 0, 123396717, 0, 0, 0, 102482762, 0, 0, 0, 244478689, 0, 0, 0, 87504416, 0, 0, 0, 835902070, 0, 0, 0, 957107177, 0, 0, 0, 126956420, 0, 0, 0, 442857742, 0, 0, 0, 393130953, 0, 0, 0, 139466916, 0, 0, 0, 692160967, 0, 0, 0, 686120186, 0, 0, 0, 733143858, 0, 0, 0, 757089645, 0, 0, 0, 630426532, 0, 0, 0, 263019463, 0, 0, 0, 934121709, 0, 0, 0, 492094822, 0, 0, 0, 361493065, 0, 0, 0, 343620802, 0, 0, 0, 128011953, 0, 0, 0, 858464746, 0, 0, 0, 46079951, 0, 0, 0, 390446097, 0, 0, 0, 19054848, 0, 0, 0, 752046112, 0, 0, 0, 191827828, 0, 0, 0, 804351704, 0, 0, 0, 638556303, 0, 0, 0, 16320531, 0, 0, 0, 165152784, 0, 0, 0, 363578923, 0, 0, 0, 327606699, 0, 0, 0, 77129466, 0, 0, 0, 633509905, 0, 0, 0, 784676356, 0, 0, 0, 225158203, 0, 0, 0, 121519287, 0, 0, 0, 866868977, 0, 0, 0, 806610547, 0, 0, 0, 764320369, 0, 0, 0, 459091109, 0, 0, 0, 652200745, 0, 0, 0, 780172842, 0, 0, 0, 514479221, 0, 0, 0, 232728150, 0, 0, 0, 591954646, 0, 0, 0, 712477759, 0, 0, 0, 851649414, 0, 0, 0, 63428495, 0, 0, 0, 684004259, 0, 0, 0, 330922562, 0, 0, 0, 840555884, 0, 0, 0, 134402891, 0, 0, 0, 562998721, 0, 0, 0, 924510885, 0, 0, 0, 301116831, 0, 0, 0, 482692269, 0, 0, 0, 612216198, 0, 0, 0, 193710006, 0, 0, 0, 998222993, 0, 0, 0, 1};
std::vector<mint> H = power({0, 1}, m, G);
mint res = 0;
for (std::size_t i = 0; i != H.size(); ++i)
res += H[i] * F[i];
std::cout << res << std::endl;
}
else if (n == 28)
{
std::vector<mint> F = {1, 0, 0, 0, 1458, 0, 0, 0, 46485102, 0, 0, 0, 156888273, 0, 0, 0, 324635103, 0, 0, 0, 69335800, 0, 0, 0, 890091610, 0, 0, 0, 524120255, 0, 0, 0, 410842735, 0, 0, 0, 604774367, 0, 0, 0, 333642960, 0, 0, 0, 253967953, 0, 0, 0, 735298387, 0, 0, 0, 959647355, 0, 0, 0, 71320846, 0, 0, 0, 584013059, 0, 0, 0, 398542755, 0, 0, 0, 106060719, 0, 0, 0, 648301890, 0, 0, 0, 386812262, 0, 0, 0, 868018307, 0, 0, 0, 424953977, 0, 0, 0, 711033721, 0, 0, 0, 34094521, 0, 0, 0, 364601234, 0, 0, 0, 821612342, 0, 0, 0, 175909022, 0, 0, 0, 439617221, 0, 0, 0, 930911053, 0, 0, 0, 147554697, 0, 0, 0, 253448742, 0, 0, 0, 518078171, 0, 0, 0, 957480805, 0, 0, 0, 805410011, 0, 0, 0, 68489461, 0, 0, 0, 686764013, 0, 0, 0, 589615784, 0, 0, 0, 798447325, 0, 0, 0, 322145279, 0, 0, 0, 7292124, 0, 0, 0, 422372454, 0, 0, 0, 849050588, 0, 0, 0, 910870868, 0, 0, 0, 818753179, 0, 0, 0, 558443213, 0, 0, 0, 681341253, 0, 0, 0, 193737446, 0, 0, 0, 693240993, 0, 0, 0, 739631694, 0, 0, 0, 487282911, 0, 0, 0, 66898937, 0, 0, 0, 331066730, 0, 0, 0, 703600081, 0, 0, 0, 725531435, 0, 0, 0, 865239733, 0, 0, 0, 913157863, 0, 0, 0, 587650776, 0, 0, 0, 785848464, 0, 0, 0, 499179779, 0, 0, 0, 625873985, 0, 0, 0, 820104575, 0, 0, 0, 218485525, 0, 0, 0, 891109047, 0, 0, 0, 860612197, 0, 0, 0, 564414541, 0, 0, 0, 693839047, 0, 0, 0, 30601791, 0, 0, 0, 971466361, 0, 0, 0, 448560823, 0, 0, 0, 84100127, 0, 0, 0, 156415581, 0, 0, 0, 496344830, 0, 0, 0, 53299932, 0, 0, 0, 13333233, 0, 0, 0, 931008007, 0, 0, 0, 549118027, 0, 0, 0, 176279229, 0, 0, 0, 988931569, 0, 0, 0, 8485168, 0, 0, 0, 312179976, 0, 0, 0, 331026319, 0, 0, 0, 74610696, 0, 0, 0, 760896689, 0, 0, 0, 933163816, 0, 0, 0, 480868635, 0, 0, 0, 280690807, 0, 0, 0, 309222227, 0, 0, 0, 753802054, 0, 0, 0, 255700086, 0, 0, 0, 991937084, 0, 0, 0, 253510097, 0, 0, 0, 560952868, 0, 0, 0, 94628719, 0, 0, 0, 346608999, 0, 0, 0, 616631849, 0, 0, 0, 522863046, 0, 0, 0, 712464502, 0, 0, 0, 980522948, 0, 0, 0, 765579874, 0, 0, 0, 149280267, 0, 0, 0, 134310828, 0, 0, 0, 494182802, 0, 0, 0, 315811762, 0, 0, 0, 17115403, 0, 0, 0, 395160410, 0, 0, 0, 934686561, 0, 0, 0, 747137345, 0, 0, 0, 597683182, 0, 0, 0, 74835132, 0, 0, 0, 50815459, 0, 0, 0, 469763667, 0, 0, 0, 561862855, 0, 0, 0, 129299672, 0, 0, 0, 29398618, 0, 0, 0, 197480386, 0, 0, 0, 702244608, 0, 0, 0, 193479437, 0, 0, 0, 8054810, 0, 0, 0, 125145730, 0, 0, 0, 508258295, 0, 0, 0, 846068964, 0, 0, 0, 102815320, 0, 0, 0, 121465873, 0, 0, 0, 892834621, 0, 0, 0, 103712558, 0, 0, 0, 254465072, 0, 0, 0, 160281121, 0, 0, 0, 910377354, 0, 0, 0, 499970306, 0, 0, 0, 621322226, 0, 0, 0, 116223741, 0, 0, 0, 549391523, 0, 0, 0, 993707944, 0, 0, 0, 800119598, 0, 0, 0, 691049371, 0, 0, 0, 717887813, 0, 0, 0, 228866127, 0, 0, 0, 410104903, 0, 0, 0, 579751958, 0, 0, 0, 105186981, 0, 0, 0, 976793495, 0, 0, 0, 703277130, 0, 0, 0, 375470116, 0, 0, 0, 615024592, 0, 0, 0, 199049485, 0, 0, 0, 721753688, 0, 0, 0, 228958147, 0, 0, 0, 745972008, 0, 0, 0, 798270211, 0, 0, 0, 852561995, 0, 0, 0, 369163572, 0, 0, 0, 655715189, 0, 0, 0, 393415634, 0, 0, 0, 353571692, 0, 0, 0, 947898984, 0, 0, 0, 215896495, 0, 0, 0, 344592926, 0, 0, 0, 951376343, 0, 0, 0, 204060956, 0, 0, 0, 730659100, 0, 0, 0, 685530599, 0, 0, 0, 388145601, 0, 0, 0, 907379287, 0, 0, 0, 823829674, 0, 0, 0, 31921450, 0, 0, 0, 514321952, 0, 0, 0, 787814765, 0, 0, 0, 595082627, 0, 0, 0, 497213702, 0, 0, 0, 808395329, 0, 0, 0, 444643234, 0, 0, 0, 441080923, 0, 0, 0, 149401829, 0, 0, 0, 23602687, 0, 0, 0, 822327776, 0, 0, 0, 397415911, 0, 0, 0, 746005726, 0, 0, 0, 785253790, 0, 0, 0, 42635785, 0, 0, 0, 109022692, 0, 0, 0, 33135122, 0, 0, 0, 828129646, 0, 0, 0, 468566185, 0, 0, 0, 444983448, 0, 0, 0, 575021409, 0, 0, 0, 274387744, 0, 0, 0, 21760636, 0, 0, 0, 703654205, 0, 0, 0, 609493910, 0, 0, 0, 521176631, 0, 0, 0, 147201028, 0, 0, 0, 918692434, 0, 0, 0, 70178467, 0, 0, 0, 952248631, 0, 0, 0, 426547946, 0, 0, 0, 613444324, 0, 0, 0, 246321271, 0, 0, 0, 127138660, 0, 0, 0, 457098071, 0, 0, 0, 402764485, 0, 0, 0, 310289413, 0, 0, 0, 153943717, 0, 0, 0, 85919774, 0, 0, 0, 836559099, 0, 0, 0, 710767197, 0, 0, 0, 101480076, 0, 0, 0, 593014560, 0, 0, 0, 276397482, 0, 0, 0, 335840279, 0, 0, 0, 964154470, 0, 0, 0, 563411227, 0, 0, 0, 93985492, 0, 0, 0, 324030375, 0, 0, 0, 404188947, 0, 0, 0, 14826357, 0, 0, 0, 55330559, 0, 0, 0, 587588116, 0, 0, 0, 330755671, 0, 0, 0, 265317281, 0, 0, 0, 392993444, 0, 0, 0, 681874617, 0, 0, 0, 703319126, 0, 0, 0, 36738553, 0, 0, 0, 419503315, 0, 0, 0, 27138776, 0, 0, 0, 17809049, 0, 0, 0, 414850394, 0, 0, 0, 41302148, 0, 0, 0, 881561763, 0, 0, 0, 692751472, 0, 0, 0, 61135397, 0, 0, 0, 285133250, 0, 0, 0, 906182971, 0};
std::vector<mint> G = {1, 0, 0, 0, 998100530, 0, 0, 0, 492495255, 0, 0, 0, 874041654, 0, 0, 0, 505978013, 0, 0, 0, 231566553, 0, 0, 0, 689099760, 0, 0, 0, 92797550, 0, 0, 0, 602703122, 0, 0, 0, 30977309, 0, 0, 0, 959488441, 0, 0, 0, 932837958, 0, 0, 0, 479529203, 0, 0, 0, 343674754, 0, 0, 0, 803770840, 0, 0, 0, 538467951, 0, 0, 0, 756683302, 0, 0, 0, 1273862, 0, 0, 0, 333410736, 0, 0, 0, 107788459, 0, 0, 0, 76086116, 0, 0, 0, 506390067, 0, 0, 0, 847190348, 0, 0, 0, 432857366, 0, 0, 0, 549719976, 0, 0, 0, 657956183, 0, 0, 0, 500004064, 0, 0, 0, 345761718, 0, 0, 0, 9892621, 0, 0, 0, 57948247, 0, 0, 0, 542775967, 0, 0, 0, 121170535, 0, 0, 0, 718479386, 0, 0, 0, 323281581, 0, 0, 0, 720333492, 0, 0, 0, 580472901, 0, 0, 0, 656679159, 0, 0, 0, 306454645, 0, 0, 0, 330509570, 0, 0, 0, 515394720, 0, 0, 0, 643282100, 0, 0, 0, 333490106, 0, 0, 0, 29741971, 0, 0, 0, 406767094, 0, 0, 0, 302162029, 0, 0, 0, 922963449, 0, 0, 0, 706895452, 0, 0, 0, 294852234, 0, 0, 0, 736333174, 0, 0, 0, 267843491, 0, 0, 0, 848221733, 0, 0, 0, 686614658, 0, 0, 0, 736158144, 0, 0, 0, 975848407, 0, 0, 0, 524572160, 0, 0, 0, 545335443, 0, 0, 0, 303884214, 0, 0, 0, 557885586, 0, 0, 0, 704873039, 0, 0, 0, 810322619, 0, 0, 0, 562228932, 0, 0, 0, 13306417, 0, 0, 0, 512012112, 0, 0, 0, 104579822, 0, 0, 0, 850744881, 0, 0, 0, 185670188, 0, 0, 0, 422062259, 0, 0, 0, 259330201, 0, 0, 0, 581672267, 0, 0, 0, 327380739, 0, 0, 0, 181781033, 0, 0, 0, 970670259, 0, 0, 0, 854691230, 0, 0, 0, 112730126, 0, 0, 0, 458233573, 0, 0, 0, 171810708, 0, 0, 0, 518193591, 0, 0, 0, 280112774, 0, 0, 0, 562970886, 0, 0, 0, 598259272, 0, 0, 0, 716485905, 0, 0, 0, 343375432, 0, 0, 0, 147705010, 0, 0, 0, 342603661, 0, 0, 0, 823777227, 0, 0, 0, 544147561, 0, 0, 0, 154494740, 0, 0, 0, 652534925, 0, 0, 0, 788804183, 0, 0, 0, 122128904, 0, 0, 0, 255183511, 0, 0, 0, 258546497, 0, 0, 0, 220995694, 0, 0, 0, 664137437, 0, 0, 0, 361433915, 0, 0, 0, 875084425, 0, 0, 0, 705255994, 0, 0, 0, 444712214, 0, 0, 0, 135380935, 0, 0, 0, 580861340, 0, 0, 0, 617101322, 0, 0, 0, 57414311, 0, 0, 0, 512682638, 0, 0, 0, 352820127, 0, 0, 0, 190245318, 0, 0, 0, 173305358, 0, 0, 0, 446922654, 0, 0, 0, 710591337, 0, 0, 0, 494488143, 0, 0, 0, 963885293, 0, 0, 0, 80881273, 0, 0, 0, 232105555, 0, 0, 0, 522160087, 0, 0, 0, 772250426, 0, 0, 0, 715499973, 0, 0, 0, 725330337, 0, 0, 0, 900279005, 0, 0, 0, 975224038, 0, 0, 0, 275515910, 0, 0, 0, 769232788, 0, 0, 0, 462047920, 0, 0, 0, 759120975, 0, 0, 0, 807338008, 0, 0, 0, 326089097, 0, 0, 0, 40687220, 0, 0, 0, 487023620, 0, 0, 0, 370242606, 0, 0, 0, 480193473, 0, 0, 0, 947836646, 0, 0, 0, 396458448, 0, 0, 0, 549983794, 0, 0, 0, 518832022, 0, 0, 0, 405486010, 0, 0, 0, 783731928, 0, 0, 0, 880123083, 0, 0, 0, 915808312, 0, 0, 0, 537813522, 0, 0, 0, 447749109, 0, 0, 0, 683681469, 0, 0, 0, 621725128, 0, 0, 0, 355197890, 0, 0, 0, 291257079, 0, 0, 0, 158670721, 0, 0, 0, 935004298, 0, 0, 0, 202815858, 0, 0, 0, 662373348, 0, 0, 0, 568161339, 0, 0, 0, 609019953, 0, 0, 0, 257603811, 0, 0, 0, 136117388, 0, 0, 0, 205719601, 0, 0, 0, 943260697, 0, 0, 0, 705144515, 0, 0, 0, 13543624, 0, 0, 0, 811439571, 0, 0, 0, 419678640, 0, 0, 0, 866820658, 0, 0, 0, 589963278, 0, 0, 0, 24907387, 0, 0, 0, 389437811, 0, 0, 0, 227099027, 0, 0, 0, 557020888, 0, 0, 0, 9615136, 0, 0, 0, 918908605, 0, 0, 0, 769568293, 0, 0, 0, 739641785, 0, 0, 0, 867173606, 0, 0, 0, 623658154, 0, 0, 0, 548909573, 0, 0, 0, 396524980, 0, 0, 0, 609541382, 0, 0, 0, 977284391, 0, 0, 0, 843121017, 0, 0, 0, 933917328, 0, 0, 0, 290947981, 0, 0, 0, 67826953, 0, 0, 0, 622316983, 0, 0, 0, 781112456, 0, 0, 0, 858294404, 0, 0, 0, 398614684, 0, 0, 0, 386750697, 0, 0, 0, 679921984, 0, 0, 0, 336766738, 0, 0, 0, 74937765, 0, 0, 0, 596717700, 0, 0, 0, 836732117, 0, 0, 0, 474686887, 0, 0, 0, 451386249, 0, 0, 0, 996221494, 0, 0, 0, 87077792, 0, 0, 0, 647572279, 0, 0, 0, 76540497, 0, 0, 0, 974474530, 0, 0, 0, 709002339, 0, 0, 0, 520417139, 0, 0, 0, 9245961, 0, 0, 0, 629257802, 0, 0, 0, 756107541, 0, 0, 0, 589134344, 0, 0, 0, 237892972, 0, 0, 0, 25525940, 0, 0, 0, 416080263, 0, 0, 0, 934016471, 0, 0, 0, 364638897, 0, 0, 0, 988418724, 0, 0, 0, 938571667, 0, 0, 0, 474535258, 0, 0, 0, 662713435, 0, 0, 0, 30277062, 0, 0, 0, 29156947, 0, 0, 0, 642460896, 0, 0, 0, 818465978, 0, 0, 0, 899840515, 0, 0, 0, 272319990, 0, 0, 0, 343212927, 0, 0, 0, 637272706, 0, 0, 0, 727160519, 0, 0, 0, 803164190, 0, 0, 0, 701938844, 0, 0, 0, 769604453, 0, 0, 0, 365533672, 0, 0, 0, 667688482, 0, 0, 0, 687387972, 0, 0, 0, 929297380, 0, 0, 0, 680558201, 0, 0, 0, 160363042, 0, 0, 0, 137701990, 0, 0, 0, 452532931, 0, 0, 0, 43151729, 0, 0, 0, 957221459, 0, 0, 0, 259813373, 0, 0, 0, 335317399, 0, 0, 0, 930540249, 0};
std::reverse(G.begin(), G.end());
std::vector<mint> H = power({0, 1}, m, G);
mint res = 0;
for (std::size_t i = 0; i != H.size(); ++i)
res += H[i] * F[i];
std::cout << res << std::endl;
}
else
std::cout << 0 << std::endl;
return 0;
}
dp[now][{0, 0}] = 1;
for (int i = 0; i <= m; ++i)
{
if (dp[now].count({0, 0}))
ans[i] = dp[now][{0, 0}];
for (int j = 0; j != n; ++j)
{
std::swap(now, lst);
dp[now].clear();
for (auto k : dp[lst])
{
std::pair<int, int> h = k.first;
mint v = k.second;
// if (j == 0)
// {
// std::cout << std::bitset<4>(h.first) << std::endl;
// std::cout << std::bitset<4>(h.second) << std::endl;
// std::cout << v << std::endl;
// }
if (h.first >> j & 1)
dp[now][{(h.first & ~(1 << j)) | (h.second & 1 << j), h.second & ~(1 << j)}] += v;
else
{
h.first &= ~(1 << j);
h.first |= h.second & 1 << j;
h.second &= ~(1 << j);
if (j && ~h.first >> j & 1 && ~h.first >> (j - 1) & 1)
dp[now][{h.first | 1 << j | 1 << (j - 1), h.second | 1 << j}] += v;
if (j + 1 < n && ~h.first >> j & 1 && ~h.second >> (j + 1) & 1)
dp[now][{h.first | 1 << j, h.second | 1 << j | 1 << (j + 1)}] += v;
if (j + 2 < n && ~h.first >> (j + 1) & 1 && ~h.first >> (j + 2) & 1 && ~h.second >> (j + 1) & 1)
dp[now][{h.first | 1 << (j + 1) | 1 << (j + 2), h.second | 1 << (j + 1)}] += v;
if (j && j + 1 < n && ~h.first >> (j - 1) & 1 && ~h.first >> j & 1 && ~h.second >> (j + 1) & 1)
dp[now][{h.first | 1 << (j - 1) | 1 << j, h.second | 1 << (j + 1)}] += v;
}
}
}
std::vector<mint> tmp = BM(std::vector<mint>(ans, ans + i + 1));
std::cout << i << ' ' << tmp.size() << std::endl;
if (i % 100 == 0)
{
std::ofstream fout("data.out");
for (std::size_t i = 0; i != tmp.size(); ++i)
fout << ans[i] << ',';
fout << std::endl;
for (std::size_t i = 0; i != tmp.size(); ++i)
fout << tmp[i] << ',';
fout << std::endl;
fout.close();
}
}
std::vector<mint> G = BM(std::vector<mint>(ans, ans + m + 1));
std::reverse(G.begin(), G.end());
std::vector<mint> H = power({0, 1}, m, G);
mint res = 0;
for (std::size_t i = 0; i != H.size(); ++i)
res += H[i] * ans[i];
std::cout << res << std::endl;
for (std::size_t i = 0; i != G.size(); ++i)
std::cout << ans[i] << ',';
std::cout << std::endl;
for (auto i : G)
std::cout << i << ',';
std::cout << std::endl;
std::cout << G.size() << std::endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3672kb
input:
4 4
output:
2
result:
ok "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
2 8
output:
0
result:
ok "0"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
12 3456
output:
491051233
result:
ok "491051233"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
1 1
output:
0
result:
ok "0"
Test #5:
score: 0
Accepted
time: 5ms
memory: 3676kb
input:
20 999999999999999983
output:
0
result:
ok "0"
Test #6:
score: 0
Accepted
time: 26ms
memory: 3688kb
input:
24 999999999999999994
output:
0
result:
ok "0"
Test #7:
score: 0
Accepted
time: 26ms
memory: 3672kb
input:
24 999999999999999955
output:
0
result:
ok "0"
Test #8:
score: 0
Accepted
time: 205ms
memory: 3636kb
input:
28 999999999999999928
output:
846645622
result:
ok "846645622"
Test #9:
score: 0
Accepted
time: 204ms
memory: 3868kb
input:
28 999999999999999971
output:
0
result:
ok "0"
Test #10:
score: 0
Accepted
time: 209ms
memory: 3700kb
input:
28 999999999999999901
output:
0
result:
ok "0"
Test #11:
score: 0
Accepted
time: 206ms
memory: 3844kb
input:
28 999999999999999945
output:
0
result:
ok "0"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
30 1000000000000000000
output:
0
result:
ok "0"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
4 144115188075855868
output:
479168365
result:
ok "479168365"
Test #14:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
4 288230376151711740
output:
661413713
result:
ok "661413713"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
4 576460752303423484
output:
854857972
result:
ok "854857972"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3684kb
input:
8 144115188075855868
output:
266363233
result:
ok "266363233"
Test #17:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
8 288230376151711740
output:
862901307
result:
ok "862901307"
Test #18:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
8 576460752303423484
output:
455991900
result:
ok "455991900"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
12 144115188075855868
output:
226857121
result:
ok "226857121"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
12 288230376151711740
output:
717445399
result:
ok "717445399"
Test #21:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
12 576460752303423484
output:
935277864
result:
ok "935277864"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
16 144115188075855868
output:
631950327
result:
ok "631950327"
Test #23:
score: 0
Accepted
time: 1ms
memory: 3824kb
input:
16 288230376151711740
output:
73767413
result:
ok "73767413"
Test #24:
score: 0
Accepted
time: 2ms
memory: 3660kb
input:
16 576460752303423484
output:
329402693
result:
ok "329402693"
Test #25:
score: 0
Accepted
time: 5ms
memory: 3880kb
input:
20 144115188075855868
output:
125405814
result:
ok "125405814"
Test #26:
score: 0
Accepted
time: 5ms
memory: 3672kb
input:
20 288230376151711740
output:
794579293
result:
ok "794579293"
Test #27:
score: 0
Accepted
time: 5ms
memory: 3608kb
input:
20 576460752303423484
output:
726571847
result:
ok "726571847"
Test #28:
score: 0
Accepted
time: 30ms
memory: 3672kb
input:
24 144115188075855868
output:
310529292
result:
ok "310529292"
Test #29:
score: 0
Accepted
time: 31ms
memory: 3688kb
input:
24 288230376151711740
output:
493789216
result:
ok "493789216"
Test #30:
score: 0
Accepted
time: 30ms
memory: 3636kb
input:
24 576460752303423484
output:
606221157
result:
ok "606221157"
Test #31:
score: 0
Accepted
time: 239ms
memory: 3696kb
input:
28 144115188075855868
output:
964541053
result:
ok "964541053"
Test #32:
score: 0
Accepted
time: 245ms
memory: 3868kb
input:
28 288230376151711740
output:
42971353
result:
ok "42971353"
Test #33:
score: 0
Accepted
time: 247ms
memory: 3864kb
input:
28 576460752303423484
output:
179569141
result:
ok "179569141"
Test #34:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
6 5
output:
0
result:
ok "0"
Test #35:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
14 28
output:
0
result:
ok "0"
Test #36:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
25 6365
output:
0
result:
ok "0"
Test #37:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
18 529543996
output:
0
result:
ok "0"
Test #38:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
10 675199829716849556
output:
0
result:
ok "0"
Test #39:
score: 0
Accepted
time: 4ms
memory: 3820kb
input:
20 425279816112802872
output:
269059955
result:
ok "269059955"
Test #40:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
8 38212554426330756
output:
207344318
result:
ok "207344318"
Test #41:
score: 0
Accepted
time: 23ms
memory: 3692kb
input:
24 666881067086698696
output:
245351821
result:
ok "245351821"
Test #42:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
4 728683474913510792
output:
466882081
result:
ok "466882081"
Test #43:
score: 0
Accepted
time: 178ms
memory: 3632kb
input:
28 201838304882525604
output:
217184228
result:
ok "217184228"
Test #44:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4 8560
output:
596875387
result:
ok "596875387"
Test #45:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
12 60764
output:
930662011
result:
ok "930662011"
Test #46:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
8 45272
output:
239612337
result:
ok "239612337"
Test #47:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
8 84616
output:
826857610
result:
ok "826857610"
Test #48:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
4 316408
output:
529567983
result:
ok "529567983"
Test #49:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
8 12
output:
1182
result:
ok "1182"
Test #50:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
8 16
output:
16644
result:
ok "16644"
Test #51:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
4 8
output:
6
result:
ok "6"
Test #52:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
12 16
output:
5253822
result:
ok "5253822"
Extra Test:
score: 0
Extra Test Passed