题解：http://blog.csdn.net/xingyeyongheng/article/details/10005923

这里采用了二分法求等比数列前n项和。

等比数列前n项和也可以用矩乘快速幂来求[a 1]    [Sn]    =    [Sn+1]

　　　　　　　　　　　　　　　　　　  [0 1]    [a  ]          [   a   ]

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef unsigned long long ull;typedef vector
          
            vec;typedef vector
           
             mat;typedef pair
            
              Point2;typedef pair
             
               Point;int N;mat I;mat operator * (const mat &a,const mat &b){ mat c(N,vec(N)); for(int i=0;i
              
               >1); if(n&1) return Point(t.first*t.first*a,t.second*(t.first*a+1)); else return Point(t.first*t.first,(t.second-t.first)*(t.first*a+1)+t.first);}Point2 sum_A_n(mat a,ull n){ if(n==0) return Point2(I,I); Point2 t=sum_A_n(a,n>>1); if(n&1) return Point2(t.first*t.first*a,t.second*(t.first*a+I)); else return Point2(t.first*t.first,(t.second-t.first)*(t.first*a+I)+t.first);}queue
               
                q;int child[40][26],fail[40],size=1;bool word[40];void Insert(char S[]){ int len=strlen(S); int now=0; for(int i=0;i
                
                 >n>>m){ Init(); for(int i=1;i<=n;++i) { scanf("%s",s); Insert(s); } build(); for(int i=0;i