結果

問題 No.314 ケンケンパ
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-12-07 00:45:14
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,109 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 52,968 KB
最終ジャッジ日時 2023-10-12 18:43:13
合計ジャッジ時間 900 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:57:1: error: ‘vector’ does not name a type; did you mean ‘perror’?
 vector<vector<vector<modint>>> dp;
 ^~~~~~
 perror
main.cpp: In function ‘int main()’:
main.cpp:83:3: error: ‘dp’ was not declared in this scope
   dp.assign(2, vector<vector<modint>>(3, vector<modint>(3)));
   ^~
main.cpp:83:16: error: ‘vector’ was not declared in this scope
   dp.assign(2, vector<vector<modint>>(3, vector<modint>(3)));
                ^~~~~~
main.cpp:83:16: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
main.cpp:3:1:
+#include <vector>
 using namespace std;
main.cpp:83:16:
   dp.assign(2, vector<vector<modint>>(3, vector<modint>(3)));
                ^~~~~~
main.cpp:83:36: error: expected primary-expression before ‘>>’ token
   dp.assign(2, vector<vector<modint>>(3, vector<modint>(3)));
                                    ^~
main.cpp:83:55: error: expected primary-expression before ‘>’ token
   dp.assign(2, vector<vector<modint>>(3, vector<modint>(3)));
                                                       ^

ソースコード

diff # 

#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>;

vector<vector<vector<modint>>> dp;
int n;

//modint rec(int i, int x2, int x1) {
//  modint &res = dp[i&1][x2][x1];
//  if(i == n) { return res = modint(1); }
//  if(res != *modint::none) { return res; }
//  res = 0;
//  if(x2 == 1 && x1 == 1) {
//    res = rec(i+1, x1, 2);
//  } else if(x2 == 2 && x1 == 1) {
//    res = rec(i+1, x1, 1) + rec(i+1, x1, 2);
//  } else if(x2 == 1 && x1 == 2) {
//    res = rec(i+1, x1, 1);
//  } else if(x2 == 0 && x1 == 0) {
//    res = rec(i+1, x1, 1);
//  } else if(x2 == 0 && x1 == 1) {
//    res = rec(i+1, x1, 1) + rec(i+1, x1, 2);
//  } else {
//    fprintf(stderr, "x2=%d, x1=%d\n", x2, x1);
//  }
//  return res;
//}

int main(void) {
  scanf("%d", &n);
  dp.assign(2, vector<vector<modint>>(3, vector<modint>(3)));
//  modint res = rec(0, 0, 0);
  dp[0][0][0] = 1;
  for(int i : range(n)) {
    int bi  = i & 1,
        bni = !bi;
    // (x2, x1) = (0, 0) -> [1]
    dp[bni][0][1] += dp[bi][0][0];
    // (x2, x1) = (0, 1) -> [1, 2]
    dp[bni][1][1] += dp[bi][0][1];
    dp[bni][1][2] += dp[bi][0][1];
    // (x2, x1) = (0, 2) -> X
    // nop
    // (x2, x1) = (1, 1) -> [2]
    dp[bni][1][2] += dp[bi][1][1];
    // (x2, x1) = (1, 2) -> [1]
    dp[bni][2][1] += dp[bi][1][2];
    // (x2, x1) = (2, 1) -> [1, 2]
    dp[bni][1][1] += dp[bi][2][1];
    dp[bni][1][2] += dp[bi][2][1];
    for(int x2 : range(3)) {
      for(int x1 : range(3)) {
        dp[bi][x1][x2] = 0;
      }
    }
  }
  modint res = dp[n&1][0][0] + dp[n&1][0][1] + dp[n&1][1][1] + dp[n&1][1][2] + dp[n&1][2][1];
  printf("%d\n", res.intvalue());
  return 0;
}
0