結果

問題 No.493 とても長い数列と文字列(Long Long Sequence and a String）
ユーザー はまやんはまやん
提出日時 2017-03-11 01:25:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 800 ms
コード長 2,882 bytes
コンパイル時間 1,829 ms
コンパイル使用メモリ 168,860 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-24 09:28:18
合計ジャッジ時間 4,439 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 115
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long ll;
int mod = 1000000007;
int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
template<class... T> int add(int x, T... y) { return add(x, add(y...)); }
int mul(int x, int y) { return 1LL * x * y % mod; }
template<class... T> int mul(int x, T... y) { return mul(x, mul(y...)); }
int sub(int x, int y) { return add(x, mod - y); }
int modpow(int a, long long b) {
    int ret = 1;
    while (b > 0) {
        if (b & 1) ret = 1LL * ret * a % mod;
        a = 1LL * a * a % mod; b >>= 1;
    }
    return ret;
}
int modinv(int a) { return modpow(a, mod - 2); }
//-----------------------------------------------------------------
ll K, L, R;
//-----------------------------------------------------------------
ll sz[63], sm[63];
int mu[63];
void pre() {
    sz[0] = 0;
    rep(i, 1, 63) {
        int c = 0;
        int ii = i * i;
        while (0 < ii) c++, ii /= 10;
        sz[i] = 2 * sz[i - 1] + c;
    }
    sm[0] = 0;
    rep(i, 1, 63) {
        ll c = 0;
        int ii = i * i;
        while (0 < ii) {
            if (ii % 10 == 0) c += 10;
            else c += ii % 10;
            ii /= 10;
        }
        sm[i] = 2 * sm[i - 1] + c;
    }
    mu[0] = 1;
    rep(i, 1, 63) {
        int c = 1;
        int ii = i * i;
        while (0 < ii) {
            if (ii % 10 == 0) c = mul(c, 10);
            else c = mul(c, ii % 10);
            ii /= 10;
        }
        mu[i] = mul(mu[i - 1], mu[i - 1], c);
    }
    //rep(i, 0, 63) printf("%d -> %lld\n", i, sz[i]);
}
//-----------------------------------------------------------------
ll calcSum(int K, ll x) {
    if (x == 0) return 0;
    if (x <= sz[K - 1]) return calcSum(K - 1, x);
    ll s = sz[K] - sz[K - 1];
    string kk = to_string(K * K);
    if (x <= s) {
        ll ret = sm[K - 1];
        x -= sz[K - 1];
        int ki = 0;
        while (0 < x) {
            if (kk[ki] == '0') ret += 10;
            else ret += kk[ki] - '0';
            x--; ki++;
        }
        return ret;
    }
    ll ret = sm[K - 1];
    rep(i, 0, kk.length()) {
        if (kk[i] == '0') ret += 10;
        else ret += kk[i] - '0';
    }
    return ret + calcSum(K - 1, x - s);
}
//-----------------------------------------------------------------
ll calcMul(int K, ll x) {
    if (x == 0) return 1;
    if (x <= sz[K - 1]) return calcMul(K - 1, x);
    ll s = sz[K] - sz[K - 1];
    string kk = to_string(K * K);
    if (x <= s) {
        ll ret = mu[K - 1];
        x -= sz[K - 1];
        int ki = 0;
        while (0 < x) {
            if (kk[ki] == '0') ret = mul(ret, 10);
            else ret = mul(ret, kk[ki] - '0');
            x--; ki++;
        }
        return ret;
    }
    ll ret = mu[K - 1];
    rep(i, 0, kk.length()) {
        if (kk[i] == '0') ret = mul(ret, 10);
        else ret = mul(ret, kk[i] - '0');
    }
    return mul(ret, (int)calcMul(K - 1, x - s));
}
//-----------------------------------------------------------------
int main() {
    pre();
    cin >> K >> L >> R;
    if (63 <= K) K = 62;
    if (sz[K] < R) {
        printf("-1\n");
        return 0;
    }
    ll a = calcSum(K, R) - calcSum(K, L - 1);
    ll b = mul(calcMul(K, R), modinv(calcMul(K, L - 1)));
    printf("%lld %lld\n", a, b);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0