QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#532167 | #7927. Fortune Telling | WaterSun | WA | 0ms | 4056kb | C++14 | 2.0kb | 2024-08-25 00:59:03 | 2024-08-25 00:59:03 |
Judging History
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'