QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#926914#9627. 算术shendeliliang#WA 7ms3584kbC++203.6kb2025-03-06 14:36:412025-03-06 14:36:46

Judging History

This is the latest submission verdict.

  • [2025-03-06 14:36:46]
  • Judged
  • Verdict: WA
  • Time: 7ms
  • Memory: 3584kb
  • [2025-03-06 14:36:41]
  • Submitted

answer

#include<bits/stdc++.h>
using ll = long long;
#define int ll
using namespace std;


const int mod = 998244353;

class modInt{ // 有模数
    public:
        modInt(const long long x=0): num(x%mod){}
        explicit operator long long() {
            return num;
        }
        friend std::ostream& operator<< (std::ostream& out, const modInt& item) {
            out << item.num;
            return out;
        }
        friend std::istream& operator>> (std::istream& in, modInt& item) {
            in >> item.num;
            return in;
        }
        friend modInt operator^ (modInt a, long long b) {
            modInt res(1);
            if (b == 0) {
                return res;
            }
            for( ; b; a = a * a, b >>= 1)
                if(b&1)
                    res = res * a;
            return res;
        }
        static modInt inv(const modInt x) {
            return x ^ (mod-2);
        }
        friend modInt operator+ (const modInt& lhs, const modInt& rhs) {
            return (lhs.num + rhs.num) % mod;
        }
        modInt& operator+= (const modInt& ano) {
            num = (num + ano.num) % mod;
            return *this;
        }
        friend modInt operator* (const modInt& lhs, const modInt& rhs) {
            return lhs.num * rhs.num % mod;
        }
        modInt& operator*= (const modInt& ano) {
            num = num * ano.num % mod;
            return *this;
        }
        friend modInt operator- (const modInt& lhs, const modInt& rhs) {
            long long tmp = lhs.num-rhs.num;
            return tmp<0 ? tmp+mod : tmp; 
        }
        modInt& operator-= (const modInt& ano) {
            *this = *this - ano;
            return *this;
        }
        friend modInt operator/ (const modInt& lhs, const modInt& rhs) {
            return (lhs * inv(rhs)).num % mod;
        }
        modInt& operator/= (const modInt& ano) {
            *this = *this / ano;
            return *this;
        }
        long long toLL() {
            return num;
        }
    private:
        long long num;
};


int dp[101];

void solve() {
    vector<int> a(11, 0);
    for (int i = 1; i <= 9; ++i) {
        cin >> a[i];
    }
    modInt ans = 1;
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 2; i <= 9; ++i) {
        for (int j = 1; j <= a[i]; ++j) {
            q.push(i);
        }
        if (a[i] > 0) {
            ans *= (modInt(i) ^ (a[i]));
        }
        // cout << i << " " << a[i] << " " << ans << "\n";
    }
    ans *= modInt(dp[a[1]]);
    if (q.size() == 0) {
        cout << ans << "\n";
        return;
    }
    //cout << ans << '\n';
    for (int i = a[1]; i > 0; --i) {
        int x = q.top();
        q.pop();
        // x -> x + 1
        // dp[i] -> dp[i-1]
        // * (x+1) / x * (dp[i-1] / dp[i])
        // * (x+1) * dp[i-1] / (x * dp[i])
        // cout << (x * dp[i]) << ' ' << ((x+1) * dp[i-1]) << '\n';
        if (x * dp[i] <= (x+1) * dp[i-1]) {
            ans *= modInt(x+1) * dp[i-1] / (x * dp[i]);
            q.push(x+1);
        } else {
            break;
        }
    }
    cout << ans << "\n";
}

signed main() {
    int T;
    dp[0] = 0;
    for (int i = 1; i <= 100; ++i) {
        dp[i] = dp[i-1] + 1;
        for (int j = 1; j < i; ++j) {
            dp[i] = max(dp[i], dp[j] * dp[i-j]);
        }
    }
    dp[0] = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

/*
7
5 3 0 0 0 0 0 0 0
4 1 1 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 2
99 88 77 66 55 44 33 22 11
100 90 80 70 60 50 40 30 20
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

7
5 3 0 0 0 0 0 0 0
4 1 1 1 0 0 0 0 0
1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 2
99 88 77 66 55 44 33 22 11
100 90 80 70 60 50 40 30 20

output:

54
108
1
10
90
90553232
143532368

result:

ok 7 lines

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 3456kb

input:

1000
22 80 50 23 35 71 81 70 96
40 33 36 2 51 52 96 5 32
56 35 85 13 58 80 26 14 31
60 21 8 19 79 5 94 44 33
85 55 10 59 76 98 28 22 69
14 72 40 14 100 68 5 18 69
95 42 51 0 32 97 37 34 85
54 33 18 40 34 10 72 72 68
81 47 80 23 23 68 40 3 71
58 7 36 79 89 83 5 68 16
30 3 82 79 35 28 30 55 88
17 86 2...

output:

113014030
321820208
765709043
819408880
639261805
241458014
7172464
780360907
240853384
151457742
298466126
259030391
124742738
698195085
493291429
982170221
409158325
951979430
141426731
501117393
440485591
163247072
78098984
910409582
308024444
168349368
423889166
815038086
827159852
914298923
465...

result:

wrong answer 1st lines differ - expected: '376701872', found: '113014030'