QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#532172 | #7927. Fortune Telling | WaterSun | WA | 0ms | 3884kb | C++14 | 1.9kb | 2024-08-25 00:59:48 | 2024-08-25 00:59:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int mod = 998244353;
int add(int a, int b)
{
return a + b < mod ? a + b : a + b - mod;
}
int sub(int a, int b)
{
return a - b >= 0 ? a - b : a - b + mod;
}
int mult(int a, int b)
{
return (LL) a * b % mod;
}
int binpow(int a, int n)
{
int res = 1;
while(n)
{
if(n & 1)
res = mult(res, a);
a = mult(a, a);
n /= 2;
}
return res;
}
map<int, VI> dp;
const int ml6 = binpow(6, mod - 2);
LL sum = 0;
void solve(int n)
{
if(dp.count(n))
return;
sum += n;
if(n <= 6)
{
VI res(n, binpow(n, mod - 2));
dp[n] = res;
// cerr << n << " " << binpow(n,mod - 2) << " ???\n";
return;
}
solve(5 * n / 6);
solve(5 * n / 6 + 1);
VI a = dp[5 * n / 6],b = dp[5 * n / 6 + 1];
VI res(n);
FOR(j, 0, 6)
{
int cnt = 0;
FOR(i, 0, n)
{
if(i % 6 == j)
continue;
if(j < n % 6)
res[i] = add(res[i], a[cnt]);
// ,cerr << i << " " << cnt << " " << a[cnt] << " first\n";
else
res[i] = add(res[i], b[cnt]);
// ,cerr << i << " " << cnt << " " << b[cnt] << " second\n";
cnt++;
}
}
// cerr << n << " begin:\n";
// FOR(i, 0, n) cerr << res[i] << " "; cerr << "\n";
FOR(i, 0, n)
res[i] = mult(res[i], ml6);
// cerr << "\n";
dp[n] = res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int n;
cin >> n;
solve(n);
VI res = dp[n];
FOR(i, 0, n)
{
cout << res[i] << "\n";
}
//cerr << sum << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
3
output:
332748118 332748118 332748118
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
7
output:
305019108 876236710 876236710 876236710 876236710 876236710 305019108
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
8
output:
64701023 112764640 160828257 160828257 160828257 160828257 112764640 64701023
result:
ok 8 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
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: 3584kb
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: 3612kb
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'