結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー ei1333333
提出日時 2017-03-11 00:32:50
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,415 bytes
コンパイル時間 1,491 ms
コンパイル使用メモリ 160,760 KB
実行使用メモリ 13,884 KB
最終ジャッジ日時 2024-06-24 09:18:31
合計ジャッジ時間 5,170 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 55 TLE * 1 -- * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

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


int64 szCalc[62];

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};
  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), max(0LL, 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 (ks);
}


int main()
{
  int64 N, L, R;
  cin >> N >> L >> R;
  --L;

  for(int i = 1; i < 59; i++) {
    int64 base = 1, ret = 0;
    for(int j = i; j >= 1; j--) {
      string p = to_string(1LL * j * j);
      ret += p.size() * base;
      base *= 2;
    }
    szCalc[i] = ret;
  }

  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