結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー ei1333333
提出日時 2017-03-11 00:50:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,971 bytes
コンパイル時間 1,708 ms
コンパイル使用メモリ 180,868 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-24 09:20:48
合計ジャッジ時間 4,833 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 59 WA * 53 RE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
const int mod = 1e9 + 7;


int64 szCalc[62], sum1[62], sum2[62];
map< tuple< int64, int64, int64 >, pair< int64, int64 > > ds;

int64 pow2(int s)
{
  int64 t = 1;
  for(int i = 0; i < s; i++) t *= 2;
  return (t);
}

pair< int64, int64 > rec(int64 a, int64 b, int64 depth)
{
  if(a >= b) return {0, 1};
  if(depth == 1) return {1, 1};
  if(a == 0 && b > szCalc[depth]) return {sum1[depth], sum2[depth]};
  if(ds.count({a, b, depth})) return (ds[{a, b, depth}]);
  int64 mid = szCalc[depth - 1];
  pair< int64, int64 > ks(0, 1);
  string ss = to_string(1LL * depth * depth);
  for(int i = 0; i < ss.size(); i++) {
    int64 pos = mid + i;
    ss[i] -= '0';
    if(ss[i] == 0) ss[i] += 10;
    if(a <= pos && pos < b) {
      (ks.first += ss[i] % mod) %= mod;
      (ks.second *= ss[i] % mod) %= mod;
    }
  }
  int64 shift = mid + (int64) ss.size();
  auto get1 = rec(a, min(mid, b), depth - 1);
  auto get2 = rec(max(0LL, a - shift), b - shift, depth - 1);
  (ks.first += get1.first) %= mod;
  (ks.first += get2.first) %= mod;
  (ks.second *= get1.second) %= mod;
  (ks.second *= get2.second) %= mod;
  return (ds[{a, b, depth}] = ks);
}


int main()
{
  int64 N, L, R;
  cin >> N >> L >> R;
  --L;
  for(int i = 1; i < 59; i++) {
    int64 base = 1, res = 0, a = 0, b = 1;
    for(int j = i; j >= 1; j--) {
      string p = to_string(1LL * j * j);
      int64 c = 0, d = 1;
      for(int k = 0; k < p.size(); k++) {
        int bb = p[k] - '0';
        if(bb == 0) bb += 10;
        c += bb;
        d *= bb;
        c %= mod;
        d %= mod;
      }
      res += p.size() * base;
      a += c * base % mod;
      b *= d * base % mod;
      base *= 2;
    }
    szCalc[i] = res;
    sum1[i] = a;
    sum2[i] = b;
  }

  int K = 1;
  while(szCalc[K] < R) ++K;
  if(N < K) {
    cout << -1 << endl;
    return (0);
  }
  auto get = rec(L, R, K);
  cout << get.first << " " << get.second << endl;
}
0