QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#248189 | #7632. Balanced Arrays | ucup-team2307 | AC ✓ | 216ms | 17796kb | C++20 | 7.9kb | 2023-11-11 17:48:59 | 2023-11-11 17:48:59 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
template<typename F>
void multitest(F func) {
int t;
cin >> t;
while(t--) func();
}
void report(int ok) {
cout << (ok?"YES":"NO") << '\n';
}
const int mod = 998244353;
namespace math {
const int L = 1<<20, A = 1<<20, B = 32, G = 3;
#define INLINE inline __attribute__ (( always_inline ))
struct mint {
uint32_t v;
template<class T = int>
mint(T x = 0) {
x %= mod;
if(x < 0) x += mod;
v = x;
}
mint operator-() const {
return mint(v ? mod-v : 0);
}
mint &operator*=(const mint &r) {
v = v*1ll*r.v%mod;
return *this;
}
mint &operator+=(const mint &r) {
v = v+r.v>=mod ? (v+r.v-mod) : (v+r.v);
return *this;
}
mint &operator-=(const mint &r) {
return *this += -r;
}
mint &operator/=(const mint &r) {
return *this *= r.inv();
}
friend mint operator+(mint a, const mint &b) {
return a += b;
}
friend mint operator-(mint a, const mint &b) {
return a -= b;
}
friend mint operator*(mint a, const mint &b) {
return a *= b;
}
friend mint operator/(mint a, const mint &b) {
return a /= b;
}
template<class T = int>
mint pow(T p) const {
mint res = 1, cur = *this;
while(p) {
if(p&1) res = res*cur;
cur = cur*cur, p>>=1;
}
return res;
}
mint inv() const {
return mint(*this).pow(mod-2);
}
friend bool operator==(const mint &a, const mint &b) {
return a.v == b.v;
}
friend bool operator!=(const mint &a, const mint &b) {
return !(a == b);
}
friend istream& operator>>(istream &is, mint &m) {
ll v;
is >> v;
m = mint(v);
return is;
}
friend ostream& operator<<(ostream &os, const mint &m) {
os << m.v;
return os;
}
};
mint fact[A], inum[A], ifact[A];
void calc_inum() {
inum[1] = 1;
for(int i = 2; i < A; i++) inum[i] = -inum[mod%i]*(mod/i);
}
void calc_combi() {
if(0 == inum[1]) calc_inum();
fact[0] = ifact[0] = 1;
for(int i = 1; i < A; i++) fact[i] = fact[i-1]*i;
for(int i = 1; i < A; i++) ifact[i] = ifact[i-1]*inum[i];
}
mint nck(int n, int k) {
if(0 == fact[0]) calc_combi();
if(k > n || k < 0) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
uint W[L], WI[L];
INLINE void calc_roots() {
W[0] = 1;
int g = mint(G).pow((mod-1)/L).v;
int i;
for(i = 1; i < L/2; i++) W[i] = W[i-1]*1ull*g%mod;
for(int x = 2; x < L; x*=2) {
for(int y = 0; y < L/2; y+=x)
W[i++] = W[y];
}
for(i = 0; i < L; i++) {
WI[i] = (uint64_t(W[i])<<B)/mod;
}
}
INLINE void _ntt(int N, vector<mint> &a) {//normal poly -> bit-rev dft | internally [0; 2*mod)
int pos = 0;
for(int l = L/2; l != N/2; l/=2)
pos += l;
for(int l = N/2; l; l/=2) {
for(int x = 0; x < N; x+=2*l) {
for(int j = pos, i = 0; i < l; i++, j++) {
uint u = a[x+i].v+a[x+l+i].v;
if(u >= 2*mod) u -= 2*mod;
uint v = a[x+i].v-a[x+l+i].v+2*mod;
uint Q = (v*1ull*WI[j])>>B;
v = v*W[j] - Q*mod;
a[x+i].v = u, a[x+l+i].v = v;
}
}
pos += l;
}
for(int i = 0; i < N; i++) if(a[i].v >= mod) a[i].v -= mod;
}
INLINE void _ntt_inv(int N, vector<mint> &a) {//bit-rev dft -> normal poly | internally [0; 4*mod)
int pos = L-2;
for(int l = 1; l < N; l*=2) {
for(int x = 0; x < N; x += 2*l) {
for(int j = pos, i = 0; i < l; i++, j++) {
uint u = a[x+i].v, v = a[x+l+i].v;
uint Q = (WI[j]*1ull*v)>>B;
if(u >= 2*mod) u -= 2*mod;
v = v*W[j] - Q*mod;
a[x+i].v = u+v, a[x+l+i].v = u-v+2*mod;
}
}
pos -= 2*l;
}
reverse(1 + all(a));
mint x = mint((mod+1)/2).pow(__lg(N));
for(auto &i : a) i *= x;//takes care of 2*mod
}
template<bool inv>
INLINE void ntt(int n, vector<mint> &a) {//don't forget about reverse order
if(W[0] == 0) calc_roots();
if(!inv) _ntt(n, a);
else _ntt_inv(n, a);
}
struct poly : vector<mint> {
template<class... Args>
explicit poly(Args... args) : vector<mint>(args...) {}
poly(initializer_list<mint> il) : vector<mint>(il.begin(), il.end()) {}
poly &trim(int k) {// mod x^k
if(size() > k) {
erase(begin()+k, end());
shrink_to_fit();
}
return *this;
}
poly &trim() {//remove heading zeroes
int k = 0;
while(k < size() && (*this)[size()-k-1] == 0) k++;
trim(size()-k);
return *this;
}
poly low(int k) const {//get first k coefficients
k = min(k, (int)size());
poly res;
for(int i = 0; i < k; i++) res.push_back((*this)[i]);
return res;
}
friend poly operator*(poly a, const poly &b) {
poly res = b;
int n = a.size()+b.size()-1;
while(n&(n-1)) n += n&-n;
a.resize(n);
res.resize(n);
ntt<0>(n, a);
ntt<0>(n, res);
for(int i = 0; i < n; i++) res[i] *= a[i];
ntt<1>(n, res);
res.trim();//remove ?
return res;
}
poly &operator*=(const poly &b) {
return (*this) = (*this)*b;
}
template<class T>
poly &operator*=(const T &x) {
for(auto &i : *this) i *= x;
return *this;
}
poly &operator+=(const poly &x) {
if(size() < x.size()) resize(x.size());
for(int i = 0; i < min(size(), x.size()); i++) (*this)[i] += x[i];
return *this;
}
poly &operator-=(const poly &x) {
if(size() < x.size()) resize(x.size());
for(int i = 0; i < min(size(), x.size()); i++) (*this)[i] -= x[i];
return *this;
}
template<class T> friend poly operator*(poly p, const T &x) { return p *= x; }
template<class T> friend poly operator*(const T &x, poly p) { return p *= x; }
friend poly operator+(poly p, const poly &x) { return p += x; }
friend poly operator-(poly p, const poly &x) { return p -= x; }
poly inv(int N) {//first n coefficients of P^-1
assert((*this)[0].v);
poly R {(*this)[0].inv()};
R.reserve(2*N);
for(int len = 2; len/2 < N; len*=2) {//R' = R(2 - RT)
poly T = low(len);
T.resize(2*len);ntt<0>(2*len, T);
R.resize(2*len);ntt<0>(2*len, R);
for(int i = 0; i < 2*len; i++) R[i] = R[i]*(2 - R[i]*T[i]);
ntt<1>(2*len, R);
R.trim(len);
}
return R.trim(N);
}
poly &derive() {
for(int i = 0; i+1 < size(); i++) {
(*this)[i] = (*this)[i+1]*(i+1);
}
pop_back();
return *this;
}
poly derivative() { return poly(*this).derive(); }
poly &integrate() {
if(0 == inum[1]) calc_inum();
push_back(0);
for(int i = size(); i-- > 1;) {
(*this)[i] = (*this)[i-1] * inum[i];
}
(*this)[0] = 0;
return *this;
}
poly integral() { return poly(*this).integrate(); }
poly ln(int N) {//first n coefficients of ln(P) = P'/P
return (low(N+1).derivative() * inv(N)).trim(N-1).integrate().trim(N);
}
poly exp(int N) {//first n coefficients of exp(P), quite slow
poly R{1};
for(int len = 2; len/2 < N; len*=2) {
R = (R*(poly{1}+low(len)-R.ln(len))).trim(len);
}
return R.trim(N);
}
};
}
using namespace math;
int main() {
cin.tie(0)->sync_with_stdio(0);
//multitest([&](){});
auto f = [&](int N, int M) -> mint {
mint ans = 1;
// for(int j = 0; j < N; j++)
// ans *= mint(M + j);
ans *= fact[M + N - 1] / fact[M - 1];
// for(int j = 0; j < N; j++)
// ans /= mint(N + 1 - j);
ans /= fact[N + 1];
// for(int j = 0; j < N; j++)
// ans *= mint(M - 1 + j);
ans *= fact[M + N - 2] / fact[M - 2];
// for(int j = 0; j < N; j++)
// ans /= mint(N - j);
ans /= fact[N];
// cout << N << " " << M << " " << ans << endl;
return ans;
};
// int cnt = 0;
// for(int a = 1; a <= 4; a++) {
// for(int b = 1; b <= 4; b++) {
// for(int c = 1; c <= 4; c++) {
// for(int d = 1; d <= 4; d++) {
// if(a < b && c < d && a <= c && b <= d) {
// //ab
// //cd
// if(a - b == -1 || a - d == -1 || c - b == -1 || c - d == -1) continue;
// cnt++;
// }
// }
// }
// }
// }
// cout << cnt << '\n';
int n, m;
cin >> n >> m;
mint ans = 0;
for(int i = 0; i <= min(m, n); i++) {
ans += f(m - i, n + 2) * (i % 2 ? -1 : 1) * nck(n, i);
}
cout << ans << '\n';
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 17ms
memory: 16224kb
input:
2 2
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 216ms
memory: 16980kb
input:
500000 500000
output:
984531374
result:
ok 1 number(s): "984531374"
Test #3:
score: 0
Accepted
time: 14ms
memory: 17276kb
input:
500000 1
output:
219705876
result:
ok 1 number(s): "219705876"
Test #4:
score: 0
Accepted
time: 10ms
memory: 17152kb
input:
1 500000
output:
500001
result:
ok 1 number(s): "500001"
Test #5:
score: 0
Accepted
time: 156ms
memory: 16308kb
input:
500000 353535
output:
33730077
result:
ok 1 number(s): "33730077"
Test #6:
score: 0
Accepted
time: 156ms
memory: 16132kb
input:
353535 500000
output:
182445298
result:
ok 1 number(s): "182445298"
Test #7:
score: 0
Accepted
time: 216ms
memory: 16564kb
input:
499999 499999
output:
933220940
result:
ok 1 number(s): "933220940"
Test #8:
score: 0
Accepted
time: 216ms
memory: 17700kb
input:
499999 499998
output:
899786345
result:
ok 1 number(s): "899786345"
Test #9:
score: 0
Accepted
time: 170ms
memory: 16248kb
input:
377773 400009
output:
206748715
result:
ok 1 number(s): "206748715"
Test #10:
score: 0
Accepted
time: 54ms
memory: 16820kb
input:
499999 100001
output:
482775773
result:
ok 1 number(s): "482775773"
Test #11:
score: 0
Accepted
time: 194ms
memory: 17796kb
input:
444445 488884
output:
70939759
result:
ok 1 number(s): "70939759"
Test #12:
score: 0
Accepted
time: 193ms
memory: 16472kb
input:
488885 444449
output:
591315327
result:
ok 1 number(s): "591315327"
Test #13:
score: 0
Accepted
time: 14ms
memory: 16704kb
input:
500000 111
output:
313439156
result:
ok 1 number(s): "313439156"
Test #14:
score: 0
Accepted
time: 149ms
memory: 17664kb
input:
333333 444444
output:
403492103
result:
ok 1 number(s): "403492103"
Test #15:
score: 0
Accepted
time: 157ms
memory: 16996kb
input:
499994 343433
output:
334451699
result:
ok 1 number(s): "334451699"
Test #16:
score: 0
Accepted
time: 180ms
memory: 17196kb
input:
477774 411113
output:
63883341
result:
ok 1 number(s): "63883341"
Test #17:
score: 0
Accepted
time: 67ms
memory: 16368kb
input:
123456 432109
output:
238795570
result:
ok 1 number(s): "238795570"
Test #18:
score: 0
Accepted
time: 66ms
memory: 17340kb
input:
131331 467777
output:
834790039
result:
ok 1 number(s): "834790039"
Test #19:
score: 0
Accepted
time: 17ms
memory: 17384kb
input:
500000 2
output:
304727284
result:
ok 1 number(s): "304727284"
Test #20:
score: 0
Accepted
time: 13ms
memory: 17208kb
input:
1111 111
output:
98321603
result:
ok 1 number(s): "98321603"
Test #21:
score: 0
Accepted
time: 186ms
memory: 16468kb
input:
416084 493105
output:
916827025
result:
ok 1 number(s): "916827025"
Test #22:
score: 0
Accepted
time: 35ms
memory: 16032kb
input:
53888 138663
output:
57263952
result:
ok 1 number(s): "57263952"
Test #23:
score: 0
Accepted
time: 98ms
memory: 17580kb
input:
219161 382743
output:
304889787
result:
ok 1 number(s): "304889787"
Test #24:
score: 0
Accepted
time: 87ms
memory: 17004kb
input:
181392 318090
output:
12528742
result:
ok 1 number(s): "12528742"
Test #25:
score: 0
Accepted
time: 68ms
memory: 17488kb
input:
135930 422947
output:
554153000
result:
ok 1 number(s): "554153000"
Test #26:
score: 0
Accepted
time: 103ms
memory: 16748kb
input:
280507 210276
output:
812816587
result:
ok 1 number(s): "812816587"
Test #27:
score: 0
Accepted
time: 115ms
memory: 16016kb
input:
253119 420465
output:
124024302
result:
ok 1 number(s): "124024302"
Test #28:
score: 0
Accepted
time: 53ms
memory: 16144kb
input:
446636 97448
output:
150388382
result:
ok 1 number(s): "150388382"
Test #29:
score: 0
Accepted
time: 64ms
memory: 16012kb
input:
284890 126665
output:
786559507
result:
ok 1 number(s): "786559507"
Test #30:
score: 0
Accepted
time: 24ms
memory: 16032kb
input:
186708 28279
output:
607509026
result:
ok 1 number(s): "607509026"
Extra Test:
score: 0
Extra Test Passed