Codeforces Round \ # 291 (Div. 2) E - Darth Vader and Tree (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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.