Codeforces Round \ # 291 (Div. 2) E - Darth Vader and Tree (DP + 매트릭스 쾌속 멱)

이 문 제 는 오랫동안 생각 했 지만 결단력 이 없다.그래서 문 제 를 찾 아 봤 습 니 다.문제 풀이 의 '쾌속 멱' 이라는 두 글 자 를 보 니 틀 렸 다.이 세 글자.제호 가 머리 에 들 어 오 는 것 과 같 군...............................................x 의 범 위 는 10 ^ 9 이기 때문에 그때 생각 할 때 과감하게 dp 를 밀어 내 는 방법 을 버 렸 습 니 다.나 는 왜 행렬 의 빠 른 멱 을 생각 하지 못 했 을 까..................................................너무 약해.sad。。100 * 100 * 100 * log (10 ^ 9) 의 복잡 도가 딱 좋다.그래서 행렬 의 빠 른 멱 을 생각 하 니 모든 것 이 간단 해 졌 다.거리 < = x 의 모든 거리의 점 수 를 DP 를 통 해 밀어 내 고 빠 른 속도 로 해결 할 수 있 습 니 다.우선 DP 전달 식 은 생각 하기 쉽다.전달 코드 는 다음 과 같 습 니 다.

for(i=1; i<=x; i++) { dp[i]=0; for(j=1; j<=i; j++) { dp[i]+=dp[i-j]*a[j]; } }

dp [i] 는 거리 가 i 인 점 의 개 수 를 나타 낸다.각 단락 의 거리 가 최대 100 이기 때문에 아래 의 j 의 순환 은 최대 100 회 에 불과 하 다.그러면 100 * 100 의 행렬 을 만들어 이 전달 과정 을 실현 할 수 있다.먼저 100 개의 dp 값 을 처리 한 후에 행렬 의 빠 른 멱 을 끼 우 면 된다.코드 는 다음 과 같 습 니 다:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
LL a[102], dp[102], sum[102];
struct Matrix {
        LL ma[102][102];
} init,res;
Matrix Mult(Matrix x, Matrix y)
{
        Matrix tmp;
        for(int i=0; i<101; i++) {
                for(int j=0; j<101; j++) {
                        tmp.ma[i][j]=0;
                        for(int k=0; k<101; k++) {
                                tmp.ma[i][j]+=x.ma[i][k]*y.ma[k][j];
                                if(tmp.ma[i][j]>=mod) tmp.ma[i][j]%=mod;
                        }
                }
        }
        return tmp;
}
Matrix Pow(Matrix x, int k)
{
        Matrix tmp;
        int i, j;
        for(i=0; i<101; i++) for(j=0; j<101; j++) tmp.ma[i][j]=(i==j);
        while(k) {
                if(k&1) tmp=Mult(tmp,x);
                x=Mult(x,x);
                k>>=1;
        }
        return tmp;
}
int main()
{
        int n, x, i, j, y;
        while(scanf("%d%d",&n,&x)!=EOF) {
                memset(a,0,sizeof(a));
                memset(dp,0,sizeof(dp));
                for(i=0; i<n; i++) {
                        scanf("%d",&y);
                        a[y]++;
                }
                dp[0]=1;
                sum[0]=0;
                for(i=1; i<=100; i++) {
                        for(j=1; j<=i; j++) {
                                dp[i]+=dp[i-j]*a[j];
                                if(dp[i]>=mod) dp[i]%=mod;
                        }
                        sum[i]=sum[i-1]+dp[i];
                        if(sum[i]>=mod) sum[i]%=mod;
                }
                if(x<=100) {
                        printf("%I64d
",(sum[x]+1)%mod);
                        continue ;
                }
                memset(init.ma,0,sizeof(init.ma));
                for(i=0; i<100; i++) {
                        init.ma[0][i]=init.ma[100][i]=a[i+1];
                }
                for(i=1; i<100; i++) {
                        init.ma[i][i-1]=1;
                }
                init.ma[100][100]=1;
                res=Pow(init,x-100);
                LL ans=(sum[100]*res.ma[100][100])%mod;
                for(i=1; i<=100; i++) {
                        ans+=dp[i]*res.ma[100][100-i];
                        if(ans>=mod) ans%=mod;
                }
                printf("%I64d
",(ans+1)%mod);
        }
        return 0;
}