結果

問題 No.314 ケンケンパ
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-12-07 04:16:36
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,052 bytes
コンパイル時間 449 ms
コンパイル使用メモリ 51,704 KB
最終ジャッジ日時 2024-11-14 19:30:13
合計ジャッジ時間 886 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:58:1: error: ‘vector’ does not name a type
   58 | vector<vector<modint>> dp;
      | ^~~~~~
main.cpp: In function ‘int main()’:
main.cpp:62:3: error: ‘dp’ was not declared in this scope
   62 |   dp.assign(2, vector<modint>(4));
      |   ^~
main.cpp:62:16: error: ‘vector’ was not declared in this scope
   62 |   dp.assign(2, vector<modint>(4));
      |                ^~~~~~
main.cpp:3:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    2 | #include <algorithm>
  +++ |+#include <vector>
    3 | using namespace std;
main.cpp:62:29: error: expected primary-expression before ‘>’ token
   62 |   dp.assign(2, vector<modint>(4));
      |                             ^
main.cpp:72:16: error: ‘accumulate’ was not declared in this scope
   72 |   modint res = accumulate(dp[n&1].begin(), dp[n&1].end(), modint(0));
      |                ^~~~~~~~~~
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 # 

#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