10.21T4 字典树+高精度

Description

　　平平带着韵韵来到了游乐园，看到了n辆漂亮的遥控车，每辆车上都有一个唯一的名字name[i]。韵韵早就迫不及待地想玩名字是s的遥控车。可是韵韵毕竟还小，她想象的名字可能是一辆车名字的前缀（也就是说能确定一个i，使s是name[i]的前缀），这时她就能玩第i辆车；或者是一个无中生有的名字，即s不是任何一辆车名字的前缀，这时候她什么也不能玩。
　　你需要完成下面的任务：
　　1.韵韵想了m个她想要的名字，请告诉她能玩多少次。
　　2.由于管理员粗心的操作，导致每辆车的摆放位置都可能出现微小的差错，原来第i辆车现在的位置可能是i-1、i、i+1中的任意一个（第1辆车的位置不可能是0，第n辆车的位置不可能是n+1）。请你计算出共有多少种可能的排列。
　　注：数据保证当s是name[i]的前缀时，i是唯一确定的。一辆车可以玩多次。

Input

　　第一行是2个正整数n、m。
　　接下来n行，每行1个字符串name[i]，表示第i辆车的名字。
　　接下来m行，每行1个字符串s，表示韵韵想要的名字。

Output

　　第一行输出韵韵能玩的次数。
　　第二行输出共有多少种可能的排列。

Sample Input

4 4

Abcd

DeF

AAa

aBccc

AbC

aBcc

Sample Output

Hint

【数据规模】：
　　对于题目涉及到的字符串严格区分大小写，且长度小于255。
　　对于20％的数据 n≤10,m≤10；
　　对于40％的数据 n≤1000，m≤1000；
　　对于100％的数据 n≤10000，m≤10000。

第一问字典树很简单

第二问明显方程是f[i]=f[i-1]+f[i-2]，因为与后面交换与跟前面交换实际上是一个道理

换和不换转移一下就可以了

code：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<string>
  4 #include<cstring>
  5 #define N 100005
  6 #define P 10000
  7 using namespace std;
  8 int ch[700001][52];
  9 int tot,num[N];
 10 void insert(string k) {
 11     int now=0;
 12     for(int i=0; i<k.size(); i++) {
 13         if(!ch[now][k[i]]) {
 14             ch[now][k[i]]=++tot;
 15             now=tot;
 16         } else {
 17             now=ch[now][k[i]];
 18         }
 19     }
 20 }
 21 string name[N];
 22 string f[N];
 23 string add(string str1,string str2) { //高精度加法
 24     string str;
 25     int len1=str1.length();
 26     int len2=str2.length();
 27     //前面补0，弄成长度相同
 28     if(len1<len2) {
 29         for(int i=1; i<=len2-len1; i++)
 30             str1="0"+str1;
 31     } else {
 32         for(int i=1; i<=len1-len2; i++)
 33             str2="0"+str2;
 34     }
 35     len1=str1.length();
 36     int cf=0;
 37     int temp;
 38     for(int i=len1-1; i>=0; i--) {
 39         temp=str1[i]-'0'+str2[i]-'0'+cf;
 40         cf=temp/10;
 41         temp%=10;
 42         str=char(temp+'0')+str;
 43     }
 44     if(cf!=0)  str=char(cf+'0')+str;
 45     return str;
 46 }
 47 struct Gaojin{
 48     int top,a[1000];
 49     Gaojin(){memset(a,0,sizeof(a));top=0;}
 50 };
 51 Gaojin operator +(const Gaojin A,const Gaojin B){
 52     Gaojin C;C.top=max(A.top,B.top);
 53     for(int i=1;i<=C.top;++i)C.a[i]=A.a[i]+B.a[i];
 54     for(int i=1;i<C.top;++i)if(C.a[i]>=P){
 55         C.a[i]-=P;++C.a[i+1];
 56     }
 57     while(C.a[C.top]>=P){C.a[C.top]-=P;C.a[++C.top]++;}
 58     return C;
 59 }
 60 void Out(const Gaojin C){
 61     cout<<C.a[C.top];
 62     for(int i=C.top-1;i;--i){
 63         printf("%04d",C.a[i]);
 64     }
 65 }
 66 int main() {
 67     int n,m;
 68     cin>>n>>m;
 69     for(int i=1; i<=n; i++) {
 70         cin>>name[i];
 71         insert(name[i]);
 72     }
 73     int ans=0;
 74     for(int i=1; i<=m; i++) {
 75         string temp;
 76         cin>>temp;
 77         int now=0,flag=0;
 78         for(int j=0; j<temp.size(); j++) {
 79             if(ch[now][temp[j]]) {
 80                 now=ch[now][temp[j]];
 81             } else {
 82                 flag=1;
 83                 break;
 84             }
 85         }
 86         if(flag)continue;
 87         ans++;
 88     }
 89     cout<<ans<<'
';
 90     if(n==0) {
 91         cout<<0;
 92         return 0;
 93     }
 94     if(n==1) {
 95         cout<<1;
 96         return 0;
 97     }
 98     Gaojin A;
 99     A.top=1;
100     A.a[1]=1;
101     Gaojin B;
102     B.top=1;
103     B.a[1]=1; 
104     for(int i=2; i<=n; i++) {
105         Gaojin C=A+B;
106         A=B;
107         B=C;
108     }
109     Out(B);
110     return 0;
111 }

over