poj 2778 AC 자동 동기 DP
3113 단어 acm_동적 계획acm_데이터 구조
[제목 의 뜻]
poj 1625
[문제 풀이]
poj 1625 는 dp 이 고 이 문제 의 DP 는 행렬 을 통 해 이 루어 집 니 다.
【 코드 】
#include
#include
using namespace std;
const int maxn=100,base=100000,kind=4;
struct node
{
int sum,id;
node* ch[kind];
node* fail;
}a[maxn];
int ans[maxn][maxn],f[maxn][maxn];
int tot=0,m,n;
node* getroot()
{
tot++;
int i;
for (i=0;ich[k]==0)
now->ch[k]=getnode();
now=now->ch[k];
}
now->sum++;
}
queue q;
void build()
{
int i,k;
node* now,*ff;
q.push(root);
while (!q.empty())
{
now=q.front();
q.pop();
for (i=0;ich[i]!=0)
{
q.push(now->ch[i]);
for (ff=now->fail;ff!=0;ff=ff->fail)
if (ff->ch[i]!=0)
{
now->ch[i]->fail=ff->ch[i];
if (ff->ch[i]->sum==1) now->ch[i]->sum=1;//
break;
}
}
}
}
void init()
{
cin >> m >> n;
int i;
char s[maxn];
for (i=1;i<=m;i++)
{
cin >> s;
ins(s);
}
}
void get_matrix()
{
node* now,*tmp;
int i,j,ct;
for (i=1;i<=tot;i++)
for (j=0;jch[j]!=0)
{
ct=now->ch[j]->id;
if (now->ch[j]->sum==0) f[ct][i]++;
}
else
{
for (tmp=now->fail;tmp!=0;tmp=tmp->fail)
if (tmp->ch[j]!=0)
break;
if (tmp!=0) tmp=tmp->ch[j];
else tmp=root;
ct=tmp->id;
if (tmp->sum==0) f[ct][i]++;
}
}
}
void mul(int a[][maxn],int b[][maxn])
{
int i,j,k;
int c[maxn][maxn]={0};
for (i=1;i<=tot;i++)
for (j=1;j<=tot;j++)
for (k=1;k<=tot;k++)
{
long long tt=a[i][k];
tt=(tt*b[k][j])%base;
c[i][j]=(c[i][j]+int(tt))%base;
}
for (i=1;i<=tot;i++)
for (j=1;j<=tot;j++)
a[i][j]=c[i][j];
}
int cal()
{
int i,sum;
for (i=1;i<=tot;i++)
ans[i][i]=1;
while (n)
{
if (n&1)
mul(ans,f);
mul(f,f);
n>>=1;
}
sum=0;
for (i=1;i<=tot;i++)
sum+=ans[i][1];
return sum%base;
}
int main()
{
freopen("pin.txt","r",stdin);
freopen("pou.txt","w",stdout);
init();
build();
get_matrix();
cout << cal() << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 1255 커버 면적 직사각형 면적 교차평면 에 있 는 몇 개의 사각형 을 지정 하여 이 사각형 에 적어도 두 번 덮 인 구역 의 면적 을 구하 십시오. Input 데 이 터 를 입력 하 는 첫 번 째 줄 은 정수 T (1 < = T < = 100) 로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.