QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#500511 | #7927. Fortune Telling | New_Folder | RE | 0ms | 0kb | C++23 | 3.4kb | 2024-08-01 13:23:53 | 2024-08-01 13:23:53 |
answer
#pragma GCC optimize(2)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll mod = 998244353;
ll inv[7];
//vector<unordered_map<int, ll>> dp;
vector<vector<ll>> dp;
ll fastpow(ll base,ll po){
ll ans = 1;
while(po){
if(po&1){
ans *= base;
ans %= mod;
}
base *= base;
base %= mod;
po >>=1;
}
return ans;
}
void calc(int n){
dp[n].resize(n + 1);
if(dp[5*n/6].empty()){
calc(5 * n / 6);
}
if(dp[5*n/6+1].empty()){
calc(5 * n / 6 + 1);
}
for (int k = 1; k <= n;k++){
ll res = 0;
if (n % 6 == 0)
{
int bef = (k - 1) % 6;
int af = 5 - bef;
if (bef)
{
res += bef * dp[5 * n / 6][ k - k / 6 - (k % 6 == 0 ? 0 : 1)];
}
if (af)
{
res += af * dp[5 * n / 6][ k - k / 6];
}
res = res % mod * inv[6] % mod;
dp[n][k] = res;
}
else
{
int rem = n % 6;
if (k % 6 == 0)
{
if (rem)
{
res += rem * dp[5 * n / 6][ k - k / 6];
}
if (5 - rem)
{
res += (5 - rem) * dp[5 * n / 6 + 1][ k - k / 6];
}
res = res % mod * inv[6] % mod;
dp[n][k] = res;
}
else
{
int rem2 = k % 6;
if (rem >= rem2)
{
if (rem2 - 1)
{
res += (rem2 - 1) * dp[5 * n / 6][ k - k / 6 - 1];
}
if (rem - rem2)
{
res += (rem - rem2) * dp[5 * n / 6][ k - k / 6];
}
if (6 - rem)
{
res += (6 - rem) * dp[5 * n / 6 + 1][ k - k / 6];
}
res = res % mod * inv[6] % mod;
dp[n][k] = res;
}
else
{
if (rem)
{
res += (rem)*dp[5 * n / 6][ k - k / 6 - 1];
}
if (rem2 - rem - 1)
{
res += (rem2 - rem - 1) * dp[5 * n / 6 + 1][ k - k / 6 - 1];
}
if (6 - rem2)
{
res += (6 - rem2) * dp[5 * n / 6 + 1][k - k / 6];
}
res = res % mod * inv[6] % mod;
dp[n][k] = res;
}
}
}
}
}
void solve()
{
int n;
cin >> n;
dp.resize(n + 1);
for (int i = 1; i <= 6;i++){
inv[i] = fastpow(i * 1LL, mod - 2);
}
for (int i = 1; i <= 6; i++)
{
dp[i].resize(i + 1);
for (int j = 1; j <= i; j++)
{
dp[i][j] = inv[i];
}
}
calc(n);
for (int i = 1; i <= n;i++){
cout << dp[n][i] << '\n';
}
//cout << "finish" << endl;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3