注册 登录
编程论坛 C语言论坛

请求老师验证一下这个VC程序能不能运行?

ysr2857 发布于 2020-05-24 18:37, 1809 次点击
这是个快速数论变换程序就是NTT:
下面这个是定义
#define g 3//模数的原根
#define mod 998244353//通常情况下的模数

int pow(int x,int y)//快速幂
{
    ll z=1ll*x,ans=1ll;
    for (;y;y/=2,z=z*z%mod)if (y&1)ans=ans*z%mod;//注意精度
    return (int)ans%mod;
}

下面是NTT板子,由FFT稍改了几下就成了(原文是这么说的)
inline void ntt(int a[],int len,int inv)
{
    int bit=0;
    while ((1<<bit)<len)++bit;
    fo(i,0,len-1)
    {
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
        if (i<rev[i])swap(a[i],a[rev[i]]);
    }//前面和FFT一样
    for (int mid=1;mid<len;mid*=2)
    {
        int tmp=pow(g,(mod-1)/(mid*2));//原根代替单位根
        if (inv==-1)tmp=pow(tmp,mod-2);//逆变换则乘上逆元
        for (int i=0;i<len;i+=mid*2)
        {
            int omega=1;
            for (ll j=0;j<mid;++j,omega=omega*tmp%mod)
            {
                int x=a[i+j],y=omega*a[i+j+mid]%mod;
                a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;//注意取模
            }
        }//大体和FFT差不多
    }
}

请老师有空的时候看看,欢迎指点!谢谢您!
3 回复
#2
ysr28572020-05-24 18:41
据说NTT可以用于大整数的快速乘法除法运算,下面的话是原文的说明:
和FFT一样,NTT也只能处理n为2的次幂的多项式
NTT调用和FFT一模一样,注意 long long和除法都变成乘逆元
逆NTT变换后每一项系数乘上多项式长度的逆元即可

请问老师,NTT如何用于快速乘法除法运算呢?
#3
ysr28572020-06-06 12:38
顶一下,希望各位老师给与指导!谢谢您!
#4
ysr28572020-06-18 10:22
我不懂vc请求老师给予指导,谢谢!
1