マジックリング

問題の説明
小易は魔力を持つ手環の上にn個の数字(環を構成する)を持っていて、この魔力の手環が魔力を使うたびに奇妙な変化が発生します:各数字は自分と後ろの数字の和になります(最後の数字の後ろの数字は最初です).ある位置の数字が100以上になるとすぐに100を型抜き(例えばある位置が103になると自動的に3になる).このマジックハンドリングの構成を示し、k回のマジックを使った後のマジックハンドリングの状態を計算してください.
説明の入力
入力データには、第1の動作の2つの整数n(2≦n≦50)とk(1≦k≦20000000)が含まれ、第2の動作の魔力ハンドリングの初期のn個の数をスペースで区切って、スペースで区切っている.範囲はいずれも0から99である.
出力の説明
出力マジックハンドリングはk回使用した後の状態で、スペースで区切られ、行末にスペースがありません.
入力例
3 2 1 2 3
出力例
8 9 7
ぶんせき
n*nのマトリクスMを構築することができる.現在の状態をベクトルと見なすと,次の状態ベクトルは現在のベクトルに行列を乗じた結果である.初期状態列ベクトル(n*1)がvであると仮定すると、最終的な状態ベクトルはM*M*に等しい...M*v=M^k*v(kは状態変換の回数)である.そこで問題は行列のべき乗をどのように迅速に解くかに変換する.行列のべき乗を二分法で迅速に解くことができ,計算の複雑さはlognである.
note

行列は、ベクトルデータの変化

を容易に記述することができる.

二分法は問題の複雑さをlogn

にすることができる.
コード#コード#

#include 
#include 
#include 

using namespace std;

vector mult(const vector> &m, const vector &v)
{
    int n = v.size();
    vector product(n, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            product[i] = (product[i] + m[i][j] * v[j]) % 100;
        }
    }
    return product;
}

vector> mult(const vector> &lhs, const vector> &rhs)
{
    int n = lhs.size();
    vector> product(n, vector(n, 0));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                product[i][j] = (product[i][j] + lhs[i][k] * rhs[k][j]) % 100;
            }
        }
    }
    return product;
}

vector> power(const vector> &m, int p)
{
    if (p <= 1)
        return m;

    vector> h = power(m, p / 2);

    if (p % 2 == 0)
        return mult(h, h);
    return mult(m, mult(h, h));
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    vector v(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);

    vector> m(n, vector(n, 0));
    for (int i = 0; i < n; i++)
    {
        m[i][i] = m[i][(i + 1) % n] = 1;
    }

    m = power(m, k);
    vector ret = mult(m, v);

    printf("%d", ret[0]);
    for (int i = 1; i < n; i++)
        printf(" %d", ret[i]);

    return 0;
}