結果
| 問題 | No.314 ケンケンパ |
| ユーザー |
 yasunori
|
| 提出日時 | 2024-01-09 12:00:19 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 139 ms / 1,000 ms |
| コード長 | 6,005 bytes |
| コンパイル時間 | 2,166 ms |
| コンパイル使用メモリ | 203,464 KB |
| 最終ジャッジ日時 | 2025-02-18 16:41:13 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T> using min_priority_queue = priority_queue<T,vector<T>,greater<T>>;template<typename T>void printv(vector<T> &v){bool b = false;for(auto i : v){if(b) cout << " ";else b = true;cout << i;}cout << endl;}int64_t rand64(){int64_t l = rand();int64_t r = rand();return (l<<31)+r;}template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b; // aをbで更新return true;}return false;}template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b; // aをbで更新return true;}return false;}template <typename T>T exEuclid(T a, T b, T &x, T &y){T d = a;if(b != 0){d = exEuclid(b, a%b, y, x);y -= (a/b)*x;}else{x = 1;y = 0;}//cout << a << " * " << x << " + " << b << " * " << y << " = " << d << endl;return d;}int64_t mod;struct modint{int64_t n;int64_t p;modint(){n = 0;p = mod;}modint(int64_t a){if(a <= -mod) a %= mod;else if(a >= mod) a %= mod;if(a < 0) a += mod;n = a;p = mod;}modint(int64_t a, int64_t q){if(a <= -q) a %= q;else if(a >= q) a %= q;if(a < 0) a += q;n = a;p = q;}modint pow(int64_t a){if(a <= 1-p) a %= p-1;else if(a >= p-1) a %= p-1;if(a < 0) a += p-1;modint rtn;if(n == 0) {rtn.n = 0;return rtn;}if(n == 1) {rtn.n = 1;return rtn;}if(a == 0) {rtn.n = 1;return rtn;}if(a == 1) {rtn.n = n;return rtn;}int64_t b = a/2;int64_t c = a%2;rtn = pow(b);rtn *= rtn;if(c){rtn *= modint(n);}return rtn;}bool operator==(modint other){return n == other.n && p == other.p;}bool operator!=(modint other){return !(n == other.n && p == other.p);}modint operator+(modint other){modint rtn(n+other.n, p);return rtn;}modint operator-(modint other){modint rtn(n-other.n, p);return rtn;}modint operator*(modint other){modint rtn(n*other.n, p);return rtn;}modint operator/(modint other){int64_t x, y, d;d = exEuclid(other.n, p, x, y);int64_t rtn = x*n;if(d > 1) rtn /= d;return modint(rtn);}void operator+=(modint other){n += other.n;if(n >= p) n %= p;}void operator-=(modint other){n -= other.n;if(n < 0) n += p;}void operator*=(modint other){n *= other.n;if(n >= p) n %= p;}void operator/=(modint other){int64_t x, y, d;d = exEuclid(other.n, p, x, y);n *= x;if(d > 1) n /= d;if(n <= p || p <= n) n %= p;if(n < 0) n += p;return;}void operator++(){n++;if(n == p) n = 0;return;}void operator--(){n--;if(n == -1) n = p-1;return;}};vector<modint> fact_mod_v;vector<modint> inv_fact_mod_v;modint comb_mod(int64_t n, int64_t m){if(n < 0 || m < 0 || m > n) return 0;modint rtn = fact_mod_v[n]*inv_fact_mod_v[m]*inv_fact_mod_v[n-m];return rtn;}modint comb_mod_small(int64_t n, int64_t m){if(m < mod){return comb_mod(n%mod, m);}return comb_mod_small(n/mod, m/mod)*comb_mod(n%mod, m%mod);}void init_fact(int64_t n){fact_mod_v.resize(n+1,0);inv_fact_mod_v.resize(n+1,0);for(int64_t i = 0; i <= n; i++){if(i == 0){fact_mod_v[i] = modint(1);}else{fact_mod_v[i] = modint(i*fact_mod_v[i-1].n);}//cout << i << endl;}for(int64_t i = min(n, mod-1); i >= 0; i--){if(i == min(n, mod-1)){inv_fact_mod_v[i] = modint(fact_mod_v[i]).pow(-1);}else{inv_fact_mod_v[i] = modint(inv_fact_mod_v[i+1].n*(i+1));}//cout << i << endl;}}bool yn(bool b){if(b) cout << "Yes" << endl;else cout << "No" << endl;return b;}bool debug;bool randomInput;bool debugOutput;int numOfTestCase;using ans_type = int;void input(){if(numOfTestCase > 1){}if(randomInput){}else{}return;}void output_input(){;}ans_type calc(){int N; cin >> N;mod = 1000000007;vector<vector<modint>> dp(N, vector<modint>(4, 0));dp[0][0b01] = 1;for(int i = 1; i < N; i++){for(int j = 0; j < 4; j++){if(j != 3) dp[i][((j<<1)+1)&3] += dp[i-1][j];if(j&1 != 0) dp[i][j<<1&3] += dp[i-1][j];}}modint ans(0);for(int j = 0; j < 4; j++) ans += dp[N-1][j];cout << ans.n << endl;return ans_type();}ans_type calc_simple(){return ans_type();}void output(ans_type ans){return;}int main(){debug = 0;randomInput = 0;debugOutput = 0;numOfTestCase = 1;srand(time(NULL));cout << fixed << setprecision(12);if(numOfTestCase == 0) cin >> numOfTestCase;if(debug){for(int i = 0; i < numOfTestCase; i++){if(debugOutput) cout << string(16, '-') << endl;input();ans_type ans = calc();ans_type ansSimple = calc_simple();if(ans != ansSimple){output_input();output(ans);output(ansSimple);}}}else{for(int i = 0; i < numOfTestCase; i++){input();output(calc());}}return 0;}