QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#231962#7634. CardsjovanbenginAC ✓8810ms46876kbC++204.7kb2023-10-29 18:27:362023-10-29 18:27:36

Judging History

你现在查看的是最新测评结果

  • [2023-10-29 18:27:36]
  • 评测
  • 测评结果:AC
  • 用时:8810ms
  • 内存:46876kb
  • [2023-10-29 18:27:36]
  • 提交

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,我给组数据试试?

詳細信息

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