QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#260371 | #7838. 往日之影 | hos_lyric# | 40 | 20ms | 15680kb | C++14 | 7.7kb | 2023-11-22 04:55:04 | 2024-07-04 03:08:06 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
// Barrett
struct ModInt {
static unsigned M;
static unsigned long long NEG_INV_M;
static void setM(unsigned m) { M = m; NEG_INV_M = -1ULL / M; }
unsigned x;
ModInt() : x(0U) {}
ModInt(unsigned x_) : x(x_ % M) {}
ModInt(unsigned long long x_) : x(x_ % M) {}
ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) {
const unsigned long long y = static_cast<unsigned long long>(x) * a.x;
const unsigned long long q = static_cast<unsigned long long>((static_cast<unsigned __int128>(NEG_INV_M) * y) >> 64);
const unsigned long long r = y - M * q;
x = r - M * (r >= M);
return *this;
}
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
unsigned ModInt::M;
unsigned long long ModInt::NEG_INV_M;
// !!!Use ModInt::setM!!!
////////////////////////////////////////////////////////////////////////////////
using Mint = ModInt;
constexpr int LIM_INV = 1'000'010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];
void prepare() {
inv[1] = 1;
for (int i = 2; i < LIM_INV; ++i) {
inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
}
fac[0] = invFac[0] = 1;
for (int i = 1; i < LIM_INV; ++i) {
fac[i] = fac[i - 1] * i;
invFac[i] = invFac[i - 1] * inv[i];
}
}
Mint binom(Int n, Int k) {
if (n < 0) {
if (k >= 0) {
return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
} else if (n - k >= 0) {
return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
} else {
return 0;
}
} else {
if (0 <= k && k <= n) {
assert(n < LIM_INV);
return fac[n] * invFac[k] * invFac[n - k];
} else {
return 0;
}
}
}
struct F {
Mint x, y;
F(Mint x_ = 0, Mint y_ = 0) : x(x_), y(y_) {}
friend ostream &operator<<(ostream &os, const F &f) {
if (!f.y) return os << f.x;
if (!f.x) return os << f.y << "i";
return os << f.x << "+" << f.y << "i";
}
F operator+(const F &f) const { return F(x + f.x, y + f.y); }
F operator*(const F &f) const { return F(x * f.x - y * f.y, x * f.y + y * f.x); }
F operator*(const Mint &a) const { return F(x * a, y * a); }
};
int main() {
int numCases, MO;
for (; ~scanf("%d%d", &numCases, &MO); ) {
Mint::setM(MO);
prepare();
const F I[4] = {F(1, 0), F(0, 1), F(-1, 0), F(0, -1)};
for (int caseId = 1; caseId <= numCases; ++caseId) {
int N, A[4];
scanf("%d", &N);
for (int j = 0; j < 4; ++j) {
scanf("%d", &A[j]);
}
/*
i^1: at most 1
i^3: at most 1
i^0, i^2: not both
*/
F ans;
for (const int s : {0, 2}) {
int base = 0;
for (int j = 0; j < 4; ++j) {
base -= A[j] * (s * j);
}
base &= 3;
if (N >= (s ? 1 : 0)) {
// 2^binom(N,2)
const F f = I[base] * Mint(2).pow((Int)N*(N-1)/2);
// cerr<<"s="<<s<<" "<<__LINE__<<"> "<<f<<endl;
ans = ans + f;
}
if (N - 1 >= (s ? 1 : 0)) {
F f;
for (int j1 = 0; j1 < 4; ++j1) if (A[j1]) {
f = f + I[(base - 1 * j1) & 3] * A[j1];
}
// 2^binom(N-1,2) (1+i)^(N-1)
f = f * Mint(2).pow((Int)(N-1)*(N-2)/2 + (N-1)/2) * I[((N-1)/2) & 3];
if ((N-1) & 1) {
f = f * F(1, 1);
}
// cerr<<"s="<<s<<" "<<__LINE__<<"> "<<f<<endl;
ans = ans + f;
}
if (N - 1 >= (s ? 1 : 0)) {
F f;
for (int j3 = 0; j3 < 4; ++j3) if (A[j3]) {
f = f + I[(base - 3 * j3) & 3] * A[j3];
}
// 2^binom(N-1,2) (1-i)^(N-1)
f = f * Mint(2).pow((Int)(N-1)*(N-2)/2 + (N-1)/2) * I[(-((N-1)/2)) & 3];
if ((N-1) & 1) {
f = f * F(1, -1);
}
// cerr<<"s="<<s<<" "<<__LINE__<<"> "<<f<<endl;
ans = ans + f;
}
if (N - 2 >= (s ? 1 : 0)) {
F f;
for (int j1 = 0; j1 < 4; ++j1) if (A[j1]) {
const Mint a = A[j1];
--A[j1];
for (int j3 = 0; j3 < 4; ++j3) if (A[j3]) {
const Mint aa = a * A[j3];
f = f + I[(base - 1 * j1 - 3 * j3) & 3] * aa;
}
++A[j1];
}
// 2^binom(N-2,2) (1+i)^(N-2) (1-i)^(N-2) 2^1
f = f * Mint(2).pow((Int)(N-2)*(N-3)/2 + (N-2) + 1);
// cerr<<"s="<<s<<" "<<__LINE__<<"> "<<f<<endl;
ans = ans + f;
}
}
ans = ans * Mint(4).pow(-N);
// cerr<<"ans = "<<ans<<endl;
ans = ans * Mint(2).pow(-(Int)N*(N-1)/2);
printf("%u\n", ans.x.x);
}
}
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 7ms
memory: 15644kb
input:
1 998244353 3 1 1 0 1
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 7ms
memory: 15492kb
input:
1 998244353 7 0 2 1 4
output:
998069185
result:
ok single line: '998069185'
Test #3:
score: 0
Accepted
time: 9ms
memory: 15496kb
input:
1 998244353 4 0 1 0 3
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 7ms
memory: 15492kb
input:
1 998244353 2 1 0 1 0
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 11ms
memory: 15680kb
input:
1 998244353 6 2 1 0 3
output:
997696001
result:
ok single line: '997696001'
Test #6:
score: 0
Accepted
time: 7ms
memory: 15624kb
input:
1 998244353 2 1 0 1 0
output:
0
result:
ok single line: '0'
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 20
Accepted
time: 5ms
memory: 15664kb
input:
1 998244353 40 11 9 9 11
output:
855684614
result:
ok single line: '855684614'
Test #8:
score: 0
Accepted
time: 7ms
memory: 15548kb
input:
1 998244353 39 12 8 7 12
output:
629648158
result:
ok single line: '629648158'
Test #9:
score: 0
Accepted
time: 7ms
memory: 15640kb
input:
1 998244353 38 13 8 9 8
output:
944107686
result:
ok single line: '944107686'
Test #10:
score: 0
Accepted
time: 11ms
memory: 15532kb
input:
1 998244353 37 16 7 7 7
output:
393700837
result:
ok single line: '393700837'
Test #11:
score: 0
Accepted
time: 10ms
memory: 15492kb
input:
4 998244353 10 0 3 2 5 9 2 1 1 5 10 1 2 3 4 9 4 0 3 2
output:
124779131 998235309 124779131 998236023
result:
ok 4 lines
Test #12:
score: 0
Accepted
time: 7ms
memory: 15628kb
input:
4 998244353 10 2 1 4 3 9 1 2 4 2 10 3 2 5 0 9 3 2 2 2
output:
124779131 998239593 124778655 998236261
result:
ok 4 lines
Test #13:
score: 0
Accepted
time: 11ms
memory: 15612kb
input:
4 998244353 10 1 4 1 4 9 2 0 5 2 10 3 5 1 1 9 6 1 1 1
output:
623900891 998239355 374338940 998231025
result:
ok 4 lines
Test #14:
score: 0
Accepted
time: 7ms
memory: 15564kb
input:
8 998244353 4 2 1 0 1 4 0 2 0 2 5 0 1 1 3 4 0 1 0 3 5 1 1 0 3 5 0 3 1 1 4 2 2 0 0 5 1 1 2 1
output:
0 0 995319809 0 997269505 995319809 982646785 996294657
result:
ok 8 lines
Test #15:
score: 0
Accepted
time: 11ms
memory: 15624kb
input:
8 998244353 4 2 1 0 1 4 3 0 1 0 4 0 2 2 0 5 2 0 1 2 5 1 2 0 2 5 0 1 1 3 5 0 1 1 3 4 1 1 1 1
output:
0 0 967049217 997269505 0 995319809 995319809 0
result:
ok 8 lines
Test #16:
score: 0
Accepted
time: 7ms
memory: 15672kb
input:
3 998244353 30 1 10 7 12 8 0 3 0 5 2 0 1 0 1
output:
54137262 998208177 0
result:
ok 3 lines
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #17:
score: 0
Wrong Answer
time: 20ms
memory: 15636kb
input:
1 998244353 99 12 22 33 32 15 998244353 7 1 2 2 2 6 1 2 1 2 6 1 1 3 1 7 0 3 1 3 7 1 1 2 3 7 3 1 0 3 6 1 2 1 2 7 1 2 2 2 7 3 3 0 1 6 1 1 3 1 7 5 1 0 1 6 3 0 1 2 6 2 0 0 4 7 2 0 1 4 6 4 1 0 1
output:
940435798 998145345 997939713 997574145 998145345 998069185 998038721 997939713 998145345 998160577 997574145 998053953 997696001 997086721 997962561 997939713
result:
wrong output format Extra information in the output file
Subtask #4:
score: 10
Accepted
Test #23:
score: 10
Accepted
time: 8ms
memory: 15628kb
input:
999 999999001 2 2 0 0 0 3 3 0 0 0 4 4 0 0 0 5 5 0 0 0 6 6 0 0 0 7 7 0 0 0 8 8 0 0 0 9 9 0 0 0 10 10 0 0 0 11 11 0 0 0 12 12 0 0 0 13 13 0 0 0 14 14 0 0 0 15 15 0 0 0 16 16 0 0 0 17 17 0 0 0 18 18 0 0 0 19 19 0 0 0 20 20 0 0 0 21 21 0 0 0 22 22 0 0 0 23 23 0 0 0 24 24 0 0 0 25 25 0 0 0 26 26 0 0 0 27...
output:
499999501 874999126 359374641 919920956 691222454 586081873 33512082 496961574 790501684 206445579 708073277 492142887 486007979 21786019 802052117 198521403 854660059 658779344 904643630 538486221 357736277 949763680 94144464 342842045 695164947 276856011 552666277 813428208 572457238 910726512 177...
result:
ok 999 lines
Test #24:
score: 0
Accepted
time: 7ms
memory: 15632kb
input:
1 1000000933 154579 154579 0 0 0
output:
657848365
result:
ok single line: '657848365'
Test #25:
score: 0
Accepted
time: 11ms
memory: 15612kb
input:
1 999999001 475343 475343 0 0 0
output:
619834045
result:
ok single line: '619834045'
Test #26:
score: 0
Accepted
time: 11ms
memory: 15628kb
input:
1 999999001 165629 165629 0 0 0
output:
753727723
result:
ok single line: '753727723'
Test #27:
score: 0
Accepted
time: 11ms
memory: 15484kb
input:
1 1000000933 348634 348634 0 0 0
output:
360252198
result:
ok single line: '360252198'
Test #28:
score: 0
Accepted
time: 16ms
memory: 15636kb
input:
10000 999999229 88 88 0 0 0 96 96 0 0 0 24 24 0 0 0 95 95 0 0 0 38 38 0 0 0 27 27 0 0 0 21 21 0 0 0 76 76 0 0 0 45 45 0 0 0 72 72 0 0 0 83 83 0 0 0 78 78 0 0 0 93 93 0 0 0 73 73 0 0 0 64 64 0 0 0 71 71 0 0 0 37 37 0 0 0 42 42 0 0 0 13 13 0 0 0 19 19 0 0 0 79 79 0 0 0 65 65 0 0 0 91 91 0 0 0 28 28 0 ...
output:
228919133 233057601 14414502 12124194 609308119 236040032 384632724 342725930 359253864 890419758 438100183 233688628 152725418 662705946 267680214 513058807 175872233 462495339 413457613 571184369 442694163 537658282 297765746 578699117 239095545 57659973 903105608 745160181 652441005 521182492 347...
result:
ok 10000 lines
Test #29:
score: 0
Accepted
time: 19ms
memory: 15468kb
input:
10000 999999937 53 53 0 0 0 81 81 0 0 0 12 12 0 0 0 19 19 0 0 0 32 32 0 0 0 43 43 0 0 0 54 54 0 0 0 70 70 0 0 0 50 50 0 0 0 86 86 0 0 0 31 31 0 0 0 33 33 0 0 0 85 85 0 0 0 54 54 0 0 0 39 39 0 0 0 90 90 0 0 0 75 75 0 0 0 37 37 0 0 0 84 84 0 0 0 68 68 0 0 0 98 98 0 0 0 73 73 0 0 0 45 45 0 0 0 71 71 0 ...
output:
315851314 404961058 478608220 872834111 278393486 518892420 770069569 110378716 660680499 726285336 810531197 451629260 668208879 770069569 948485799 58650663 417912486 382928062 769177073 530030150 665011673 960730579 766994694 452899566 414064316 5286677 960730579 155111507 110378716 582367338 872...
result:
ok 10000 lines
Test #30:
score: 0
Accepted
time: 19ms
memory: 15532kb
input:
10000 1000000933 94 94 0 0 0 33 33 0 0 0 79 79 0 0 0 11 11 0 0 0 25 25 0 0 0 99 99 0 0 0 12 12 0 0 0 13 13 0 0 0 97 97 0 0 0 70 70 0 0 0 23 23 0 0 0 62 62 0 0 0 29 29 0 0 0 50 50 0 0 0 58 58 0 0 0 96 96 0 0 0 49 49 0 0 0 23 23 0 0 0 94 94 0 0 0 81 81 0 0 0 52 52 0 0 0 27 27 0 0 0 48 48 0 0 0 35 35 0...
output:
302038132 324852455 712788007 51168171 665310026 719061662 642183435 960667161 525345109 829432052 887075946 622617369 92198574 962363993 672506569 207567890 342207626 887075946 302038132 792241276 216981867 23895508 903615878 834858306 749794882 224043056 834367334 962363993 244541137 140944214 712...
result:
ok 10000 lines
Test #31:
score: 0
Accepted
time: 15ms
memory: 15488kb
input:
10000 999999229 48 48 0 0 0 99 99 0 0 0 56 56 0 0 0 82 82 0 0 0 13 13 0 0 0 78 78 0 0 0 44 44 0 0 0 23 23 0 0 0 91 91 0 0 0 39 39 0 0 0 31 31 0 0 0 39 39 0 0 0 22 22 0 0 0 69 69 0 0 0 63 63 0 0 0 49 49 0 0 0 54 54 0 0 0 91 91 0 0 0 86 86 0 0 0 14 14 0 0 0 80 80 0 0 0 47 47 0 0 0 52 52 0 0 0 56 56 0 ...
output:
969254311 41258828 420816844 53150269 413457613 233688628 16329388 962253276 297765746 579341371 491021836 579341371 694633659 238365606 737049114 282048136 467787038 297765746 568729633 239095545 37731193 985694051 20197429 420816844 467787038 337283936 131320231 267680214 890419758 12124194 757560...
result:
ok 10000 lines
Test #32:
score: 0
Accepted
time: 19ms
memory: 15620kb
input:
10000 1000000097 47 47 0 0 0 32 32 0 0 0 67 67 0 0 0 29 29 0 0 0 47 47 0 0 0 24 24 0 0 0 62 62 0 0 0 34 34 0 0 0 69 69 0 0 0 90 90 0 0 0 48 48 0 0 0 33 33 0 0 0 70 70 0 0 0 27 27 0 0 0 93 93 0 0 0 37 37 0 0 0 59 59 0 0 0 95 95 0 0 0 83 83 0 0 0 58 58 0 0 0 91 91 0 0 0 93 93 0 0 0 54 54 0 0 0 87 87 0...
output:
722092697 288259246 443086249 346535444 722092697 96701722 589679036 496735762 287843437 134626935 367894801 88663770 85448149 843667949 156786538 440592027 933702679 516941035 418538470 518055305 804803263 156786538 107212544 806586057 107212544 256264258 107212544 810269380 343546929 426066064 144...
result:
ok 10000 lines
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%