QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#500511#7927. Fortune TellingNew_FolderRE 0ms0kbC++233.4kb2024-08-01 13:23:532024-08-01 13:23:53

Judging History

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

  • [2024-08-01 13:23:53]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: