QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#230033 | #7634. Cards | ucup-team1198# | AC ✓ | 1959ms | 27228kb | C++20 | 5.1kb | 2023-10-28 17:27:55 | 2023-10-28 19:29:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()
const int MOD = 998244353;
int add(int a, int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int sub(int a, int b) {
return a >= b ? a - b : a + MOD - b;
}
int mul(int a, int b) {
return (1ll * a * b) % MOD;
}
int pw(int x, int n) {
int res = 1;
while (n) {
if (n % 2 == 0) {
x = mul(x, x);
n /= 2;
} else {
res = mul(res, x);
n--;
}
}
return res;
}
const int G = 3;
void fft(vector<int>& a, bool inv = false) {
int n = a.size();
int k = 0;
while ((1 << k) < n) ++k;
static vector<int> rev, power = {0, 1};
rev.resize(n);
rev[0] = 0;
for (int i = 1; i < n; ++i) {
rev[i] = rev[i / 2] / 2 + ((i & 1) << (k - 1));
if (i < rev[i]) {
swap(a[i], a[rev[i]]);
}
}
for (int l = 1; l < n; l *= 2) {
if ((int)power.size() == l) {
power.resize(2 * l);
int w = pw(G, (MOD - 1) / 2 / l);
for (int i = l; i < 2 * l; ++i) {
power[i] = power[i / 2];
if (i & 1) {
power[i] = mul(power[i], w);
}
}
}
for (int i = 0; i < n; i += 2 * l) {
for (int j = 0; j < l; ++j) {
int x = a[i + j], y = mul(a[i + j + l], power[j + l]);
a[i + j] = add(x, y);
a[i + j + l] = sub(x, y);
}
}
}
if (inv) {
int anti = pw(n, MOD - 2);
for (int i = 0; i < n; ++i) {
a[i] = mul(a[i], anti);
}
reverse(a.begin() + 1, a.end());
}
}
vector<int> operator*(vector<int> a, vector<int> b) {
int sz = a.size() + b.size() - 1;
int k = 0;
while ((1 << k) < sz) ++k;
a.resize(1 << k);
b.resize(1 << k);
fft(a);
fft(b);
for (int i = 0; i < (1 << k); ++i) {
a[i] = mul(a[i], b[i]);
}
fft(a, true);
a.resize(sz);
return a;
}
const int MAXN = 2e5 + 100;
vector<int> powers[MAXN];
int sum = 0;
void calc_powers(int len, const vector<int>& a) {
/// cerr << len << endl;
if (!powers[len].empty()) return;
if (len == 0) {
powers[len] = {1};
return;
}
if (len == 1) {
powers[len] = a;
sum += a.size();
return;
}
calc_powers(len / 2, a);
calc_powers((len + 1) / 2, a);
powers[len] = powers[len / 2] * powers[(len + 1) / 2];
sum += powers[len].size();
}
vector<int> operator+(const vector<int>& a, const vector<int>& b) {
vector<int> c(max(a.size(), b.size()));
for (int i = 0; i < (int)a.size(); ++i) {
c[i] = add(c[i], a[i]);
}
for (int i = 0; i < (int)b.size(); ++i) {
c[i] = add(c[i], b[i]);
}
return c;
}
vector<int> solve(int len, vector<int> cur) {
if (len == 1) {
auto res = cur * powers[1];
for (int i = 2; i < (int)res.size(); ++i) {
res[i - 2] = res[i];
}
res.pop_back();
res.pop_back();
return res;
}
int len1 = len / 2;
int len2 = (len + 1) / 2;
vector<int> to_add = {0};
if ((int)cur.size() > 2 * len1) {
to_add.resize(cur.size() - 2 * len1);
for (int i = 0; i < (int)to_add.size(); ++i) {
to_add[i] = cur[i + 2 * len1];
}
to_add = to_add * powers[len1];
cur.resize(2 * len1);
}
cur = solve(len1, cur) + to_add;
to_add = {0};
if ((int)cur.size() > 2 * len2) {
to_add.resize(cur.size() - 2 * len2);
for (int i = 0; i < (int)to_add.size(); ++i) {
to_add[i] = cur[i + 2 * len2];
}
to_add = to_add * powers[len2];
cur.resize(2 * len2);
}
cur = solve(len2, cur) + to_add;
return cur;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> p(5);
int sum = 0;
for (int i = 0; i < 5; ++i) {
cin >> p[i];
sum += p[i];
}
if (m == 0) {
cout << "1\n";
return 0;
}
sum = pw(sum, MOD - 2);
for (int i = 0; i < 5; ++i) {
p[i] = mul(p[i], sum);
}
/**vector<int> slow(n + 1);
slow[n] = 1;
for (int i = 0; i < m; ++i) {
vector<int> slow2(slow.size() + 2);
for (int i = 0; i < (int)slow.size(); ++i) {
for (int j = 0; j < 5; ++j) {
if (i + j - 2 < 0) continue;
slow2[i + j - 2] = add(slow2[i + j - 2], mul(slow[i], p[j]));
}
}
slow = move(slow2);
}
int ans_slow = 0;
for (int i = 0; i < (int)slow.size(); ++i) {
ans_slow = add(ans_slow, slow[i]);
}
cout << ans_slow << "\n";*/
/// cout << (1 << 17) - 1 << endl;
calc_powers(m, p);
/// cerr << ::sum << endl;
vector<int> start(n + 1);
start[n] = 1;
auto res = solve(m, start);
int ans = 0;
for (int i = 0; i < (int)res.size(); ++i) {
ans = add(ans, res[i]);
}
cout << ans << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8284kb
input:
1 1 1 1 1 1 1
output:
399297742
result:
ok 1 number(s): "399297742"
Test #2:
score: 0
Accepted
time: 1871ms
memory: 23880kb
input:
100000 100000 1234 4567 7890 4321 54321
output:
348074135
result:
ok 1 number(s): "348074135"
Test #3:
score: 0
Accepted
time: 1851ms
memory: 23792kb
input:
100000 100000 1 2 3 4 5
output:
639188342
result:
ok 1 number(s): "639188342"
Test #4:
score: 0
Accepted
time: 1862ms
memory: 23872kb
input:
100000 100000 5 4 3 2 1
output:
211669278
result:
ok 1 number(s): "211669278"
Test #5:
score: 0
Accepted
time: 2ms
memory: 8336kb
input:
0 0 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 922ms
memory: 15356kb
input:
1 50000 1 1 1 1 1
output:
548880636
result:
ok 1 number(s): "548880636"
Test #7:
score: 0
Accepted
time: 4ms
memory: 9332kb
input:
50000 1 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 1837ms
memory: 23808kb
input:
100000 100000 234 666 7655 12234 0
output:
45268602
result:
ok 1 number(s): "45268602"
Test #9:
score: 0
Accepted
time: 1956ms
memory: 27228kb
input:
99999 99999 12345 54332 12345 65432 34444
output:
360543661
result:
ok 1 number(s): "360543661"
Test #10:
score: 0
Accepted
time: 1896ms
memory: 25632kb
input:
99998 99998 1 1 1 1 1
output:
602326230
result:
ok 1 number(s): "602326230"
Test #11:
score: 0
Accepted
time: 1959ms
memory: 26984kb
input:
99998 99997 1 1 1 1 1
output:
159752985
result:
ok 1 number(s): "159752985"
Test #12:
score: 0
Accepted
time: 1882ms
memory: 24408kb
input:
99997 100000 1 2 3 4 5
output:
139603712
result:
ok 1 number(s): "139603712"
Test #13:
score: 0
Accepted
time: 1951ms
memory: 27004kb
input:
100000 99997 1 2 2 1 3232323
output:
363030953
result:
ok 1 number(s): "363030953"
Test #14:
score: 0
Accepted
time: 0ms
memory: 8496kb
input:
0 0 0 0 1 0 0
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 127ms
memory: 9592kb
input:
10000 10000 91095828 93770094 5303328 491263 50290308
output:
135900098
result:
ok 1 number(s): "135900098"
Test #16:
score: 0
Accepted
time: 145ms
memory: 9908kb
input:
9226 9995 62366139 253808 1929312 491263 4375669
output:
812662634
result:
ok 1 number(s): "812662634"
Test #17:
score: 0
Accepted
time: 117ms
memory: 9996kb
input:
18641 10000 1061 4359 1330 13764 16043
output:
112339046
result:
ok 1 number(s): "112339046"
Extra Test:
score: 0
Extra Test Passed