QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#231157 | #7634. Cards | ucup-team484# | AC ✓ | 8372ms | 9448kb | C++17 | 3.9kb | 2023-10-29 02:48:31 | 2023-10-29 02:48:31 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e6 + 5;
const int BLOCK = 900;
int pw(int x, int y) {
int r = 1;
for (; y; y /= 2, x = x * 1ll * x % mod)
if (y & 1)
r = r * 1ll * x % mod;
return r;
}
const int root = 565042129; // 3^(119 * 2^3)
const int root_pw = 1 << 20; // order of root
const int root_1 = pw(root, mod - 2);
void fft(vector<int> & a, bool invert) {
int n = a.size();
for(int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (j ^= bit; !(j&bit); j ^= (bit>>=1));
if (i < j)
swap(a[i], a[j]);
}
for(int len = 2; len <= n; len <<= 1) {
int wlen = invert ? root_1 : root;
for(int i = len; i < root_pw; i <<= 1)
wlen = 1LL * wlen * wlen % mod;
for(int i = 0; i < n; i += len) {
for(int j=i, w=1; j < i + len/2; j++) {
int u=a[j], v=1LL*a[j+len/2]*w % mod;
a[j] = u+v < mod ? u+v : u+v-mod;
a[j+len/2] = u-v < 0 ? u-v+mod : u-v;
w = 1LL * w * wlen % mod;
}
}
}
if(invert) {
int n_1 = pw(n, mod - 2);
for(int & x : a)
x = 1LL * x * n_1 % mod;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m, s = 0; cin >> n >> m;
if (m == 0) {
cout << "1\n";
return 0;
}
int mm = 1;
while (mm <= 4 * m)
mm *= 2;
vector<int> a(5);
for (int i = 0; i < 5; i++) {
cin >> a[i];
s += a[i];
}
s = pw(s, mod - 2);
for (int i = 0; i < 5; i++)
a[i] = a[i] * 1ll * s % mod;
int lo = max(0, 2 * m - n);
// vector<int> dp(4 * m + 1);
// dp[2 * m] = 1;
// for (int i = 0; i < m; i++) {
// vector<int> ndp(4 * m + 1);
// for (int j = lo; j <= 4 * m; j++) {
// for (int k = -2; k <= 2; k++)
// if (lo <= k + j && k + j <= 4 * m)
// ndp[k + j] = (ndp[k + j] + dp[j] * 1ll * a[k + 2]) % mod;
// }
// swap(dp, ndp);
// }
// for (int i = 0; i <= 4 * m; i++) {
// cout << dp[i] << " ";
// }
// cout << endl;
// int ans = 0;
// for (int i = max(0, 2 * m - n); i <= 4 * m; i++) {
// ans += dp[i];
// if (ans >= mod)
// ans -= mod;
// }
// cout << ans << "\n";
vector<int> cur(mm), arr(mm);
cur[2 * m] = 1;
for (int i = 0; i < 5; i++)
arr[i] = a[i];
fft(arr, 0);
for (int i = 0; i < mm; i++)
arr[i] = pw(arr[i], BLOCK);
// fft(arr, 1);
for (int i = 0; i < m;) {
if (i + BLOCK >= m) {
vector<int> nx(mm);
for (int j = lo; j <= 4 * m; j++) {
for (int k = -2; k <= 2; k++)
if (lo <= k + j && k + j <= 4 * m)
nx[k + j] = (nx[k + j] + cur[j] * 1ll * a[k + 2]) % mod;
}
swap(cur, nx);
i++;
continue;
}
vector<int> small(4 * BLOCK), tail(mm);
for (int j = lo; j <= 4 * m && j - lo < 2 * BLOCK; j++) {
small[j - lo] = cur[j];
cur[j] = 0;
}
for (int it = 0; it < BLOCK; it++) {
vector<int> tmp(4 * BLOCK);
for (int j = 0; j < 4 * BLOCK; j++) {
for (int k = -2; k <= 2; k++)
if (0 <= k + j && k + j < 4 * BLOCK)
tmp[k + j] = (tmp[k + j] + small[j] * 1ll * a[k + 2]) % mod;
}
swap(small, tmp);
}
for (int j = 0; j + lo + 2 * BLOCK <= 4 * m; j++) {
cur[j] = cur[j + lo + 2 * BLOCK];
cur[j + lo + 2 * BLOCK] = 0;
}
fft(cur, 0);
for (int j = 0; j < mm; j++)
cur[j] = cur[j] * 1ll * arr[j] % mod;
fft(cur, 1);
for (int j = 4 * m; j >= lo; j--) {
cur[j] = cur[j - lo];
cur[j - lo] = 0;
}
for (int j = lo; j <= 4 * m && j - lo < 4 * BLOCK; j++) {
cur[j] += small[j - lo];
if (cur[j] >= mod)
cur[j] -= mod;
}
i += BLOCK;
}
// for (int i = 0; i <= 4 * m; i++) {
//// cout << cur[i] << " ";
// assert(cur[i] == dp[i]);
// }
// cout << endl;
int ans = 0;
for (int i = lo; i <= 4 * m; i++) {
ans += cur[i];
if (ans >= mod)
ans -= mod;
}
cout << ans << "\n";
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
1 1 1 1 1 1 1
output:
399297742
result:
ok 1 number(s): "399297742"
Test #2:
score: 0
Accepted
time: 8357ms
memory: 9380kb
input:
100000 100000 1234 4567 7890 4321 54321
output:
348074135
result:
ok 1 number(s): "348074135"
Test #3:
score: 0
Accepted
time: 8329ms
memory: 9444kb
input:
100000 100000 1 2 3 4 5
output:
639188342
result:
ok 1 number(s): "639188342"
Test #4:
score: 0
Accepted
time: 8360ms
memory: 9368kb
input:
100000 100000 5 4 3 2 1
output:
211669278
result:
ok 1 number(s): "211669278"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
0 0 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 3106ms
memory: 6284kb
input:
1 50000 1 1 1 1 1
output:
548880636
result:
ok 1 number(s): "548880636"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
50000 1 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 8343ms
memory: 9448kb
input:
100000 100000 234 666 7655 12234 0
output:
45268602
result:
ok 1 number(s): "45268602"
Test #9:
score: 0
Accepted
time: 8343ms
memory: 9448kb
input:
99999 99999 12345 54332 12345 65432 34444
output:
360543661
result:
ok 1 number(s): "360543661"
Test #10:
score: 0
Accepted
time: 8349ms
memory: 9364kb
input:
99998 99998 1 1 1 1 1
output:
602326230
result:
ok 1 number(s): "602326230"
Test #11:
score: 0
Accepted
time: 8353ms
memory: 9448kb
input:
99998 99997 1 1 1 1 1
output:
159752985
result:
ok 1 number(s): "159752985"
Test #12:
score: 0
Accepted
time: 8372ms
memory: 9368kb
input:
99997 100000 1 2 3 4 5
output:
139603712
result:
ok 1 number(s): "139603712"
Test #13:
score: 0
Accepted
time: 8326ms
memory: 9368kb
input:
100000 99997 1 2 2 1 3232323
output:
363030953
result:
ok 1 number(s): "363030953"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
0 0 0 0 1 0 0
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 305ms
memory: 3840kb
input:
10000 10000 91095828 93770094 5303328 491263 50290308
output:
135900098
result:
ok 1 number(s): "135900098"
Test #16:
score: 0
Accepted
time: 302ms
memory: 3840kb
input:
9226 9995 62366139 253808 1929312 491263 4375669
output:
812662634
result:
ok 1 number(s): "812662634"
Test #17:
score: 0
Accepted
time: 318ms
memory: 3828kb
input:
18641 10000 1061 4359 1330 13764 16043
output:
112339046
result:
ok 1 number(s): "112339046"
Extra Test:
score: 0
Extra Test Passed