QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#228077 | #7634. Cards | ucup-team1209# | AC ✓ | 3959ms | 34528kb | C++20 | 3.0kb | 2023-10-28 11:33:50 | 2023-10-28 11:33:50 |
Judging History
你现在查看的是测评时间为 2023-10-28 11:33:50 的历史记录
- [2023-10-28 19:27:18]
- hack成功,自动添加数据
- (//qoj.ac/hack/414)
- [2023-10-28 11:33:50]
- 提交
answer
#include<bits/stdc++.h>
using std::cin, std::cout;
using u64 = unsigned long long;
using u128 = __int128_t;
const int mod = 998244353;
const int N = 1 << 20;
int rev[N], wn[N], lim, invlim;
int pow(int a, int b, int ans = 1) {
for(;b;b >>= 1, a = (u64) a * a % mod) if(b & 1)
ans = (u64) ans * a % mod;
return ans;
}
void init(int len) {
lim = 2 << std::__lg(len - 1);
invlim = mod - (mod - 1) / lim;
for(static int i = 1;i < lim;i += i) {
wn[i] = 1;
const int w = pow(3, mod / i / 2);
for(int j = 1;j < i;++j) {
wn[i + j] = (u64) wn[i + j - 1] * w % mod;
}
}
for(int i = 1;i < lim;++i) {
rev[i] = rev[i >> 1] >> 1 | (i % 2u * lim / 2);
}
}
void DFT(u64 * a) {
static u64 t[N];
for(int i = 0;i < lim;++i) {
t[i] = a[rev[i]];
}
for(int i = 1;i < lim;i += i) {
for(int j = 0;j < lim;j += i + i) {
for(int k = 0;k < i;++k) {
const u64 x = t[i + j + k] * wn[i + k] % mod;
t[i + j + k] = t[k + j] + mod - x;
t[k + j] += x;
}
}
}
for(int i = 0;i < lim;++i) {
a[i] = t[i] % mod;
}
}
void IDFT(u64 * a) {
DFT(a), std::reverse(a + 1, a + lim);
for(int i = 0;i < lim;++i) {
a[i] = (u64) a[i] * invlim % mod;
}
}
int n, m;
int x[5];
u64 h[N];
u64 f[N], g[N];
u64 tmp[N];
const int B = 1000;
int main() {
#ifdef zqj
// freopen("$.in", "r", stdin);
#endif
cin >> n >> m;
int sum = 0;
for(int i = 0;i < 5;++i) cin >> x[i], sum += x[i];
sum = pow(sum, mod - 2);
for(int i = 0;i < 5;++i) {
x[i] = (u64) x[i] * sum % mod;
h[i] = x[i];
}
f[0] = 1;
init((m + B) * 4);
DFT(h);
for(int i = 0;i < lim;++i) {
h[i] = pow(h[i], B);
}
for(int i = 1;i <= m % B;++i) {
for(int j = 0;j <= m * 4;++j) {
g[j + 0] += f[j] * x[0];
g[j + 1] += f[j] * x[1];
g[j + 2] += f[j] * x[2];
g[j + 3] += f[j] * x[3];
g[j + 4] += f[j] * x[4];
}
// x => x + n - 2 * i
const int kill = 2 * i - n;
for(int j = 0;j <= m * 4;++j) {
f[j] = g[j] % mod;
g[j] = 0;
}
for(int i = 0;i < kill;++i) {
f[i] = 0;
}
}
for(int i = m % B + 1;i <= m;i += B) {
const int prekill = std::max(2 * (i - 1) - n, 0);
const int kill = std::max(2 * (i + B - 1) - n, 0);
for(int j = kill;j <= m * 4;++j) {
tmp[j] = f[j];
f[j] = 0;
}
DFT(tmp);
for(int j = 0;j < lim;++j) {
tmp[j] = (u64) tmp[j] * h[j] % mod;
}
IDFT(tmp);
for(int k = 0;k < B;++k) {
const int R = kill + k * 4 + 4;
for(int j = prekill;j < R;++j) {
g[j + 0] += f[j] * x[0];
g[j + 1] += f[j] * x[1];
g[j + 2] += f[j] * x[2];
g[j + 3] += f[j] * x[3];
g[j + 4] += f[j] * x[4];
}
for(int j = prekill;j < R;++j) {
f[j] = g[j] % mod;
g[j] = 0;
}
for(int j = prekill;j < std::max(2 * (i + k) - n, 0);++j) {
f[j] = 0;
}
}
for(int j = kill;j <= m * 4;++j) {
f[j] = (f[j] + tmp[j]) % mod;
}
memset(tmp, 0, lim << 2);
memset(f, 0, kill << 2);
}
u64 ans = 0;
for(int j = 0;j <= m * 4;++j) {
ans += f[j];
}
cout << ans % mod << '\n';
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11876kb
input:
1 1 1 1 1 1 1
output:
399297742
result:
ok 1 number(s): "399297742"
Test #2:
score: 0
Accepted
time: 3059ms
memory: 32128kb
input:
100000 100000 1234 4567 7890 4321 54321
output:
348074135
result:
ok 1 number(s): "348074135"
Test #3:
score: 0
Accepted
time: 3048ms
memory: 32124kb
input:
100000 100000 1 2 3 4 5
output:
639188342
result:
ok 1 number(s): "639188342"
Test #4:
score: 0
Accepted
time: 3059ms
memory: 32220kb
input:
100000 100000 5 4 3 2 1
output:
211669278
result:
ok 1 number(s): "211669278"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11908kb
input:
0 0 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 966ms
memory: 20064kb
input:
1 50000 1 1 1 1 1
output:
548880636
result:
ok 1 number(s): "548880636"
Test #7:
score: 0
Accepted
time: 2ms
memory: 11908kb
input:
50000 1 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 3056ms
memory: 32280kb
input:
100000 100000 234 666 7655 12234 0
output:
45268602
result:
ok 1 number(s): "45268602"
Test #9:
score: 0
Accepted
time: 3958ms
memory: 34436kb
input:
99999 99999 12345 54332 12345 65432 34444
output:
360543661
result:
ok 1 number(s): "360543661"
Test #10:
score: 0
Accepted
time: 3957ms
memory: 34524kb
input:
99998 99998 1 1 1 1 1
output:
602326230
result:
ok 1 number(s): "602326230"
Test #11:
score: 0
Accepted
time: 3940ms
memory: 32540kb
input:
99998 99997 1 1 1 1 1
output:
159752985
result:
ok 1 number(s): "159752985"
Test #12:
score: 0
Accepted
time: 3054ms
memory: 32212kb
input:
99997 100000 1 2 3 4 5
output:
139603712
result:
ok 1 number(s): "139603712"
Test #13:
score: 0
Accepted
time: 3959ms
memory: 34528kb
input:
100000 99997 1 2 2 1 3232323
output:
363030953
result:
ok 1 number(s): "363030953"
Test #14:
score: 0
Accepted
time: 0ms
memory: 11888kb
input:
0 0 0 0 1 0 0
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 87ms
memory: 21024kb
input:
10000 10000 91095828 93770094 5303328 491263 50290308
output:
135900098
result:
ok 1 number(s): "135900098"
Test #16:
score: 0
Accepted
time: 167ms
memory: 12896kb
input:
9226 9995 62366139 253808 1929312 491263 4375669
output:
812662634
result:
ok 1 number(s): "812662634"
Test #17:
score: 0
Accepted
time: 66ms
memory: 14880kb
input:
18641 10000 1061 4359 1330 13764 16043
output:
112339046
result:
ok 1 number(s): "112339046"
Extra Test:
score: 0
Extra Test Passed