#1030674 (C++17) No.314 ケンケンパ

• 問題: No.314 ケンケンパ
• ユーザー: elphe
• 提出日時: 2024-12-10 17:00:07
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 8 ms / 1,000 ms
• コード長: 7,944 bytes
• コンパイル時間: 738 ms
• コンパイル使用メモリ: 68,888 KB
• 最終ジャッジ日時: 2025-02-26 11:49:08
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 17

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <cstdint>
#include <array>
using namespace std;
template<unsigned int MOD> class mod_int
{
private:
    unsigned int value = 0;
    constexpr static bool is_prime(const unsigned int arg) noexcept
    {
        for (unsigned int i = 2; i * i <= arg; ++i)
            if (arg % i == 0) return false;
        return true;
    }
    constexpr static unsigned int pow_mod(unsigned int a, size_t b) noexcept
    {
        if (MOD == 1) return 0;
        unsigned int ans = 1;
        a %= MOD;
        for (; b != 0; b >>= 1, a = static_cast<unsigned long long>(a) * a % MOD)
            if (b & 1) ans = ans * static_cast<unsigned long long>(a) % MOD;
        return ans;
    }
public:
    constexpr mod_int() noexcept { static_assert(MOD != 0, "0 cannot be set as \'MOD.\'"); }
    template<typename T> constexpr mod_int(const T arg) noexcept { static_assert(MOD != 0, "0 cannot be set as \'MOD.\'"); value = (unsigned int)(arg 
        % MOD); }
    constexpr mod_int<MOD> operator+(const mod_int<MOD> other) const noexcept { return mod_int(this->value >= MOD - other.value ? this->value - (MOD 
        - other.value) : this->value + other.value); }
    constexpr mod_int<MOD> operator-(const mod_int<MOD> other) const noexcept { return mod_int(this->value >= other.value ? this->value - other.value 
        : MOD - (other.value - this->value)); }
    constexpr mod_int<MOD> operator*(const mod_int<MOD> other) const noexcept { if constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned 
        long long>(this->value) * other.value % MOD); else return mod_int(this->value * other.value % MOD); }
    constexpr mod_int<MOD> operator/(const mod_int<MOD> other) const noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if 
        constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned long long>(this->value) * pow_mod(other.value, MOD - 2) % MOD); else return 
        mod_int(this->value * pow_mod(other.value, MOD - 2) % MOD); }
    template<typename T> constexpr mod_int<MOD> operator+(T arg) const noexcept { arg %= MOD; return mod_int(value >= MOD - static_cast<unsigned int
        >(arg) ? value - (MOD - static_cast<unsigned int>(arg)) : value + static_cast<unsigned int>(arg)); }
    template<typename T> constexpr mod_int<MOD> operator-(T arg) const noexcept { arg %= MOD; return mod_int(value >= static_cast<unsigned int>(arg) 
        ? value - static_cast<unsigned int>(arg) : MOD - (static_cast<unsigned int>(arg) - value)); }
    template<typename T> constexpr mod_int<MOD> operator*(T arg) const noexcept { if constexpr (MOD >= (1u << 16)) return mod_int(static_cast
        <unsigned long long>(value) * (arg % MOD) % MOD); else return mod_int(value * static_cast<unsigned int>(arg % MOD) % MOD); }
    template<typename T> constexpr mod_int<MOD> operator/(T arg) const noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if 
        constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned long long>(value) * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) 
        % MOD); else return mod_int(value * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD); }
    constexpr mod_int<MOD>& operator+=(const mod_int<MOD> other) noexcept { if (this->value >= MOD - other.value) this->value -= (MOD - other.value); 
        else this->value += other.value; return *this; }
    constexpr mod_int<MOD>& operator-=(const mod_int<MOD> other) noexcept { if (this->value >= other.value) this->value -= other.value; else this
        ->value += (MOD - other.value); return *this; }
    constexpr mod_int<MOD>& operator*=(const mod_int<MOD> other) noexcept { if constexpr (MOD >= (1u << 16)) this->value = static_cast<unsigned long 
        long>(this->value) * other.value % MOD; else this->value = this->value * other.value % MOD; return *this; }
    constexpr mod_int<MOD>& operator/=(const mod_int<MOD> other) noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if 
        constexpr (MOD >= (1u << 16)) this->value = static_cast<unsigned long long>(this->value) * pow_mod(other.value, MOD - 2) % MOD; else this
        ->value = this->value * pow_mod(other.value, MOD - 2) % MOD; return *this; }
    template<typename T> constexpr mod_int<MOD>& operator+=(T arg) noexcept { arg %= MOD; if (value >= MOD - arg) value -= (MOD - arg); else value += 
        arg; return *this; }
    template<typename T> constexpr mod_int<MOD>& operator-=(T arg) noexcept { arg %= MOD; if (value >= arg) value -= arg; else value += (MOD - arg); 
        return *this; }
    template<typename T> constexpr mod_int<MOD>& operator*=(T arg) noexcept { if constexpr (MOD >= (1u << 16)) value = static_cast<unsigned long long
        >(value) * (arg % MOD) % MOD; else value = value * (arg % MOD) % MOD; return *this; }
    template<typename T> constexpr mod_int<MOD>& operator/=(T arg) noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if 
        constexpr (MOD >= (1u << 16)) value = static_cast<unsigned long long>(value) * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD; 
        else value = value * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD; return *this; }
    constexpr mod_int<MOD>& operator++() noexcept { if (value + 1 == MOD) value = 0; else ++value; return *this; }
    constexpr mod_int<MOD> operator++(int) noexcept { const auto temp = value; if (value + 1 == MOD) value = 0; else ++value; return mod_int<MOD
        >(temp); }
    constexpr mod_int<MOD>& operator--() noexcept { if (value == 0) value = MOD - 1; else --value; return *this; }
    constexpr mod_int<MOD> operator--(int) noexcept { const auto temp = value; if (value == 0) value = MOD - 1; else --value; return *this; }
    constexpr bool operator==(const mod_int<MOD> other) const noexcept { return this->value == other.value; }
    constexpr bool operator!=(const mod_int<MOD> other) const noexcept { return this->value != other.value; }
    constexpr bool operator<(const mod_int<MOD> other) const noexcept { return this->value < other.value; }
    constexpr bool operator<=(const mod_int<MOD> other) const noexcept { return this->value <= other.value; }
    constexpr bool operator>(const mod_int<MOD> other) const noexcept { return this->value > other.value; }
    constexpr bool operator>=(const mod_int<MOD> other) const noexcept { return this->value >= other.value; }
    template<typename T> constexpr bool operator==(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); 
        return value == arg; }
    template<typename T> constexpr bool operator!=(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); 
        return value != arg; }
    template<typename T> constexpr bool operator<(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); 
        return value < arg; }
    template<typename T> constexpr bool operator<=(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); 
        return value <= arg; }
    template<typename T> constexpr bool operator>(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); 
        return value > arg; }
    template<typename T> constexpr bool operator>=(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); 
        return value >= arg; }
    operator unsigned int() const noexcept { return this->value; }
    constexpr mod_int<MOD> pow_mod(unsigned long long times)
    {
        if (MOD == 1) return 0;
        mod_int<MOD> ans = 1;
        unsigned int a = this->value;
        for (; times != 0; times >>= 1, a = static_cast<unsigned long long>(a) * a % MOD)
            if (times & 1) ans.value = static_cast<unsigned long long>(ans.value) * a % MOD;
        return ans;
    }
};
int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    uint32_t N, i;
    cin >> N;
    if (N == 1)
    {
        cout << "1\n";
        return 0;
    }
    array<mod_int<1'000'000'007>, 3> dp_cur, dp_prev;
    dp_cur[0] = dp_cur[1] = 1, dp_cur[2] = 0;
    for (i = 2; i != N; ++i)
    {
        dp_cur.swap(dp_prev);
        dp_cur[0] = dp_prev[2];
        dp_cur[1] = dp_prev[0] + dp_prev[2];
        dp_cur[2] = dp_prev[1];
    }
    cout << dp_cur[0] + dp_cur[1] + dp_cur[2] << '\n';
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX