3

我在实施 NTT 时遇到了困难。在阅读了来自http://www.apfloat.org/ntt.html、http://codeforces.com/blog/entry/43499和其他一些关于 FFT 和 NTT 的大量教程后，我利用 Fermats 理论实现了NTT在选择模素数时。但我仍然认为我错过了一些东西，因为 invNTT(NNT(a)) 没有以'a'的形式出现。

请看看我的实现。

public static long[] invNTT(long[] a){
    long[] ans = NTT(a,true);
    for(int i=0;i<a.length;i++)
        ans[i] = ans[i]/(a.length);
    return ans;
}

public static long modPow(long a,long n,long mod){
    if(n==1)
        return a;
    if(n==0)
        return 1;
    long tempRes = modPow(a,n/2,mod);
    tempRes = (tempRes*tempRes)%mod;
    if(n%2==1)
        tempRes = (tempRes*a)%mod;
    return tempRes;
}


public static long[] NTT(long[] a, boolean inverse){
    if(a.length==1)
        return a;
    int len = a.length, k = len/2;
    long p = (long)Math.pow(2, k)+1;
    print(a);
    System.out.println("p="+p);
    long even[] = new long[k];
    long odd[] = new long[k];
    for(int i=0,j=0;i<k;i++){
        even[i]=a[j++];
        odd[i]=a[j++];
    }
    long[] evenNTT = NTT(even,inverse);
    long[] oddNTT = NTT(odd,inverse);
    long res[] = new long[len];
    for(int i=0;i<k;i++){
        long root1 = inverse?modPowNeg(p,modPow(2,i,p))[2]:modPow(2,i,p);
        long root2 = inverse?modPowNeg(p,modPow(2,i+k,p))[2]:modPow(2,i+k,p);
        System.out.println(i+" and "+(i+k)+" th roots "+root1+" "+root2);
        res[i] = evenNTT[i]+(root1*oddNTT[i]);
        res[k+i] = evenNTT[i]+(root2*oddNTT[i]);
    }
    print(res);
    return res;
}

public static void print(long a[]){
    for(int i=0;i<a.length;i++)
        System.out.print(a[i]+" ");
    System.out.println();
}

}
4

0 回答 0