CFR 621 E. Wet Shark and Blocks ( DP, Fast Matrix Multiplication )

Problem - E - Codeforces

題意：
給一個序列，每次隨便選一個數字，加到字串尾。求有幾種方法，挑 B 個數字後，除以 X 的餘數為 K。

資料規模：
數字量 2  ≤ N  ≤  50 000
 1  ≤ B  ≤  1e9,  0 ≤ K  <  X  ≤  100, x  ≥  2
數字大小 1 ≤  A[ i ] ≤  9
時限 2000 ms
記憶體 256 MB

解法：
dp[ i ][ j ][ k ] : 挑 i 個數字後，原本為 j，變成 k 的方法數
dp[ i ][ j ][ k ] = SIGMA{ dp[ i - 1 ][ j ][ m ] * dp[ i - 1 ][ m ][ k ] | for each j ≤ M ≤ k }
後兩維可以分別作為矩陣的兩維儲存，這時候的轉移和矩陣乘法等價。第一維便能因此用快速冪加速轉移。

時間 / 空間複雜度：
O( N + X ^ 3 lg B )

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
const int MAXN = 5e4 + 5;
const int MAXB = 1e9;
const int MAXX = 100;
const int MOD = 1e9 + 7;

mat mul(const mat &a, const mat &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] ) % MOD;
    return c;
}

mat pw(mat a, ll b){
    mat c( a.size(), vec( a[0].size() ) );
    for(int i = 0; i < a.size(); ++i) c[i][i] = 1;
    while( b > 0 ){
        if( b & 1LL ) c = mul( c, a );
        a = mul( a, a );
        b >>= 1LL;
    }
    return c;
}

int arr[MAXN];
int main(){
    ios::sync_with_stdio(false);
    int n, b, k, x;
    cin >> n >> b >> k >> x;
    for(int i = 0; i < n; ++i)
        cin >> arr[i];
    mat a( x, vec( x ) );
    for(int i = 0; i < x; ++i)
        for(int j = 0; j < n; ++j)
            ++a[i][ ( 10 * i + arr[j] ) % x ];
    a = pw( a, b );
    cout << a[0][k] << endl;
    return 0;
}