QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#245097 | #7634. Cards | ucup-team2307# | AC ✓ | 12087ms | 28420kb | C++20 | 3.1kb | 2023-11-09 18:41:33 | 2023-11-09 18:41:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef vector<int> vi;
const ll mod = 998244353, root = 62;
ll modpow(ll b, ll e) {
ll ans = 1;
for (; e; b = b * b % mod, e /= 2)
if (e & 1) ans = ans * b % mod;
return ans;
}
typedef vector<ll> vl;
void ntt(vl &a) {
int n = sz(a), L = 31 - __builtin_clz(n);
static vl rt(2, 1);
for (static int k = 2, s = 2; k < n; k *= 2, s++) {
rt.resize(n);
ll z[] = {1, modpow(root, mod >> s)};
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;
}
vi rev(n);
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int k = 1; k < n; k *= 2)
for(int i = 0; i < n; i += 2*k) rep(j,0,k) {
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
a[i + j + k] = ai - z + (z > ai ? mod : 0);
ai += (ai + z >= mod ? z - mod : z);
}
}
vl conv(const vl &a, const vl &b) {
if (a.empty() || b.empty()) return {};
int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1<<B;
int inv = modpow(n, mod - 2);
vl L(a), R(b), out(n);
L.resize(n); R.resize(n);
ntt(L), ntt(R);
rep(i,0,n) out[-i & (n-1)] = (ll)L[i] * R[i] % mod * inv % mod;
ntt(out);
return {out.begin(), out.begin() + s};
}
const int N = 303303, C = 2000;
int n, m, dp[N], tmp[4 * C + 5];
ll p[5];
vl get_trans(int x) {
vl trans {1}, base(p, p + 5);
while(x) {
if(x & 1) trans = conv(trans, base);
base = conv(base, base);
x >>= 1;
}
return trans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
int s = 0;
for(auto &i : p) cin >> i, s = (s + i) % mod;
int is = modpow(s, mod - 2);
for(auto &i : p) i = i * 1ll * is % mod;
dp[n] = 1;
n = n + 2 * m;
vl trans = get_trans(C);
for(int i = 0; i < m;) {
int step = min(m - i, C);
i += step;
if(step != C) trans = get_trans(step);
vl top(n - 2 * step + 1);
for(int i = 2 * step; i <= n; i++)
top[i - 2 * step] = dp[i], dp[i] = 0;
for(int it = step; it--;) {
memset(tmp, 0, sizeof tmp);
for(int i = 0; i < 4 * step; i++) {
for(int j = (i < 2) + (i < 1); j < 5; j++) {
// cout << i << " " << i + j - 2 << " " << dp[i] * 1ll * p[j] % mod <<endl;
tmp[i + j - 2] = (tmp[i + j - 2] + dp[i] * 1ll * p[j]) % mod;
}
}
memmove(dp, tmp, 4 * step * sizeof(int));
}
top = conv(top, trans);
for(int i = 0; i <= n; i++) {
// cout << i << " == " << dp[i] << " " << top[i] << endl;
dp[i] = dp[i] + top[i] >= mod ? dp[i] + top[i] - mod : dp[i] + top[i];
}
}
ll sum = 0;
for(auto &i : dp) {sum += i;}
cout << sum % mod << '\n';
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 3932kb
input:
1 1 1 1 1 1 1
output:
399297742
result:
ok 1 number(s): "399297742"
Test #2:
score: 0
Accepted
time: 11575ms
memory: 28032kb
input:
100000 100000 1234 4567 7890 4321 54321
output:
348074135
result:
ok 1 number(s): "348074135"
Test #3:
score: 0
Accepted
time: 12087ms
memory: 28112kb
input:
100000 100000 1 2 3 4 5
output:
639188342
result:
ok 1 number(s): "639188342"
Test #4:
score: 0
Accepted
time: 11539ms
memory: 28128kb
input:
100000 100000 5 4 3 2 1
output:
211669278
result:
ok 1 number(s): "211669278"
Test #5:
score: 0
Accepted
time: 8ms
memory: 3936kb
input:
0 0 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 3654ms
memory: 10128kb
input:
1 50000 1 1 1 1 1
output:
548880636
result:
ok 1 number(s): "548880636"
Test #7:
score: 0
Accepted
time: 14ms
memory: 6036kb
input:
50000 1 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 11580ms
memory: 28132kb
input:
100000 100000 234 666 7655 12234 0
output:
45268602
result:
ok 1 number(s): "45268602"
Test #9:
score: 0
Accepted
time: 11572ms
memory: 28412kb
input:
99999 99999 12345 54332 12345 65432 34444
output:
360543661
result:
ok 1 number(s): "360543661"
Test #10:
score: 0
Accepted
time: 11842ms
memory: 28420kb
input:
99998 99998 1 1 1 1 1
output:
602326230
result:
ok 1 number(s): "602326230"
Test #11:
score: 0
Accepted
time: 11604ms
memory: 27852kb
input:
99998 99997 1 1 1 1 1
output:
159752985
result:
ok 1 number(s): "159752985"
Test #12:
score: 0
Accepted
time: 11596ms
memory: 28052kb
input:
99997 100000 1 2 3 4 5
output:
139603712
result:
ok 1 number(s): "139603712"
Test #13:
score: 0
Accepted
time: 11745ms
memory: 27920kb
input:
100000 99997 1 2 2 1 3232323
output:
363030953
result:
ok 1 number(s): "363030953"
Test #14:
score: 0
Accepted
time: 3ms
memory: 4196kb
input:
0 0 0 0 1 0 0
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 674ms
memory: 6196kb
input:
10000 10000 91095828 93770094 5303328 491263 50290308
output:
135900098
result:
ok 1 number(s): "135900098"
Test #16:
score: 0
Accepted
time: 684ms
memory: 6500kb
input:
9226 9995 62366139 253808 1929312 491263 4375669
output:
812662634
result:
ok 1 number(s): "812662634"
Test #17:
score: 0
Accepted
time: 673ms
memory: 6364kb
input:
18641 10000 1061 4359 1330 13764 16043
output:
112339046
result:
ok 1 number(s): "112339046"
Extra Test:
score: 0
Extra Test Passed