結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
コンテスト
ユーザー ei1333333
提出日時 2017-03-11 01:09:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,097 bytes
コンパイル時間 1,883 ms
コンパイル使用メモリ 180,100 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-24 09:26:36
合計ジャッジ時間 5,023 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 112 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 >, pair< int64, int64 > > ds;

inline int64 modPow(int64 x, int64 n)
{
  if(n == 0) return (1);
  int64 ret = modPow(x, n / 2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return (ret);
}

inline int64 modInv(int64 a)
{
  return (modPow(a, mod - 2));
}


pair< int64, int64 > rec(int64 b, int64 depth)
{
  if(b <= 0) return {0, 1};
  if(depth <= 1) return {1, 1};
  if(b > szCalc[depth]) return {sum1[depth], sum2[depth]};
  if(ds.count({b, depth})) return (ds[{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(pos < b) {
      (ks.first += ss[i]);
      (ks.second *= ss[i] % mod) %= mod;
    }
  }
  int64 shift = mid + (int64) ss.size();
  auto get1 = rec(min(mid, b), depth - 1);
  auto get2 = rec(max(0LL, b - shift), depth - 1);
  (ks.first += get1.first);
  (ks.first += get2.first);
  (ks.second *= get1.second) %= mod;
  (ks.second *= get2.second) %= mod;
  return (ds[{b, depth}] = ks);
}

int main()
{
  int64 N, L, R;
  cin >> N >> L >> R;
  --L;
  for(int i = 1; i < 60; 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;
        d %= mod;
      }
      res += p.size() * base;
      a += c * base;
      b *= d * (base % mod) % mod;
      b %= 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 get1 = rec(R, K);
  auto get2 = rec(L, K);

  cout << -get2.first + get1.first << " " << get1.second * modInv(get2.second) % mod << endl;
}
0