QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#532167#7927. Fortune TellingWaterSunWA 0ms4056kbC++142.0kb2024-08-25 00:59:032024-08-25 00:59:03

Judging History

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

  • [2024-08-25 00:59:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4056kb
  • [2024-08-25 00:59:03]
  • 提交

answer

#include <bits/stdc++.h>
#define re register
#define int long long
#define Add(a,b) (((a) + (b)) % mod)
#define Mul(a,b) ((a) * (b) % mod)

using namespace std;

typedef vector<int> vi;
const int N = 3e5 + 10,mod = 998244353;
int n;
int inv[N];
unordered_map<int,vi> dp;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline int qmi(int a,int b){
    int res = 1;
    while (b){
        if (b & 1) res = Mul(res,a);
        a = Mul(a,a); b >>= 1;
    }
    return res;
}

inline void dfs(int n){
    if (dp.count(n)) return;
    vi res(n);
    if (n <= 6){
        for (re int i = 0;i < n;i++) res[i] = inv[n];
        // cerr << n << " " << inv[n] << " ???\n";
    }
    else{
        dfs(5 * n / 6);
        dfs(5 * n / 6 + 1);
        const vi a = dp[5 * n / 6],b = dp[5 * n / 6 + 1];
        // cerr << n << " begin:\n";
        for (re int p = 0;p < 6;p++){
            int id = 0;
            for (re int i = 0;i < n;i++){
                if (i % 6 == p) continue;
                if (n % 6 <= p) res[i] = Add(res[i],b[id]);
                // ,cerr << i << " " << id << " " << b[id] << " second\n";
                else res[i] = Add(res[i],a[id]);
                // ,cerr << i << " " << id << " " << a[id] << " first\n";
                // cerr << i << " " << id << " !!!\n";
                id++;
            }
        }
        // cerr << n << " begin:\n";
        // for (re int i = 0;i < n;i++) cerr << res[i] << " "; cerr << "\n";
        for (re int i = 0;i < n;i++) res[i] = Mul(res[i],inv[6]);
    }
    dp[n] = res;
}

signed main(){
    n = read();
    for (re int i = 1;i <= 6;i++) inv[i] = qmi(i,mod - 2);
    dfs(n);
    for (re int i = 0;i < n;i++) printf("%lld\n",dp[n][i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3

output:

332748118
332748118
332748118

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 4056kb

input:

7

output:

305019108
876236710
876236710
876236710
876236710
876236710
305019108

result:

ok 7 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

8

output:

64701023
112764640
160828257
160828257
160828257
160828257
112764640
64701023

result:

ok 8 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

10

output:

409773145
853745402
299473306
743445563
189173467
189173467
743445563
299473306
853745402
409773145

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

11

output:

989514850
873566509
757618168
641669827
525721486
409773145
525721486
641669827
757618168
873566509
989514850

result:

ok 11 lines

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 4052kb

input:

12

output:

159099473
81800579
4501685
925447144
848148250
770849356
175103562
252402456
329701350
407000244
484299138
561598032

result:

wrong answer 1st lines differ - expected: '175103562', found: '159099473'