結果

問題 No.315 世界のなんとか3.5
コンテスト
ユーザー yuppe19 😺
提出日時 2015-12-08 23:08:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 5,326 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 863 ms
コンパイル使用メモリ 61,532 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-09-14 20:25:28
合計ジャッジ時間 4,169 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 TLE * 1 -- * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:130:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  130 |   char a[200010], b[200010]; scanf("%s%s%d", a, b, &p);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <cstring>
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>;

int p;
//vector<vector<vector<vector<vector<vector<i64>>>>>> dp;
i64 dp[2][2][2][3][25][32];

//int calc(int p) {
//  int res = 0;
//  while(p) { res++; p /= 10; }
//  return --res;
//}

i64 f(string s) {
  int n = s.size();
//  dp.assign(2, vector<vector<vector<vector<vector<i64>>>>>(2, vector<vector<vector<vector<i64>>>>(2, vector<vector<vector<i64>>>(3, vector<vector<i64>>(3, vector<i64>(8, 0))))));
  for(int i : range(2)) for(int j : range(2)) for(int k : range(2)) for(int l : range(3)) for(int m : range(25)) for(int o : range(32)) dp[i][j][k][l][m][o] = 0;
  dp[0][0][0][0][0][0] = 1;
  for(int i : range(n)) {
    int cur = i & 1,
        nxt = !cur;
    for(int j : range(2)) for(int k : range(2)) for(int l : range(3)) for(int m : range(25)) for(int o : range(32)) dp[nxt][j][k][l][m][o] = 0;
    for(int j : range(2)) {
      for(int k03 : range(3)) {
        for(int k025 : range(25)) { // FIXME (？ω？)＜この辺の計算量をどうやって落とすか
          for(int k032 : range(32)) { // (？ω？)＜この辺
            // MEMO (ΦωΦ)＜「10倍してdを足したときに2の何乗になるか」が、「前に2の何乗だったか」という情報から分かるか
            if(!dp[cur][j][0][k03][k025][k032] && !dp[cur][j][1][k03][k025][k032]) { continue; }
            for(int d : range(j?10:s[i]-'0'+1)) {
              int flag = j || d < s[i] - '0',
                  k13 = (k03 + d) % 3,
                  k125 = (k025 * 10 + d) % 25,
                  k132 = (k032 * 10 + d) % 32;
              dp[nxt][flag][d==3][k13][k125][k132] += dp[cur][j][0][k03][k025][k032];
              dp[nxt][flag][d==3][k13][k125][k132] %= mod;
              dp[nxt][flag][1]   [k13][k125][k132] += dp[cur][j][1][k03][k025][k032];
              dp[nxt][flag][1]   [k13][k125][k132] %= mod;
            }
          }
        }
      }
    }
  }

//  int q = calc(p);

  i64 res = 0;
  for(int j : range(2)) {
    for(int k25 : range(25)) {
      for(int k32 : range(32)) {
        if(p == 8 && !(k32%8)) { continue; }
        else if(p==80 && !(k32%16) && !(k25%5)) { continue; }
        else if(p==800 &&!k32 && !k25) { continue; }
        for(int k3 : range(3)) {
          res += dp[n&1][j][1][k3][k25][k32];
          res %= mod;
        }
        res += dp[n&1][j][0][0][k25][k32];
        res %= mod;
      }
    }
  }
  return res;
//  return --res;
}

void minus1(char *s) {
  int n = strlen(s);
  for(int i=n-1; i>=0; i--) {
    if(s[i] == '0') { s[i] = '9'; }
    else { s[i] -= 1; break; }
  }
}

int main(void) {
  char a[200010], b[200010]; scanf("%s%s%d", a, b, &p);
//  string a, b; cin >> a >> b >> p;
  minus1(a);
  i64 r0 = f(b);
  i64 r1 = f(a);
  i64 res = r0 - r1;
  printf("%d\n", int((res+mod) % mod));
  return 0;
}
0