結果

問題 No.314 ケンケンパ
コンテスト
ユーザー yuppe19 😺
提出日時 2015-12-07 04:16:36
言語 C++11(old_compat)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -include bits/stdc++.h -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 8 ms / 1,000 ms
コード長 3,052 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,511 ms
コンパイル使用メモリ 175,232 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-03-08 16:04:49
合計ジャッジ時間 2,103 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:61:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   61 |   int n; scanf("%d", &n);
      |          ~~~~~^~~~~~~~~~

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

template <int mod>
struct Modint {
  static const Modint* none; // *modint::none
  long long x;
  Modint(void)  { x = 0; };
  Modint(long long a)  { x = (a%mod+mod)%mod; };
  Modint(string s) {
    x = 0;
    for(char c : s) {
      (x *= 10) += (c - '0');
      x %= mod;
    }
//    if(!x) { x = mod; }
  };
  static Modint* noneInstance(void) { Modint* res = new Modint(); res->x = -1; return res; }
  bool is_none(void) { return x == -1; }
  Modint operator + (const Modint a)    { return Modint(*this) += a; }
  Modint operator - (const Modint a)    { return Modint(*this) -= a; }
  Modint operator * (const Modint a)    { return Modint(*this) *= a; }
  Modint operator * (const long long a) { return Modint(*this) *= (a%mod+mod)%mod; }
  friend Modint operator * (const long long a, const Modint& b) { return Modint(b) *= (a%mod+mod)%mod; }
  Modint operator +=(const Modint& a)   { if((x+=a.x)>=mod) { x-=mod; } return *this; }
  Modint operator -=(const Modint& a)   { if((x-=a.x)<0) { x+=mod; } return *this; }
  Modint operator *=(const Modint& a)   { (x*=a.x)%=mod; return *this; }
  Modint operator *=(const long long a) { (x*=(a%mod+mod)%mod)%=mod; return *this; }
  /* a++ */ Modint operator ++(int)     { Modint old; old.x = x; if((x+=1)>=mod) { x-=mod; }; return old; }
  /* ++a */ Modint operator ++(void)    { *this += 1; return *this; }
  /* a-- */ Modint operator --(int)     { Modint old; old.x = x; if((x-=1)<0) { x+=mod; }; return old; }
  /* --a */ Modint operator --(void)    { *this -= 1; return *this; }
  bool operator ==(const Modint& a) const   { return x == a.x; }
  bool operator ==(const long long a) const { return x == (a%mod+mod)%mod; }
  bool operator !=(const Modint& a) const   { return !(x == a.x); }
  bool operator !=(const long long a) const { return x != (a%mod+mod)%mod; }
  int intvalue(void) const { return (int)x; }
  Modint pow(const long long n){
    Modint res = 1;
    long long p = x;
    for(long long i=n; i>0; i>>=1) {
      if(i & 1) { res *= p; }
      (p *= p) %= mod;
    }
    return res;
  }
};
template <int mod> const Modint<mod>* Modint<mod>::none = Modint<mod>::noneInstance();
const int mod = 1000000007;
using modint = Modint<mod>;

const int non = 0, ke1 = 1, ke2 = 2, paa = 3;
vector<vector<modint>> dp;

int main(void) {
  int n; scanf("%d", &n);
  dp.assign(2, vector<modint>(4));
  dp[non][0] = 1;
  for(int i : range(n)) {
    int cur = i & 1,
        nxt = !cur;
    dp[nxt][ke1] += dp[cur][non] + dp[cur][paa];
    dp[nxt][ke2] += dp[cur][ke1];
    dp[nxt][paa] += dp[cur][ke1] + dp[cur][ke2];
    dp[cur].assign(4, 0);
  }
  modint res = accumulate(dp[n&1].begin(), dp[n&1].end(), modint(0));
  printf("%d\n", res.intvalue());
  return 0;
}
0