#71079 (C++11（廃止可能性あり）) No.260 世界のなんとか3

• 問題: No.260 世界のなんとか3
• ユーザー: yuppe19 😺
• 提出日時: 2016-01-14 13:51:33
• 言語: C++11（廃止可能性あり） (gcc 13.3.0 + boost 1.89.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 3,743 bytes
• コンパイル時間: 333 ms
• コンパイル使用メモリ: 53,332 KB
• 最終ジャッジ日時: 2024-11-14 19:31:59
• 合計ジャッジ時間: 693 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

コンパイルメッセージ

main.cpp: In function ‘modint f(std::string)’:
main.cpp:61:3: error: ‘vector’ was not declared in this scope
   61 |   vector<vector<vector<vector<vector<modint>>>>> dp(n+1, vector<vector<vector<vector<modint>>>>(2, vector<vector<vector<modint>>>(2, vector<vector<modint>>(3, vector<modint>(8)))));
      |   ^~~~~~
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:61:44: error: expected primary-expression before ‘>>’ token
   61 |   vector<vector<vector<vector<vector<modint>>>>> dp(n+1, vector<vector<vector<vector<modint>>>>(2, vector<vector<vector<modint>>>(2, vector<vector<modint>>(3, vector<modint>(8)))));
      |                                            ^~
main.cpp:61:46: error: expected primary-expression before ‘>>’ token
   61 |   vector<vector<vector<vector<vector<modint>>>>> dp(n+1, vector<vector<vector<vector<modint>>>>(2, vector<vector<vector<modint>>>(2, vector<vector<modint>>(3, vector<modint>(8)))));
      |                                              ^~
main.cpp:61:48: error: expected primary-expression before ‘>’ token
   61 |   vector<vector<vector<vector<vector<modint>>>>> dp(n+1, vector<vector<vector<vector<modint>>>>(2, vector<vector<vector<modint>>>(2, vector<vector<modint>>(3, vector<modint>(8)))));
      |                                                ^
main.cpp:61:92: error: expected primary-expression before ‘>>’ token
   61 |   vector<vector<vector<vector<vector<modint>>>>> dp(n+1, vector<vector<vector<vector<modint>>>>(2, vector<vector<vector<modint>>>(2, vector<vector<modint>>(3, vector<modint>(8)))));
      |                                                                                            ^~
main.cpp:61:94: error: expected primary-expression before ‘>>’ token
   61 |   vector<vector<vector<vector<vector<modint>>>>> dp(n+1, vector<vector<ve

ソースコード

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

template<typename T>
class Range{private:struct I{T x;T operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:Range(T n):i({0}),n({n}){}Range(T i,T n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};
using range = Range<i64>;

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

modint f(string s) {
  int n = s.size();
  vector<vector<vector<vector<vector<modint>>>>> dp(n+1, vector<vector<vector<vector<modint>>>>(2, vector<vector<vector<modint>>>(2, vector<vector<modint>>(3, vector<modint>(8)))));
  dp[0][0][0][0][0] = 1;
  for(auto&& i : range(n)) {
    for(auto&& j : range(2)) {
      for(auto&& has3 : range(2)) {
        for(auto&& k0 : range(24)) {
          for(auto&& d : range(j?10:s[i]-'0'+1)) {
            int flag = j || d < s[i] - '0',
                nhas3 = has3 || (d==3),
                k1 = k0 * 10 + d;
            dp[i+1][flag][nhas3][k1%3][k1%8] += dp[i][j][has3][k0%3][k0%8];
          }
        }
      }
    }
  }
  modint res = 0;
  for(auto&& j : range(2)) {
    for(auto&& k8 : range(1, 8)) {
      for(auto&& k3 : range(3)) {
        res += dp[n][j][1][k3][k8];
      }
      res += dp[n][j][0][0][k8];
    }
  }
  return --res;
}

void minus1(string &s) {
  int n = s.size();
  for(int i=n-1; i>=0; i--) {
    if(s[i] == '0') { s[i] = '9'; }
    else { s[i] -= 1; break; }
  }
}

int main(void) {
  string a, b; cin >> a >> b;
  minus1(a);
  modint res = f(b) - f(a);
  printf("%d\n", res.intvalue());
  return 0;
}