QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297639 | #4903. 细菌 | luyiming123 | 20 | 308ms | 25356kb | C++14 | 7.7kb | 2024-01-04 21:17:49 | 2024-01-04 21:17:50 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
using i64 = int;
using ui64 = unsigned long long;
const int N = 4.8e5 + 5;
const i64 mod = 998244353, ivg = (mod + 1) / 3;
void Add(i64 &x, i64 y) {x = (x + y) % mod; if(x < 0) x += mod; return; }
int d, lim[3], pos[3], r[N], L;
i64 Poly[3][N], fac[N], ifac[N];
struct node
{
int l, r; i64 S;
};
vector <node> Seg[2], FkSeg;
i64 qpow(i64 x, i64 p = mod - 2ll)
{
i64 ans = 1ll;
while(p)
{
if(p & 1) ans = 1ll * ans * 1ll * x % mod;
x = 1ll * x * 1ll * x % mod, p >>= 1;
}
return ans;
}
void NTT(i64 *a, bool type) {
static ui64 f[N], w[N];
for(int i = 0; i < L; i++) f[i] = a[r[i] = (r[i >> 1] >> 1) | (i & 1 ? L >> 1 : 0)];
for(int d = 1; d < L; d <<= 1) {
int wd = qpow(type ? 3 : ivg, (mod - 1) / (d + d));
for(int j = w[0] = 1; j < d; j++) w[j] = 1ll * w[j - 1] * 1ll * wd % mod;
for(int i = 0; i < L; i += d << 1) {
for(int j = 0; j < d; j++) {
int y = w[j] * 1ll * f[i | j | d] % mod;
f[i | j | d] = f[i | j] + mod - y, f[i | j] += y;
}
}
if(d == (1 << 16)) for(int p = 0; p < L; p++) f[p] %= mod;
}
i64 inv = qpow(L, mod - 2);
for(int i = 0; i < L; i++) a[i] = f[i] % mod * 1ll * (type ? 1 : inv) % mod;
}
void Init(int n = N - 5)
{
fac[0] = ifac[0] = 1ll;
for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * 1ll * i % mod;
ifac[n] = qpow(fac[n]);
for(int i = n - 1; i >= 1; i--) ifac[i] = ifac[i + 1] * 1ll * (i + 1) % mod;
return;
}
i64 C(int n, int m)
{
if(n < m || n < 0 || m < 0) return 0;
return fac[n] * 1ll * ifac[m] % mod * 1ll * ifac[n - m] % mod;
}
void solve(int o, int d)
{
// bool deb = (o == 0 && d == 1);
// bool deb = (o == 2);
// printf("solve : %d, %d\n", o, d);
int lim = ::lim[o], pos = ::pos[o];
// Line : y = 0, y = lim + 1
// Line : y = lim + 1 最后被触碰
i64 Ans = 0;
// int lf = 0, rg = lim + 1;
int mx = min(d, (lim - pos + d) / 2), mn = (d + 1) / 2;
// if(deb) printf("upd : d = %d, [%d, %d]\n", d, mn, mx);
// printf("mx = %d, mn = %d\n", mx, mn);
// Add(Ans, sumC[mx] - (mn > 0 ? sumC[mn - 1] : 0));
// for(int i = mn; i <= mx; i++) Add(Ans, C(d, i));
if(FkSeg.empty())
{
FkSeg.push_back({mn, mx, 0});
for(int i = mn; i <= mx; i++) Add(FkSeg[0].S, C(d, i));
}
else
{
FkSeg[0].S = (FkSeg[0].S * 1ll * 2ll % mod - C(d - 1, FkSeg[0].r) + C(d - 1, FkSeg[0].l - 1)) % mod;
for(int j = FkSeg[0].r + 1; j <= mx; j++) Add(FkSeg[0].S, C(d, j));
FkSeg[0].r = mx;
for(int j = FkSeg[0].l; j < mn; j++) Add(FkSeg[0].S, -C(d, j));
FkSeg[0].l = mn;
}
Add(Ans, FkSeg[0].S);
//[lf, pos - 1]
if(pos > 1)
{
mx = (d - 1) / 2, mn = max(0, (2 - pos + d) / 2);
// printf("2 : mx = %d, mn = %d\n", mx, mn);
// if(deb) printf("upd : d = %d, [%d, %d]\n", d, mn, mx);
// Add(Ans, sumC[mx] - (mn > 0 ? sumC[mn - 1] : 0));
// for(int i = mn; i <= mx; i++) Add(Ans, C(d, i));
if((int)FkSeg.size() < 2)
{
FkSeg.push_back({mn, mx, 0});
for(int i = mn; i <= mx; i++) Add(FkSeg.back().S, C(d, i));
}
else
{
FkSeg[1].S = (FkSeg[1].S * 1ll * 2ll % mod - C(d - 1, FkSeg[1].r) + C(d - 1, FkSeg[1].l - 1)) % mod;
for(int j = FkSeg[1].r + 1; j <= mx; j++) Add(FkSeg[1].S, C(d, j));
FkSeg[1].r = mx;
for(int j = FkSeg[1].l; j < mn; j++) Add(FkSeg[1].S, -C(d, j));
FkSeg[1].l = mn;
}
Add(Ans, FkSeg[1].S);
}
// if(deb) printf("Answer = %lld\n", Ans);
for(int i = 1; i * 1ll * (lim + 1) + 1 <= pos + d; i++)
{
// fprintf(stderr, "step 1: o = %d, d = %d, i = %d\n", o, d, i);
// assert(1ll * 1ll * i * 1ll * (lim + 1) + 1 <= pos + d);
int lf = i * 1ll * (lim + 1) + 1, rg = min((i + 1) * 1ll * (lim + 1) - 1, 1ll * pos + d);
int mx = (rg - pos + d) / 2, mn = (lf - pos + d + 1) / 2;
// if(deb) printf("upd : d = %d, [%d, %d]\n", d, mn, mx);
if(i <= (int)Seg[0].size())
{
Seg[0][i - 1].S = (Seg[0][i - 1].S * 1ll * 2ll % mod - C(d - 1, Seg[0][i - 1].r) + C(d - 1, Seg[0][i - 1].l - 1)) % mod;
for(int j = Seg[0][i - 1].r + 1; j <= mx; j++) Add(Seg[0][i - 1].S, C(d, j));
Seg[0][i - 1].r = mx;
for(int j = Seg[0][i - 1].l; j < mn; j++) Add(Seg[0][i - 1].S, -C(d, j));
Seg[0][i - 1].l = mn;
}
else
{
Seg[0].push_back({mn, mx, 0});
for(int j = mn; j <= mx; j++) Add(Seg[0].back().S, C(d, j));
}
Add(Ans, ((i & 1) ? -1 : 1) * 1ll * Seg[0][i - 1].S);
}
// Line : y = 0 最后被触碰 pos reverse
pos = lim - pos + 1;
for(int i = 1; i * 1ll * (lim + 1) + 1 <= pos + d; i++)
{
// fprintf(stderr "step 2: o = %d, d = %d, i = %d\n", o, d, i);
int lf = i * 1ll * (lim + 1) + 1, rg = min((i + 1) * 1ll * (lim + 1) - 1, 1ll * pos + d);
int mx = (rg - pos + d) / 2, mn = (lf - pos + d + 1) / 2;
// printf("fuck : mx = %d, mn = %d\n", mx, mn);
// if(deb) printf("upd : d = %d, [%d, %d]\n", d, mn, mx);
if(i <= (int)Seg[1].size())
{
Seg[1][i - 1].S = (Seg[1][i - 1].S * 1ll * 2ll % mod - C(d - 1, Seg[1][i - 1].r) + C(d - 1, Seg[1][i - 1].l - 1)) % mod;
for(int j = Seg[1][i - 1].r + 1; j <= mx; j++) Seg[1][i - 1].S += C(d, j);
Seg[1][i - 1].r = mx;
for(int j = Seg[1][i - 1].l; j < mn; j++) Seg[1][i - 1].S -= C(d, j);
Seg[1][i - 1].l = mn;
}
else
{
Seg[1].push_back({mn, mx, 0});
for(int j = mn; j <= mx; j++) Add(Seg[1].back().S, C(d, j));
}
Add(Ans, ((i & 1) ? -1 : 1) * 1ll * Seg[1][i - 1].S);
}
Poly[o][d] = Ans;
// printf("fkkkk!\n");
return;
}
void solve2(int o)
{
int lim = ::lim[o], pos = ::pos[o];
static i64 dp[2][N];
int lf = 1 - pos + d, rg = lim - pos + d;
for(int i = 0; i <= (d << 1); i++) dp[0][i] = dp[1][i] = 0;
dp[0][d] = 1;
Poly[o][0] = 1;
for(int i = 1; i <= d; i++)
{
int op = (i & 1);
for(int j = lf; j <= rg; j++) dp[op][j] = 0;
for(int j = lf; j <= rg; j++)
{
if(j < rg) Add(dp[op][j + 1], dp[op ^ 1][j]);
if(j > lf) Add(dp[op][j - 1], dp[op ^ 1][j]);
}
Poly[o][i] = 0;
for(int j = lf; j <= rg; j++) Add(Poly[o][i], dp[op][j]);
}
return;
}
int main(void)
{
Init();
scanf("%d", &d);
for(int i = 0; i < 3; i++) scanf("%d", &lim[i]);
for(int i = 0; i < 3; i++) scanf("%d", &pos[i]);
//init sumC[i] (means C(d, 1) + ... + C(d, i))
// printf("YES1\n");
for(int o = 0; o < 3; o++)
{
if(2ll * d <= 1ll * 1ll * lim[o] * 1ll * lim[o])
{
// cerr << "sblym " << lim[o] </< " " << d << '\n';
Poly[o][0] = 1;
// for(int i = 0; i <= d; i++) sumC[i] = 0;
// sumC[0] = 1;
Seg[0].clear(), Seg[1].clear(); FkSeg.clear();
for(int d0 = 1; d0 <= d; d0++)
{
// for(int i = 0; i < d0; i++)
// {
// sumC[i] = sumC[i] * 1ll * 2ll % mod - C(d0 - 1, i);
// }
// sumC[d0] = sumC[d0 - 1] + 1;
solve(o, d0);
}
// fprintf(stderr, "length : %d %d, debtot = %lld\n", (int)Seg[0].size(), (int)Seg[1].size(), debtot);
}
else fprintf(stderr, "wtf\n"), solve2(o);
// for(int i = 0; i <= d; i++) printf("Poly[%d][%d] = %lld\n", o, i, Poly[o][i]);
// fprintf(stderr, "Yes : o = %d\n", o);
}
for(int o = 0; o < 3; o++)
{
for(int i = 0; i <= d; i++) Poly[o][i] = Poly[o][i] * 1ll * ifac[i] % mod;
}
L = 1;
while(L <= (d << 1)) L <<= 1;
for(int o = 0; o < 3; o++) NTT(Poly[o], 1);
for(int i = 0; i < L; i++) Poly[0][i] = Poly[0][i] * 1ll * Poly[1][i] % mod * 1ll * Poly[2][i] % mod;
NTT(Poly[0], 0);
printf("%lld\n", Poly[0][d] * 1ll * fac[d] % mod);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 7ms
memory: 20496kb
input:
50 41 46 42 8 20 21
output:
791406134
result:
ok 1 number(s): "791406134"
Test #2:
score: 0
Accepted
time: 7ms
memory: 19124kb
input:
50 49 44 48 49 15 25
output:
544847893
result:
ok 1 number(s): "544847893"
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #3:
score: 0
Wrong Answer
time: 4ms
memory: 19492kb
input:
5000 4994 4990 4990 976 2257 2505
output:
177052162
result:
wrong answer 1st numbers differ - expected: '836390717', found: '177052162'
Subtask #3:
score: 15
Accepted
Test #5:
score: 15
Accepted
time: 259ms
memory: 22624kb
input:
120000 300 1 1 141 1 1
output:
637174
result:
ok 1 number(s): "637174"
Test #6:
score: 0
Accepted
time: 308ms
memory: 25356kb
input:
120000 994 1 1 15 1 1
output:
218803691
result:
ok 1 number(s): "218803691"
Test #7:
score: 0
Accepted
time: 34ms
memory: 25336kb
input:
120000 119999 1 1 19896 1 1
output:
68846585
result:
ok 1 number(s): "68846585"
Subtask #4:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 46ms
memory: 22480kb
input:
119000 119991 119991 1 23819 52139 1
output:
720236862
result:
wrong answer 1st numbers differ - expected: '944500934', found: '720236862'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #3:
100%
Accepted
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%