bzoj 3530: [Sdoi 2014] 개수
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #define M 1509
5 #define MO 1000000007
6 #define ll long long
7 using namespace std;
8 char a[M];
9 int b[M],c[M],n,shu[M][10],tot=1,m,n1,fail[M],q[M],f[1202][1505][3];
10 ll ans;
11 bool bo[M];
12 void dp(int a1)
13 {
14 for(int i=1;i<=tot;i++)
15 for(int l=0;l<=1;l++)
16 {
17 if(bo[i]||!f[a1-1][i][l])
18 continue;
19 for(int j=0;j<=9;j++)
20 {
21 int k=i;
22 for(;!shu[k][j];k=fail[k]);
23 f[a1][shu[k][j]][l+j>b[a1]]=(f[a1][shu[k][j]][l+j>b[a1]]+f[a1-1][i][l])%MO;
24 if(!j)
25 f[a1][shu[k][j]][2]=(f[a1][shu[k][j]][2]+f[a1-1][i][l])%MO;
26 }
27 }
28 return;
29 }
30 int main()
31 {
32 scanf("%s",a+1);
33 n=strlen(a+1);
34 for(int i=1;i<=n;i++)
35 b[n-i+1]=a[i]-'0';
36 scanf("%d",&m);
37 for(int i=1;i<=m;i++)
38 {
39 scanf("%s",a+1);
40 n1=strlen(a+1);
41 for(int j=1;j<=n1;j++)
42 c[n1-j+1]=a[j]-'0';
43 int now=1;
44 for(int j=1;j<=n1;j++)
45 if(shu[now][c[j]])
46 now=shu[now][c[j]];
47 else
48 {
49 shu[now][c[j]]=++tot;
50 now=tot;
51 }
52 bo[now]=1;
53 }
54 for(int i=0;i<=9;i++)
55 shu[0][i]=1;
56 int h=0,t=1;
57 q[1]=1;
58 for(;h<t;)
59 {
60 h++;
61 int p=q[h];
62 for(int i=0;i<=9;i++)
63 if(shu[p][i])
64 {
65 q[++t]=shu[p][i];
66 int k=fail[p];
67 for(;!shu[k][i];k=fail[k]);
68 fail[shu[p][i]]=shu[k][i];
69 }
70 }
71 f[0][1][0]=1;
72 for(int i=1;i<=n;i++)
73 dp(i);
74 for(int i=1;i<n;i++)
75 for(int j=1;j<=tot;j++)
76 if(!bo[j])
77 ans=(ans+(ll)f[i][j][0]+f[i][j][1]-f[i][j][2])%MO;
78 for(int i=1;i<=tot;i++)
79 if(!bo[i])
80 ans=(ans+f[n][i][0]-f[n][i][2])%MO;
81 printf("%lld
",ans);
82 return 0;
83 }
AC 자동 동기 상 주 디지털 DP
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.