Submission #41043551

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using mint = modint998244353;

int main() {
    ll N;
    cin >> N;
    map<ll, mint> memo;
    memo[1] = 1;
    mint i6 = mint(6).inv(), i5 = mint(5).inv();
    auto dp = [&](auto self, ll n) {
        if (memo[n] != mint(0)) return memo[n];
        mint res = 0;
        for (ll i = 2; i <= 6; i++) {
            if (n % i != 0) continue;
            res += self(self, n / i) * i6;
        }
        res *= 6 * i5;
        return memo[n] = res;
    };
    cout << dp(dp, N).val() << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Dice Product 3
User mtrh
Language C++ (GCC 9.2.1)
Score 500
Code Size 649 Byte
Status AC
Exec Time 15 ms
Memory 3760 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 4
AC × 25
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_small_00.txt, 01_small_01.txt, 01_small_02.txt, 01_small_03.txt, 01_small_04.txt, 01_small_05.txt, 01_small_06.txt, 01_small_07.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 03_limited_00.txt, 03_limited_01.txt, 03_limited_02.txt, 03_limited_03.txt, 03_limited_04.txt, 03_limited_05.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 15 ms 3564 KiB
00_sample_01.txt AC 2 ms 3652 KiB
00_sample_02.txt AC 2 ms 3596 KiB
00_sample_03.txt AC 5 ms 3608 KiB
01_small_00.txt AC 3 ms 3568 KiB
01_small_01.txt AC 3 ms 3500 KiB
01_small_02.txt AC 2 ms 3496 KiB
01_small_03.txt AC 2 ms 3592 KiB
01_small_04.txt AC 2 ms 3500 KiB
01_small_05.txt AC 2 ms 3588 KiB
01_small_06.txt AC 3 ms 3592 KiB
01_small_07.txt AC 2 ms 3436 KiB
02_random_00.txt AC 2 ms 3624 KiB
02_random_01.txt AC 2 ms 3624 KiB
02_random_02.txt AC 5 ms 3644 KiB
02_random_03.txt AC 5 ms 3736 KiB
02_random_04.txt AC 8 ms 3760 KiB
02_random_05.txt AC 5 ms 3716 KiB
02_random_06.txt AC 6 ms 3680 KiB
03_limited_00.txt AC 2 ms 3492 KiB
03_limited_01.txt AC 2 ms 3600 KiB
03_limited_02.txt AC 2 ms 3468 KiB
03_limited_03.txt AC 2 ms 3492 KiB
03_limited_04.txt AC 2 ms 3608 KiB
03_limited_05.txt AC 2 ms 3608 KiB