先简短几句话说说FFT....

多项式可用系数和点值表示，n个点可确定一个次数小于n的多项式。

多项式乘积为 f(x)*g(x)，显然若已知f(x), g(x)的点值，O(n)可求得多项式乘积的点值。

我们所需要的就是O(nlogn)快速地将两个系数多项式表示成点值多项式，O(n)求得乘积的点值表示后O(nlogn)还原成系数多项式。

这里就需要套FFT板子了...

FFT中取n个单位根，需要n是2的幂。

又因为n个点可确定一个次数小于n的多项式，所以n > 乘积多项式的最高次数。

以上。

HDU4609 n个木棍任取三根能组成三角形的概率。

数组开小莫名T,WA.

1 #include 
      
        2 #define ll long long 3 using namespace std; 4 const int N = 4e5+10; 5 struct comp{ 6     double r,i;comp(double _r=0,double _i=0){r=_r;i=_i;} 7     comp operator+(const comp x){
    return comp(r+x.r,i+x.i);} 8     comp operator-(const comp x){
    return comp(r-x.r,i-x.i);} 9     comp operator*(const comp x){
    return comp(r*x.r-i*x.i,r*x.i+i*x.r);}10 };11 const double pi=acos(-1.0);12 void FFT(comp a[],int n,int t){13     for(int i=1,j=0;i
       
        >=1,~j&s;);15             if(i
        
         >1];//去掉两次取的木棍相同的53         for(int i = 0; i < len; i ++)54             sum[i] >>= 1;//算了2次55         for(int i = 1; i < len; i++)56             sum[i] += sum[i-1];57         ll tot = (ll)n*(n-1)*(n-2)/6, ans = tot;58         for(int i = 0; i <= maxnum; i++)59                 ans -= num[i]*sum[i];//去掉不能组成三角形的60         printf("%.7f\n", 1.0*ans/tot);61     }62     return 0;63 }
        
       
      

 

LA4671 给出A串与B串，只含小写字母a、b。问：A串中有多少本质不同的子串满足 与B串长度相同 且 与B串相对应位置字符不同的数量小于k。

题解：a做1，b做0。将B倒着来一遍和A做卷积，可得有多少位置A串与B串都是a。a做0，b做1再来一遍即可。

hash！37做基1000173169做模会冲突！1e9+7做基1e9+9做模也会冲突！双哈希可以过，37做基2^64做模可过，37做基100000000173169LL做模也可过....

1 #include 
      
        2 #define ull unsigned long long 3 using namespace std; 4 const int N = 4e5+10; 5 struct comp{ 6     double r,i;comp(double _r=0,double _i=0){r=_r;i=_i;} 7     comp operator+(const comp x){
    return comp(r+x.r,i+x.i);} 8     comp operator-(const comp x){
    return comp(r-x.r,i-x.i);} 9     comp operator*(const comp x){
    return comp(r*x.r-i*x.i,r*x.i+i*x.r);}10 };11 const double pi=acos(-1.0);12 void FFT(comp a[],int n,int t){13     for(int i=1,j=0;i
       
        >=1,~j&s;);15             if(i
        
         < lenA? (a[i] == 'a'): 0, 0);63             y[i] = comp(i < lenB? (b[i] == 'a'): 0, 0);64         }65         FFT(x, len, 1);66         FFT(y, len, 1);67         for(int i = 0; i < len; i++)68             x[i] = x[i]*y[i];69         FFT(x, len, -1);70         for(int i = 0; i < len; i++)71             ans[i] = x[i].r+0.5;72 73         for(int i = 0; i < len; i++){74             x[i] = comp(i < lenA? (a[i] == 'b') : 0, 0);75             y[i] = comp(i < lenB? (b[i] == 'b') : 0, 0);76         }77         FFT(x, len, 1);78         FFT(y, len, 1);79         for(int i = 0; i < len; i++)80             x[i] = x[i]*y[i];81         FFT(x, len, -1);82         for(int i = 0; i < len; i++)83             ans[i] += x[i].r+0.5;84 85         initHash();86         set
         
           se;87         for(int i = lenB-1; i < lenA; i++)88             if(ans[i] >= lenB-K)89                 se.insert(askHash(i-lenB+1, i));90         printf("Case %d: %d\n", ca++, (int)se.size());91     }92     return 0;93 }
         
        
       
      

 

=================================分割线=================================== 

NTT

NTT与FFT类似，FFT用复数形式会有精度损失，而NTT则是在整数域内取模意义下，无精度损失。

 

如果 P = r⋅2^k +1 是个素数，G是模P下的一个原根，那么在mod P 意义下，可以处理 2^k 以内规模的数据 。

G在模P下的阶为 P-1，即 r⋅2^k 

那么G^r 在模P下的阶为2^k ，这里的 G^r  即等价于FFT里的w_n .

那么我们用模P下的卷积运算就不会产生精度损失。

P =   998244353 = 119*2²³+1, 能够处理2²³ = 8e6+ 规模的数据，原根为3.

P = 1004535809 = 479*2²¹+1, 能够处理2²¹ = 2e6+ 规模的数据，原根为3, 且 1004535809 加起来不会爆 int.

NTT能解决模数  P = r⋅2^k +1 的问题，那么如何解决模任意数呢？

先前的 NTT资料 里有提到，

 

即用多个小素数跑NTT，最后用中国剩余定理求出 n(m-1)² 内满足条件的唯一值，当 各个素数积 > n(m-1)² 时中国剩余定理后显然可取得唯一值。

 

=================================分割线===================================

 

C_k = ∑_{i⊕j=k (Ai*Bj)，}  ⊕是某种运算符号。当⊕是+时，即是傅里叶变换；当⊕是^, &, |等某种位运算时，即是FWT快速沃尔什变换。

FFT中，数组长度要大于结果的最高次幂，高位补0；FWT时，数组长度需要是2的整数次幂，不足补0。

原理不是怎么重要...

模板套用即可。

 

1 //快速沃尔什变换 2 void FWT(int*a,int n){ 3     for(int d=1;d
      
       <<=1)for(int m=d<<1,i=0;i
      

 防溢出可mod 1e9+7大质数，则除以2的时候乘2的逆元。

 

FWT后，相乘，UFWT回去即可。