H(dp计数)

题意：

　　有一颗树，最深的点的深度是n，每个深度为i的点都有ai个孩子。

　　对于1<=k<=2n-2，回答树上有多少点对之间的距离是k，答案对1e9+7取模

　　n<=5000,ai<=1e9

分析：

　　考虑在lca处计数，发现时间复杂度是O(n^3)，即使用卷积优化也仍旧是O(n^2logn)的，无法通过n=5000的情况

　　考虑另一种计数方式，在端点处计数，分为两种，一种是down，一种是up，down就比较好处理，至于up考虑根据上一个深度来dp

　　考虑up的时候只有两种决策，一种是挂一个下来，另一种是在当前深度的上一个进行转弯，分别计数即可

　　时间复杂度O(n^2)

G(FFT+dsu)

题意：

　　我们定义两个等长字符串x和y的距离就是将最少的字母让另一种字母替代，使得x=y

　　现在给出两个字符串S，T，|S|>=|T|，问S的所有长度为T的子串，每个子串和T的距离分别是多少，都要输出

　　|S|<=125000

　　字符集只有abcdef

分析：

　　考虑如何求两个等长字符串的距离，我们只需要给对应字母建个无向图，答案就是点数-连通块个数

　　因为字符集很小，只有abcdef，所以连边情况只有36种，可以状态压缩

　　我们可以枚举s中的某个字母a，t中的某个字母b，看看有哪些位置的S子串会被这个(a,b)贡献到

　　这个东西可以用卷积来实现

　　把s中a的对应位置抠出来赋值为1，其它为0，把t中b的对应位置抠出来赋值为1，其它为0，两个多项式卷积一下就行了

1 #include
      
         2 using namespace std;  3 const int maxn=5e5;  4 const double pi=acos(-1.0);  5 char t[maxn+5],s[maxn+5];  6 int id[6][6];  7 pair
       
         index[36];  8 long long state[maxn+5];  9 int n,m; 10 struct wjmzbmr 11 { 12     double r,i; 13     wjmzbmr(double real=0.0,double image=0.0){r=real;i=image;} 14     wjmzbmr operator + (const wjmzbmr o) 15     { 16         return wjmzbmr(r+o.r,i+o.i); 17     } 18     wjmzbmr operator - (const wjmzbmr o) 19     { 20         return wjmzbmr(r-o.r,i-o.i); 21     } 22     wjmzbmr operator * (const wjmzbmr o) 23     { 24         return wjmzbmr(r*o.r-i*o.i,r*o.i+i*o.r); 25     } 26 }; 27 wjmzbmr x1[maxn+5],x2[maxn+5]; 28 void brc(wjmzbmr *y,int l) 29 { 30     for(int i=1,j=l/2;i
        
         =k)j-=k,k/=2; 35         if(j
         
          0) state[i]|=(1LL<