BZOJ1009 [HNOI2008] GT 시험(KMP 알고리즘 + 행렬 가속 dp)
수험표 번호를 순서대로 처리하고,
f[i][j]를 설정하면 수험표 전 i위 중 후 j위와 불길수의 전 j위상이 동시에 전 i위의 방안수를 나타낸다.
그럼 정답ans=f[n][0]+f[n][1]+...+f[n][m-1]
f[i][j]의 정확한 의미:
1. f[i][j]가 표시하는 모든 방안은 그 후 j위와 관련이 있을 뿐만 아니라 불길한 수를 포함하지 않는다는 것을 보증해야 한다.
2. 중복을 피하기 위해 f[i][j]가 표시하는 모든 방안은 j보다 길이가 크고 불길한 접두사와 같은 접두사를 포함하지 않는다
그렇지 않으면 다음과 같다. 1부터 m 표지, 불길수가 123124일 때 f[i][2]계수 방안에 f[i][5]계수 방안이 포함된 경우
상태 전환:
f[i][j]는 f[i-1][k]만 얻을 수 있으며, i-1위를 채운 후 접미사 k(k로 긴 접미사) 뒤에 num을 한 명 추가하는 것과 같다. 그 다음에 이 i자리의 불길한 접미사와 같은 가장 긴 접미사는 접미사 j이다.
i>=1시: f[i][j]=f[i-1][0]*a[0][j]+f[i-1][1]*a[1][j]]+...+f[i-1][m-1]*a[m-1][j]
예를 들어 불길한 수가 123124라고 가정하면 f[i][3]=f[i-1][2]+f[i-1][5]는 f[i-1][2]의 끝에 있는 ******12는 *12312가 아니기 때문에 f[i-1][5]의 보충이 필요하다.
그러나 불길한 수가 123123이면 f[i][3]=f[i-1][2], f[i][3]의 끝에 있는 *****123은 **123123이 아니기 때문이다.
i==0시: f[0][0]=1, f[0[기타]=0
그 중에서 a[k][j]는 위에서 언급한num에서 몇 개의 값을 얻을 수 있음을 나타내고 kmp 알고리즘으로 미리 처리할 수 있으며 이것은 하나의 행렬이다.
이렇게 하면 무겁지도 빠뜨리지 않고 계산할 수 있다
다시 매트릭스 가속: f[i][j] 구법은 선형 일차 추이식으로 매트릭스로 구성할 수 있다
문제가 있으면 저와 교류하는 것을 환영합니다.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int next[25]={0},hash[155]={0};
char t[25]={0};
int m,mod;
struct juzhen
{
int s[25][25];
juzhen()
{
memset(s,0,sizeof(s));
}
};
juzhen A,Z;
juzhen cheng(juzhen A,juzhen B)
{
juzhen res;
int i,j,k;
for(i=0;i<m;i++)
for(j=0;j<m;j++)
{
for(k=0;k<m;k++)
res.s[i][j]+=A.s[i][k]*B.s[k][j];
res.s[i][j]%=mod;
}
return res;
}
juzhen ksm(juzhen A,int n)
{
juzhen res;
if(n==1) return A;
res=ksm(A,n/2);
res=cheng(res,res);
if(n%2==1) res=cheng(res,A);
return res;
}
int main()
{
int n,i,j,sum,ans=0;
scanf("%d%d%d
",&n,&m,&mod);
for(i=1;i<=m;i++)
scanf("%c",&t[i]);
next[1]=next[2]=1;
for(i=2;i<m;i++)
{
j=next[i];
while(j>1&&t[i]!=t[j]) j=next[j];
if(t[j]==t[i]) next[i+1]=j+1;
else next[i+1]=1;
}
Z.s[0][0]=1;//f[0][0]==1
for(i=0;i<m;i++)// a[][]
{
j=i+1;
sum=A.s[i][j]=1;
hash[t[j]]=i+1;
while(j!=1)
{
j=next[j];
if(hash[t[j]]!=i+1)
{
A.s[i][j]=1;
hash[t[j]]=i+1;
sum++;// j( 0)
}
}
A.s[i][0]=10-sum;// i 10 ，
}
Z=cheng(Z,ksm(A,n));
for(i=0;i<m;i++)
ans+=Z.s[0][i];
printf("%d",ans%mod);
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
