結果
問題 | No.533 Mysterious Stairs |
ユーザー |
|
提出日時 | 2022-08-13 16:01:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 5,000 ms |
コード長 | 2,182 bytes |
コンパイル時間 | 1,980 ms |
コンパイル使用メモリ | 197,928 KB |
最終ジャッジ日時 | 2025-01-30 22:15:29 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i = 0; i < (n); i++)using namespace std;typedef long long ll;template< int mod >struct Fp {int x;Fp() : x(0) {}Fp(int64_t y) : x(y >= 0 ? y % mod : (mod + y % mod) % mod) {}Fp &operator+=(const Fp &p) { if((x += p.x) >= mod) x -= mod; return *this; }Fp &operator-=(const Fp &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; }Fp &operator*=(const Fp &p) { x = (int)(1LL * x * p.x % mod); return *this; }Fp &operator/=(const Fp &p) { *this *= p.inv(); return *this; }Fp operator-() const { return Fp(-x); }Fp operator+(const Fp &p) const { return Fp(*this) += p; }Fp operator-(const Fp &p) const { return Fp(*this) -= p; }Fp operator*(const Fp &p) const { return Fp(*this) *= p; }Fp operator/(const Fp &p) const { return Fp(*this) /= p; }bool operator==(const Fp &p) const { return x == p.x; }bool operator!=(const Fp &p) const { return x != p.x; }Fp inv() const {int a = x, b = mod, u = 1, v = 0, t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return Fp(u);}Fp pow(int64_t n) const {Fp ret(1), mul(x);while(n > 0) {if(n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}friend ostream &operator<<(ostream &os, const Fp &p) { return os << p.x; }friend istream &operator>>(istream &is, Fp &a) {int64_t t;is >> t;a = Fp< mod > (t);return (is);}static int get_mod() { return mod; }};using mint = Fp<1000000007>;int main(){cin.tie(0);ios::sync_with_stdio(0);int N; cin >> N;vector<vector<mint>> dp(N + 5, vector<mint>(4, 0));dp[1][1] = 1;dp[2][2] = 1;dp[3][1] = dp[3][2] = dp[3][3] = 1;for(int i = 4; i <= N; i++) {for(int a : {1, 2, 3}) {for(int b : {1, 2, 3}) {if(a != b && i - a >= 0)dp[i][a] += dp[i - a][b];}}}cout << dp[N][1] + dp[N][2] + dp[N][3] << endl;}