Codeforces 514E Darth Vader and Tree 矩阵快速幂

感觉是个很裸的矩阵快速幂，搞个100 × 100 的矩阵，直接转移就好啦。
#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

int n, x, c[];

struct Matrix {

    int a[][];

    Matrix() {

        memset(a, , sizeof(a));

    }

    void init() {

        for(int i = ; i < ; i++)

            a[i][i] = ;

    }

    Matrix operator * (const Matrix &B) const {

        Matrix C;

        for(int i = ; i < ; i++)

            for(int j = ; j < ; j++)

                for(int k = ; k < ; k++)

                    C.a[i][j] = (C.a[i][j] + 1ll * a[i][k] * B.a[k][j]) % mod;

        return C;

    }

    Matrix operator ^ (int b) {

        Matrix C; C.init();

        Matrix A = (*this);

        while(b) {

            if(b & ) C = C * A;

            A = A * A; b >>= ;

        }

        return C;

    }

} M;

int main() {

    scanf("%d%d", &n, &x);

    for(int i = ; i <= n; i++) {

        int v; scanf("%d", &v);

        c[v]++;

    }

    for(int j = ; j < ; j++) M.a[][j] = c[j + ]; M.a[][] = ;

    for(int i = ; i < ; i++) M.a[i][i - ] = ; M.a[][] = ;

    Matrix mat = M ^ (x);

    printf("%d\n", (mat.a[][] + mat.a[][]) % mod);

    return ;

 }

/*

*/