Codeforces Round #341(Div.2) E. Wet Shark and Blocks(dp + 매트릭스 신속 멱)

제목:
b≤109개의 숫자를 정하고 각 블록에 n≤105개의 숫자가 있다. 현재 각 블록에서 하나의 큰 숫자를 골라 이 큰 숫자 MOD x=k의 방법수, x, k≤100을 구한다.
분석:
한 가지 이해: dp[i][j]: =모드x에서 i를 얻었고 (\872710+k), 모드x에서 j를 얻는 방법수는 분명히 이것은 b번을 해야 한다. 분명히 ans=dpb[0][k]에서 dp1[i] [j] 이 행렬을 미리 처리한 다음에 우리가 발견한 것은 행렬의 자승이다. 예를 들어 dp2[i] [k][k]=∑9[k]=∑9j=0j=0dp1[i] [j][i] [j]가 있고 dp1[j][j][k]]에서 행렬의 빠른 멱을 옮기면 우리가 발견한 것은 행렬의 속도를 가속화하면 다른 이해 방법이 있다. 예를 들어 다른 방법: f[i]: f[i] ii] 모드의 숫자 모드수 수 수 있는 방법은 다른 이해 방법::f[j]의 이해: 다른 이해::::::이동이 바로 위에 있는 dp1[i][j] 행렬을 발견하면,ans=f[b][k]=f[0][0] ∗dpb[0][k], 같은 매트릭스 빠른 멱은 상기 두 가지를 가속시킨다. 매트릭스 빠른 멱은 복잡도가 모두 O(x3logb)이기 때문에 사실 두 번째 이해는 분치로 b의 이동을 가속화할 수 있다. 복잡도는 O(x2logb)이다.
첫 번째 코드를 제공합니다.

//
// Created by TaoSama on 2016-01-31
// Copyright (c) 2015 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 100 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

typedef long long LL;

struct Matrix {
    int row, col;
    LL mat[N][N];
    void init(int row, int col, bool one = false) {
        this->row = row; this->col = col;
        memset(mat, 0, sizeof mat);
        if(!one) return;
        for(int i = 0; i < row; ++i) mat[i][i] = 1;
    }
    Matrix operator* (const Matrix& rhs) {
        Matrix ret; ret.init(row, rhs.col);
        for(int k = 0; k < col; ++k) {
            for(int i = 0; i < row; ++i) {
                if(mat[i][k] == 0) continue;
                for(int j = 0; j < rhs.col; ++j) {
                    if(rhs.mat[k][j] == 0) continue;
                    ret.mat[i][j] += mat[i][k] * rhs.mat[k][j] % MOD;
                    ret.mat[i][j] %= MOD;
                }
            }
        }
        return ret;
    }
    Matrix operator^ (LL n) {
        Matrix ret, x = *this;
        ret.init(row, col, 1);
        while(n) {
            if(n & 1) ret = ret * x;
            x = x * x;
            n >>= 1;
        }
        return ret;
    }
} A;

int n, b, k, x;
int cnt[10];

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(scanf("%d%d%d%d", &n, &b, &k, &x) == 4) {
        memset(cnt, 0, sizeof cnt);
        for(int i = 1; i <= n; ++i) {
            int z; scanf("%d", &z);
            ++cnt[z];
        }
        printf("%d
", sizeof(long double));
        A.init(x, x);
        for(int i = 0; i < x; ++i)
            for(int j = 0; j < 10; ++j)
                A.mat[i][(i * 10 + j) % x] += cnt[j];

        Matrix ans = A ^ b;
        printf("%I64d
", ans.mat[0][k]);
    }
    return 0;
}