yukicoder No.492 IOI数列

問題

問題概要

a1 = 1, ai = 100ai-1 + 1という数列がある.
第N項を1000000007と101010101010101010101で割ったあまりを求める.

解法

前半の解
数列の一般項を求めて計算するだけ. ただし, 数が大きくなるため, 逐次modをとったり, powmodでやらないと行けない. また行列を利用して, 第n項を求める方法でもよい. 蟻本p180参照.
後半の解
答えは周期11で回っているので, mod11をしたあとに, 計算すればいい.
サンプルなどから周期はありそうで, 周期の見つけ方は,

mod = 101010101010101010101
d = 0
for i in xrange(1, 30):
    print d % mod
    d = d * 100 + 1

1
101
10101
1010101
101010101
10101010101
1010101010101
101010101010101
10101010101010101
1010101010101010101
0
1
101
10101
1010101
101010101
10101010101
1010101010101
101010101010101
10101010101010101
1010101010101010101
0
1
101
10101
1010101
101010101
10101010101
1010101010101

ミス

行列を使った問題初めて.

コード

漸化式を解くパターン

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ll INFF = 1e18;

// x^k (mod m)
long long powmod(long long x, long long k, long long m){
    long long ret = 1;
    while(k){
        if(k & 1) ret = ret * x % m;
        x = x * x % m;
        k >>= 1;
    }
    return ret;
}
// 1/a mod(p(素数))
long long invmod(long long a, long long p){
    return powmod(a, p - 2, p);
}

int main(void){
    ll n; cin >> n;
    ll d = powmod(100, n, MOD) + MOD - 1;
    d %= MOD;
    d *= invmod(99, MOD);
    printf("%lld\n", d % MOD);

    if(n % 11 == 0){
        printf("0\n"); return 0;
    }
    string s = "1";
    n %=11;
    rep(i, n  - 1){
        s = "10" + s;
    }
    cout << s << endl;

    return 0;
}

行列演算でanを求める.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ll INFF = 1e18;

typedef vector<long long> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B){ // A * B の計算
    mat C(A.size(), vec(B[0].size()));
    for(int i = 0; i < A.size(); i++){
        for(int k = 0;k < B.size(); k++){
            for(int j = 0; j < B[0].size(); j++){
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % (ll)MOD; // mod
            }
        }
    }
    return C;
}
mat pow(mat A, long long n){ // A^n の計算
    mat B(A.size(), vec(A.size()));
    for(int i = 0; i < A.size(); i++){
        B[i][i] = 1;
    }
    while(n > 0){
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}


int main(void){
    ll n; cin >> n;
    mat A(2, vec(2));
    A[0][0] = 100, A[0][1]  = 1;
    A[1][0] = 0, A[1][1] = 1;
    auto ret = pow(A, n - 1);
    ll an = (ret[0][0] + ret[0][1]) % MOD;
    printf("%lld\n", an);

    int m = n % 11;
    ll ans = 0;
    rep(i, m){
        ans = ans * 100 + 1;
    }
    printf("%lld\n", ans);
    return 0;
}