QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#233199 | #7632. Balanced Arrays | zhoukangyang | AC ✓ | 166ms | 59816kb | C++11 | 7.0kb | 2023-10-31 15:03:30 | 2023-10-31 15:03:32 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long
using namespace std;
const int mod = 998244353, _G = 3, N = (1 << 21), inv2 = (mod + 1) / 2;
#define add(a, b) (a + b >= mod ? a + b - mod : a + b)
#define dec(a, b) (a < b ? a - b + mod : a - b)
int qpow(int x, int y = mod - 2) {
int res = 1;
for(; y; x = (ll) x * x % mod, y >>= 1) if(y & 1) res = (ll) res * x % mod;
return res;
}
int fac[N + 1], ifac[N + 1], inv[N + 1];
void init(int x) {
fac[0] = ifac[0] = inv[1] = 1;
L(i, 2, x) inv[i] = (ll) inv[mod % i] * (mod - mod / i) % mod;
L(i, 1, x) fac[i] = (ll) fac[i - 1] * i % mod, ifac[i] = (ll) ifac[i - 1] * inv[i] % mod;
}
int C(int x, int y) {
return y < 0 || x < y ? 0 : (ll) fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
inline int sgn(int x) {
return (x & 1) ? mod - 1 : 1;
}
int rt[N], Lim;
void Pinit(int x) {
for(Lim = 1; Lim <= x; Lim <<= 1) ;
for(int i = 1; i < Lim; i <<= 1) {
int sG = qpow (_G, (mod - 1) / (i << 1));
rt[i] = 1;
L(j, i + 1, i * 2 - 1) rt[j] = (ll) rt[j - 1] * sG % mod;
}
}
struct poly {
vector<int> a;
int size() { return sz(a); }
int & operator [] (int x) { return a[x]; }
int v(int x) { return x < 0 || x >= sz(a) ? 0 : a[x]; }
void clear() { vector<int> ().swap(a); }
void rs(int x = 0) { a.resize(x); }
poly (int n = 0) { rs(n); }
poly (vector<int> o) { a = o; }
poly (const poly &o) { a = o.a; }
poly Rs(int x = 0) { vi res = a; res.resize(x); return res; }
inline void dif() {
int n = sz(a);
for (int l = n >> 1; l >= 1; l >>= 1)
for(int j = 0; j < n; j += l << 1)
for(int k = 0, *w = rt + l; k < l; k++, w++) {
int x = a[j + k], y = a[j + k + l];
a[j + k] = add(x, y);
a[j + k + l] = (ll) * w * dec(x, y) % mod;
}
}
void dit () {
int n = sz(a);
for(int i = 2; i <= n; i <<= 1)
for(int j = 0, l = (i >> 1); j < n; j += i)
for(int k = 0, *w = rt + l; k < l; k++, w++) {
int pa = a[j + k], pb = (ll) a[j + k + l] * *w % mod;
a[j + k] = add(pa, pb), a[j + k + l] = dec(pa, pb);
}
reverse(a.begin() + 1, a.end());
for(int i = 0, iv = qpow(n); i < n; i++) a[i] = (ll) a[i] * iv % mod;
}
friend poly operator * (poly aa, poly bb) {
if(!sz(aa) || !sz(bb)) return {};
int lim, all = sz(aa) + sz(bb) - 1;
for(lim = 1; lim < all; lim <<= 1);
aa.rs(lim), bb.rs(lim), aa.dif(), bb.dif();
L(i, 0, lim - 1) aa[i] = (ll) aa[i] * bb[i] % mod;
aa.dit(), aa.a.resize(all);
return aa;
}
poly Inv() {
poly res, f, g;
res.rs(1), res[0] = qpow(a[0]);
for(int m = 1, pn; m < sz(a); m <<= 1) {
pn = m << 1, f = res, g.rs(pn), f.rs(pn);
for(int i = 0; i < pn; i++) g[i] = (*this).v(i);
f.dif(), g.dif();
for(int i = 0; i < pn; i++) g[i] = (ll) f[i] * g[i] % mod;
g.dit();
for(int i = 0; i < m; i++) g[i] = 0;
g.dif();
for(int i = 0; i < pn; i++) g[i] = (ll) f[i] * g[i] % mod;
g.dit(), res.rs(pn);
for(int i = m; i < min(pn, sz(a)); i++) res[i] = (mod - g[i]) % mod;
}
return res.rs(sz(a)), res;
}
poly Shift (int x) {
poly zm (sz(a) + x);
L(i, max(-x, 0), sz(a) - 1) zm[i + x] = a[i];
return zm;
}
friend poly operator * (poly aa, int bb) {
poly res(sz(aa));
L(i, 0, sz(aa) - 1) res[i] = (ll) aa[i] * bb % mod;
return res;
}
friend poly operator + (poly aa, poly bb) {
vector<int> res(max(sz(aa), sz(bb)));
L(i, 0, sz(res) - 1) res[i] = add(aa.v(i), bb.v(i));
return poly(res);
}
friend poly operator - (poly aa, poly bb) {
vector<int> res(max(sz(aa), sz(bb)));
L(i, 0, sz(res) - 1) res[i] = dec(aa.v(i), bb.v(i));
return poly(res);
}
poly & operator += (poly o) {
rs(max(sz(a), sz(o)));
L(i, 0, sz(a) - 1) (a[i] += o.v(i)) %= mod;
return (*this);
}
poly & operator -= (poly o) {
rs(max(sz(a), sz(o)));
L(i, 0, sz(a) - 1) (a[i] += mod - o.v(i)) %= mod;
return (*this);
}
poly & operator *= (poly o) {
return (*this) = (*this) * o;
}
poly Integ() {
if(!sz(a)) return poly();
poly res(sz(a) + 1);
L(i, 1, sz(a)) res[i] = (ll) a[i - 1] * inv[i] % mod;
return res;
}
poly Deriv() {
if(!sz(a)) return poly();
poly res(sz(a) - 1);
L(i, 1, sz(a) - 1) res[i - 1] = (ll) a[i] * i % mod;
return res;
}
poly Ln() {
poly g = ((*this).Inv() * (*this).Deriv()).Integ();
return g.rs(sz(a)), g;
}
poly Exp() {
poly res(1), f;
res[0] = 1;
for(int m = 1, pn; m < sz(a); m <<= 1) {
pn = min(m << 1, sz(a)), f.rs(pn), res.rs(pn);
for(int i = 0; i < pn; i++) f[i] = (*this).v(i);
f -= res.Ln(), (f[0] += 1) %= mod, res *= f, res.rs(pn);
}
return res.rs(sz(a)), res;
}
poly pow(int x, int rx = -1) { // x : the power % mod; rx : the power % (mod - 1)
if(rx == -1) rx = x;
int cnt = 0;
while (a[cnt] == 0 && cnt < sz(a)) cnt += 1;
poly res = (*this);
L(i, cnt, sz(a) - 1) res[i - cnt] = res[i];
L(i, sz(a) - cnt, sz(a) - 1) res[i] = 0;
int c = res[0], w = qpow (res[0]);
L(i, 0, sz(res) - 1) res[i] = (ll) res[i] * w % mod;
res = res.Ln();
L(i, 0, sz(res) - 1) res[i] = (ll) res[i] * x % mod;
res = res.Exp();
c = qpow (c, rx);
L(i, 0, sz(res) - 1) res[i] = (ll) res[i] * c % mod;
if((ll) cnt * x > sz(a)) L(i, 0, sz(a) - 1) res[i] = 0;
else if(cnt) {
R(i, sz(a) - cnt * x - 1, 0) res[i + cnt * x] = res[i];
L(i, 0, cnt * x - 1) res[i] = 0;
}
return res;
}
poly sqrt(int rt = 1) {
poly res(1), f;
res[0] = rt;
for(int m = 1, pn; m < sz(a); m <<= 1) {
pn = min(m << 1, sz(a)), f.rs(pn);
for(int i = 0; i < pn; i++) f[i] = (*this).v(i);
f += res * res, f.rs(pn), res.rs(pn), res = f * res.Inv(), res.rs(pn);
for(int i = 0; i < pn; i++) res[i] = (ll) res[i] * inv2 % mod;
}
return res;
}
void Rev() {
reverse(a.begin(), a.end());
}
} ;
int n, m;
int main () {
// freopen("ex_water1.in", "r", stdin);
// freopen("ex_water1.ans", "w", stdout);
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
init(1 << 21);
Pinit(1 << 20);
int ans = 1;
poly f(max(n, m) + 1);
poly g(max(n, m) + 1);
poly h(max(n, m) + 1);
L(s, 1, m) {
f[s] = (ll) fac[s] * fac[s - 1] % mod * ifac[s * 2] % mod;
}
L(k, 1, (n + 1) / 2) {
g[k] = (ll) ifac[k - 1] * ifac[k - 1] % mod * inv[k] % mod * ifac[n - k * 2 + 1] % mod;
}
L(d, 0, m) {
h[d] = (ll) ifac[d] * ifac[d + 1] % mod * fac[d * 2 + n + 1] % mod;
}
h *= g;
L(i, 1, m) {
(ans += (ll) h[i] * f[i] % mod) %= mod;
}
// L(s, 1, m) {
// L(k, 1, min((n + 1) / 2, s)) {
// (ans += (ll) fac[s] * ifac[k - 1] % mod * fac[s - 1] % mod * ifac[k - 1] % mod
// * ifac[s - k + 1] % mod * ifac[s - k] % mod *
// fac[s * 2 + n + 1 - k * 2] % mod * ifac[s * 2] % mod * ifac[n - k * 2 + 1] % mod
// * inv[k] % mod) %= mod;
// }
// }
cout << ans << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 32ms
memory: 36280kb
input:
2 2
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 158ms
memory: 59748kb
input:
500000 500000
output:
984531374
result:
ok 1 number(s): "984531374"
Test #3:
score: 0
Accepted
time: 121ms
memory: 59748kb
input:
500000 1
output:
219705876
result:
ok 1 number(s): "219705876"
Test #4:
score: 0
Accepted
time: 121ms
memory: 59656kb
input:
1 500000
output:
500001
result:
ok 1 number(s): "500001"
Test #5:
score: 0
Accepted
time: 158ms
memory: 59816kb
input:
500000 353535
output:
33730077
result:
ok 1 number(s): "33730077"
Test #6:
score: 0
Accepted
time: 156ms
memory: 59800kb
input:
353535 500000
output:
182445298
result:
ok 1 number(s): "182445298"
Test #7:
score: 0
Accepted
time: 149ms
memory: 59796kb
input:
499999 499999
output:
933220940
result:
ok 1 number(s): "933220940"
Test #8:
score: 0
Accepted
time: 164ms
memory: 59756kb
input:
499999 499998
output:
899786345
result:
ok 1 number(s): "899786345"
Test #9:
score: 0
Accepted
time: 160ms
memory: 56360kb
input:
377773 400009
output:
206748715
result:
ok 1 number(s): "206748715"
Test #10:
score: 0
Accepted
time: 147ms
memory: 59748kb
input:
499999 100001
output:
482775773
result:
ok 1 number(s): "482775773"
Test #11:
score: 0
Accepted
time: 152ms
memory: 59316kb
input:
444445 488884
output:
70939759
result:
ok 1 number(s): "70939759"
Test #12:
score: 0
Accepted
time: 150ms
memory: 59372kb
input:
488885 444449
output:
591315327
result:
ok 1 number(s): "591315327"
Test #13:
score: 0
Accepted
time: 133ms
memory: 59796kb
input:
500000 111
output:
313439156
result:
ok 1 number(s): "313439156"
Test #14:
score: 0
Accepted
time: 166ms
memory: 57896kb
input:
333333 444444
output:
403492103
result:
ok 1 number(s): "403492103"
Test #15:
score: 0
Accepted
time: 154ms
memory: 59728kb
input:
499994 343433
output:
334451699
result:
ok 1 number(s): "334451699"
Test #16:
score: 0
Accepted
time: 155ms
memory: 58936kb
input:
477774 411113
output:
63883341
result:
ok 1 number(s): "63883341"
Test #17:
score: 0
Accepted
time: 155ms
memory: 57640kb
input:
123456 432109
output:
238795570
result:
ok 1 number(s): "238795570"
Test #18:
score: 0
Accepted
time: 160ms
memory: 58708kb
input:
131331 467777
output:
834790039
result:
ok 1 number(s): "834790039"
Test #19:
score: 0
Accepted
time: 119ms
memory: 59760kb
input:
500000 2
output:
304727284
result:
ok 1 number(s): "304727284"
Test #20:
score: 0
Accepted
time: 23ms
memory: 36244kb
input:
1111 111
output:
98321603
result:
ok 1 number(s): "98321603"
Test #21:
score: 0
Accepted
time: 153ms
memory: 59324kb
input:
416084 493105
output:
916827025
result:
ok 1 number(s): "916827025"
Test #22:
score: 0
Accepted
time: 83ms
memory: 44308kb
input:
53888 138663
output:
57263952
result:
ok 1 number(s): "57263952"
Test #23:
score: 0
Accepted
time: 155ms
memory: 55932kb
input:
219161 382743
output:
304889787
result:
ok 1 number(s): "304889787"
Test #24:
score: 0
Accepted
time: 154ms
memory: 53936kb
input:
181392 318090
output:
12528742
result:
ok 1 number(s): "12528742"
Test #25:
score: 0
Accepted
time: 147ms
memory: 57284kb
input:
135930 422947
output:
554153000
result:
ok 1 number(s): "554153000"
Test #26:
score: 0
Accepted
time: 164ms
memory: 52716kb
input:
280507 210276
output:
812816587
result:
ok 1 number(s): "812816587"
Test #27:
score: 0
Accepted
time: 164ms
memory: 57148kb
input:
253119 420465
output:
124024302
result:
ok 1 number(s): "124024302"
Test #28:
score: 0
Accepted
time: 149ms
memory: 57916kb
input:
446636 97448
output:
150388382
result:
ok 1 number(s): "150388382"
Test #29:
score: 0
Accepted
time: 156ms
memory: 52784kb
input:
284890 126665
output:
786559507
result:
ok 1 number(s): "786559507"
Test #30:
score: 0
Accepted
time: 84ms
memory: 45876kb
input:
186708 28279
output:
607509026
result:
ok 1 number(s): "607509026"
Extra Test:
score: 0
Extra Test Passed