結果

問題 No.492 IOI数列
コンテスト
ユーザー Xiaoxiao Deng
提出日時 2025-11-11 15:13:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 2,787 bytes
コンパイル時間 2,000 ms
コンパイル使用メモリ 202,812 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-11 15:13:08
合計ジャッジ時間 3,249 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;

// AtCoder Beginner Contest 042(D - いろはちゃんとマス目 / Iroha and a Grid)
// https://atcoder.jp/contests/abc042/tasks/arc058_b
// Fermat's little theorem を 適用するため, 大きな冪乗の計算ができるようにする.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL inverse(LL a, LL b){
    LL t = 1;
    while(b) {
        if(b & 1) t = (t * a) % MOD;
        a *= a;
        a %= MOD;
        b >>= 1;
    }
    return t % MOD;
}

// yukicoder(No.16 累乗の加算)
// x の A乗 を MOD で割った余りを計算.
// @param x: 底.
// @param A: 冪指数.
// @return ans: x の A乗 を MOD で割ったときの余り.
LL mod(LL x, LL A){

    // 1. A を 2で割っていく.
    map<LL, LL> m;
    while(A){
        LL q = A / 2;
        LL r = A % 2;
        m[q] = r;
        A /= 2;
    }
    // for(auto &p : m) cout << p.first << " " << p.second << endl;

    // 2. 1. の 結果から, 余りを逆算.
    LL ans = 1;
    for(auto &p : m){
        // A が 0 でない場合は, ans = ans * ans で, もとのべき乗数が復元されると解釈する.
        // -> ex. 729 = 3 * 3 * 3 * 3 * 3 * 3 (= 3 の 6乗)なので, 
        // (3 * 3 * 3) * (3 * 3 * 3) = 729 と読み替えると, 
        // 729 は, (3 * 3 * 3) の 2乗 と見ることが出来るからである.
        if(p.first != 0)  ans *= ans, ans %= MOD;
        // 余りが 1 の場合は, 底が, 1回分多く掛け算されていると解釈する.
        if(p.second == 1) ans *= x, ans %= MOD;
    }
    
    return ans;

}

int main() {
    
    // 1. 入力情報取得.
    LL N;
    cin >> N;
    
    // 2. IOI数列の第N項について, 101010101010101010101で割った余りを計算.
    string ans101010101010101010101[11] = {
        "0",
        "1",
        "101",
        "10101",
        "1010101",
        "101010101",
        "10101010101",
        "1010101010101",
        "101010101010101",
        "10101010101010101",
        "1010101010101010101"
    };
    LL modN11 = N % 11;
    
    // 3. IOI数列の第N項について, 1000000007で割った余りを計算.
    // A[N] = (100 の N乗 - 1) ÷ 99 なので, 1 / 99 (mod 1000000007) = 646464651 を計算.
    LL INV99 = inverse(99, MOD - 2) % MOD;
    // cout << "INV99=" << INV99 << endl;
    // -> INV99 = 646464651
    LL ans1000000007 = mod(100, N);
    ans1000000007--;
    // cout << "ans1000000007=" << ans1000000007 << endl;
    ans1000000007 *= INV99;
    ans1000000007 %= MOD;
    
    // 4. 出力.
    cout << ans1000000007 << endl;
    cout << ans101010101010101010101[modN11] << endl;
    return 0;
    
}
0