結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー ei1333333ei1333333
提出日時 2017-03-11 00:19:45
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,387 bytes
コンパイル時間 1,441 ms
コンパイル使用メモリ 162,248 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-06-24 09:16:41
合計ジャッジ時間 5,208 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 2
other AC * 1 WA * 54 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};
  if(depth == 1) return {1, 1};
  int64 mid = szCalc[depth - 1];
  pair< int64, int64 > ks(0, 1);
  string ss = to_string(depth);
  for(int i = 0; i < ss.size(); i++) {
    int64 pos = mid + i;
    ss[i] -= '0';
    if(ss[i] == 0) ss[i] += 10;
    ss[i] *= ss[i];
    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;

  int64 res = 0;
  for(int i = 1; i < 59; i++) {
    string p = to_string(1LL * i * i);
    res *= 2;
    res += p.size();
    szCalc[i] = res;
  }

  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