QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#231962 | #7634. Cards | jovanbengin | AC ✓ | 8810ms | 46876kb | C++20 | 4.7kb | 2023-10-29 18:27:36 | 2023-10-29 18:27:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define si(x) int(x.size())
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int MOD = 998244353;
int add(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
int mul(int a, int b){ return (1LL*a*b)%MOD; }
int sub(int a, int b){ return add(a, MOD - b); }
int pw(int a, int b){
if(b == 0) return 1;
int res = pw(a, b/2);
res = mul(res, res);
if(b%2) res = mul(res, a);
return res;
}
const int root = pw(3, 119);
const int root_1 = pw(root, MOD - 2);
const int root_pw = 1 << 23;
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; bit >>= 1)
j ^= bit;
j ^= bit;
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 = (int)(1LL * wlen * wlen % MOD);
for (int i = 0; i < n; i += len) {
int w = 1;
for (int j = 0; j < len / 2; j++) {
int u = a[i+j], v = (int)(1LL * a[i+j+len/2] * w % MOD);
a[i+j] = u + v < MOD ? u + v : u + v - MOD;
a[i+j+len/2] = u - v >= 0 ? u - v : u - v + MOD;
w = (int)(1LL * w * wlen % MOD);
}
}
}
if (invert) {
int n_1 = pw(n, MOD - 2);
for (int & x : a)
x = mul(x, n_1);
}
}
vector <int> multiply(vector <int> &va, vector <int> &vb){
int ns = si(va) + si(vb);
int j = 1;
while(j < ns) j *= 2;
while(si(va) < j) va.pb(0);
while(si(vb) < j) vb.pb(0);
fft(va, 0);
fft(vb, 0);
for(int i=0; i<si(va); i++){
va[i] = mul(va[i], vb[i]);
}
fft(va, 1);
while(si(va) && va.back() == 0) va.pop_back();
return va;
}
const int N = 100000;
const int K = 1500;
int sol[2][3*N+5];
int dp[2][4*K+5];
int kolko[K+5][4*K+5]; /// prob posle i poteza promena = j
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, m;
cin >> n >> m;
vector <int> p(5);
int sump = 0;
for(int i=0; i<5; i++){
cin >> p[i];
sump = add(sump, p[i]);
}
for(int i=0; i<5; i++){
p[i] = mul(p[i], pw(sump, MOD - 2));
}
kolko[0][2*K] = 1;
for(int t=0; t<K; t++){
for(int i=0; i<=4*K; i++){
for(int j=-2; j<=2; j++){
if(i+j >= 0){
kolko[t+1][i+j] = add(kolko[t+1][i+j], mul(kolko[t][i], p[j+2]));
}
}
}
}
int x = 0;
sol[0][n] = 1;
while(x + K <= m){
vector <int> poly;
for(int i=0; i<2*K; i++){
poly.pb(0);
dp[0][i] = sol[0][i];
}
for(int i=2*K; i<=4*K; i++){
dp[0][i] = 0;
}
for(int i=2*K; i<=3*N; i++){
poly.pb(sol[0][i]);
}
while(si(poly) && poly.back() == 0) poly.pop_back();
vector <int> chg;
for(int i=-2*K; i<=2*K; i++){
chg.pb(kolko[K][i+2*K]);
}
vector <int> vec = multiply(poly, chg);
for(int i=0; i<si(vec); i++){
if(i >= 2*K){
sol[1][i-2*K] = add(sol[1][i-2*K], vec[i]);
}
}
for(int turns=0; turns<K; turns++){
for(int i=0; i<=4*K; i++){
for(int j=-2; j<=2; j++){
if(i+j >= 0){
dp[1][i+j] = add(dp[1][i+j], mul(dp[0][i], p[j+2]));
}
}
}
for(int i=0; i<=4*K; i++){
dp[0][i] = dp[1][i];
dp[1][i] = 0;
}
}
for(int i=0; i<=4*K; i++){
sol[1][i] = add(sol[1][i], dp[0][i]);
}
for(int i=0; i<=3*N; i++){
sol[0][i] = sol[1][i];
sol[1][i] = 0;
}
x += K;
}
while(x < m){
x++;
for(int i=0; i<=3*N; i++){
for(int j=-2; j<=2; j++){
if(i+j >= 0){
sol[1][i+j] = add(sol[1][i+j], mul(sol[0][i], p[j+2]));
}
}
}
for(int i=0; i<=3*N; i++){
sol[0][i] = sol[1][i];
sol[1][i] = 0;
}
}
int res = 0;
for(int i=0; i<=3*N; i++){
res = add(res, sol[0][i]);
}
cout << res << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 72ms
memory: 41036kb
input:
1 1 1 1 1 1 1
output:
399297742
result:
ok 1 number(s): "399297742"
Test #2:
score: 0
Accepted
time: 8788ms
memory: 46752kb
input:
100000 100000 1234 4567 7890 4321 54321
output:
348074135
result:
ok 1 number(s): "348074135"
Test #3:
score: 0
Accepted
time: 8776ms
memory: 46812kb
input:
100000 100000 1 2 3 4 5
output:
639188342
result:
ok 1 number(s): "639188342"
Test #4:
score: 0
Accepted
time: 8795ms
memory: 46736kb
input:
100000 100000 5 4 3 2 1
output:
211669278
result:
ok 1 number(s): "211669278"
Test #5:
score: 0
Accepted
time: 64ms
memory: 38796kb
input:
0 0 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 3410ms
memory: 43904kb
input:
1 50000 1 1 1 1 1
output:
548880636
result:
ok 1 number(s): "548880636"
Test #7:
score: 0
Accepted
time: 60ms
memory: 41156kb
input:
50000 1 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 8124ms
memory: 44076kb
input:
100000 100000 234 666 7655 12234 0
output:
45268602
result:
ok 1 number(s): "45268602"
Test #9:
score: 0
Accepted
time: 8781ms
memory: 46784kb
input:
99999 99999 12345 54332 12345 65432 34444
output:
360543661
result:
ok 1 number(s): "360543661"
Test #10:
score: 0
Accepted
time: 8810ms
memory: 46876kb
input:
99998 99998 1 1 1 1 1
output:
602326230
result:
ok 1 number(s): "602326230"
Test #11:
score: 0
Accepted
time: 8790ms
memory: 46752kb
input:
99998 99997 1 1 1 1 1
output:
159752985
result:
ok 1 number(s): "159752985"
Test #12:
score: 0
Accepted
time: 8804ms
memory: 46732kb
input:
99997 100000 1 2 3 4 5
output:
139603712
result:
ok 1 number(s): "139603712"
Test #13:
score: 0
Accepted
time: 8785ms
memory: 46804kb
input:
100000 99997 1 2 2 1 3232323
output:
363030953
result:
ok 1 number(s): "363030953"
Test #14:
score: 0
Accepted
time: 57ms
memory: 38988kb
input:
0 0 0 0 1 0 0
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 2512ms
memory: 44888kb
input:
10000 10000 91095828 93770094 5303328 491263 50290308
output:
135900098
result:
ok 1 number(s): "135900098"
Test #16:
score: 0
Accepted
time: 2495ms
memory: 43816kb
input:
9226 9995 62366139 253808 1929312 491263 4375669
output:
812662634
result:
ok 1 number(s): "812662634"
Test #17:
score: 0
Accepted
time: 2522ms
memory: 44036kb
input:
18641 10000 1061 4359 1330 13764 16043
output:
112339046
result:
ok 1 number(s): "112339046"
Extra Test:
score: 0
Extra Test Passed