QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232005 | #7644. Good Splits | hos_lyric | AC ✓ | 28ms | 4536kb | C++14 | 6.3kb | 2023-10-29 18:54:10 | 2023-10-29 18:54:10 |
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 = 1010;
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;
}
}
}
Mint cata(int n) {
return inv[n + 1] * binom(2 * n, n);
}
int main() {
int N, P;
for (; ~scanf("%d%d", &N, &P); ) {
Mint::setM(P);
prepare();
vector<Mint> fs(N + 1, 0);
vector<vector<Mint>> ff(2 * N + 1, vector<Mint>(N + 1, 0));
for (int n = 0; n <= N; ++n) {
for (int i = 0; i <= n; ++i) {
fs[n] += binom(2 * n, 2 * i) * cata(i) * cata(n - i);
}
}
// cerr<<"fs = "<<fs<<endl;
ff[0][0] = 1;
for (int k = 1; k <= 2 * N; ++k) {
for (int n = 0; n <= N; ++n) {
for (int i = 0; i <= n; ++i) {
ff[k][n] += ff[k - 1][n - i] * fs[i];
}
}
}
auto cs = fs;
cs[0] = 0;
for (int k = 1; k <= N; ++k) {
for (int i = 1; i <= N - k; ++i) {
cs[k + i] -= cs[k] * ff[2 * k][i];
}
}
// cerr<<"cs = "<<cs<<endl;
for (int n = 0; n <= N; ++n) {
cs[n] /= 2;
}
vector<Mint> gs(N + 1, 0);
vector<vector<Mint>> gg(2 * N + 1, vector<Mint>(N + 1, 0));
gs[0] = 1;
for (int k = 0; k <= 2 * N; ++k) {
gg[k][0] = 1;
}
for (int n = 1; n <= N; ++n) {
for (int k = 1; k <= n; ++k) {
gs[n] += cs[k] * gg[2 * k][n - k];
}
for (int k = 1; k <= 2 * N; ++k) {
for (int i = 0; i <= n; ++i) {
gg[k][n] += gg[k - 1][n - i] * gs[i];
}
}
}
// cerr<<"gs = "<<gs<<endl;
for (int n = 1; n <= N; ++n) {
printf("%u\n", gs[n].x);
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
5 998244353
output:
1 3 14 84 592
result:
ok 5 number(s): "1 3 14 84 592"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
20 998244353
output:
1 3 14 84 592 4659 39699 359004 3399164 33378417 337584612 503820623 71483496 12733593 474907036 203223726 565209211 487441118 992424798 625482036
result:
ok 20 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
30 147084737
output:
1 3 14 84 592 4659 39699 359004 3399164 33378417 43415138 115604731 88255570 6762644 25928144 117374310 119291296 29414136 87790057 136053957 103827626 145662835 60977924 8837626 61475022 108138661 88536961 105609125 140429327 77714436
result:
ok 30 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
50 259851877
output:
1 3 14 84 592 4659 39699 359004 3399164 33378417 77732735 120479281 107558023 219154876 82657644 224090144 253190966 148874121 53920249 82785846 244357960 88406017 106161945 35184035 131007270 222579610 212725099 114435754 64242919 39323449 211238313 156440547 84150382 242052946 50634162 120017303 2...
result:
ok 50 numbers
Test #5:
score: 0
Accepted
time: 5ms
memory: 3948kb
input:
100 175127923
output:
1 3 14 84 592 4659 39699 359004 3399164 33378417 162456689 171123145 54532804 71333538 68283136 25628469 138841774 142350839 27676343 15931022 158187457 43201304 18465009 37939972 169592319 94983552 152752931 69017296 46403905 173424585 170947507 7870926 90491276 10182721 58907963 136216980 28163587...
result:
ok 100 numbers
Test #6:
score: 0
Accepted
time: 12ms
memory: 4160kb
input:
150 367542041
output:
1 3 14 84 592 4659 39699 359004 3399164 33378417 337584612 190675313 252320457 264200037 124276323 161424010 184935571 230223063 343780965 314302578 342350468 265272499 173792750 339843799 301192856 263531782 208259173 113525686 44197147 288967350 139023077 142942582 324678736 318907769 315638511 40...
result:
ok 150 numbers
Test #7:
score: 0
Accepted
time: 20ms
memory: 4536kb
input:
177 861641813
output:
1 3 14 84 592 4659 39699 359004 3399164 33378417 337584612 51986430 817568411 233712834 530886113 262319436 602763301 391560421 714952237 234059952 504165773 214901044 343336951 654631331 578657419 506328910 26764748 407306588 36662800 819329882 372916107 103054885 512356475 207029843 192047130 1038...
result:
ok 177 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
1 998244353
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 28ms
memory: 4524kb
input:
200 864048671
output:
1 3 14 84 592 4659 39699 359004 3399164 33378417 337584612 42358998 716480375 849841780 472934607 500922480 184767796 279937457 399183954 512063087 91797677 107549673 485929841 293677006 593203756 235501697 372544850 500179291 849823101 602694217 345293985 459931747 386664093 196167251 265892579 252...
result:
ok 200 numbers
Test #10:
score: 0
Accepted
time: 24ms
memory: 4460kb
input:
199 958494587
output:
1 3 14 84 592 4659 39699 359004 3399164 33378417 337584612 623069921 583730251 536976835 256616783 340763703 344818742 765288755 200573977 666742925 957661404 606909377 32714935 246057767 23198149 389527637 588746573 223336510 430768410 501175382 380964997 647932740 845833201 113681916 396614824 546...
result:
ok 199 numbers
Test #11:
score: 0
Accepted
time: 27ms
memory: 4456kb
input:
198 165619889
output:
1 3 14 84 592 4659 39699 359004 3399164 33378417 6344834 20536013 73289310 162017284 159458288 100856961 164827673 70631917 154742952 14393421 27830529 37917167 68934527 54693629 76175385 34254720 114820104 69340313 35844068 25551171 137354127 120937326 10672731 81957539 132401938 29387190 74534300 ...
result:
ok 198 numbers
Extra Test:
score: 0
Extra Test Passed