解析快速数论变换

核心结论：这段代码是无注释、极简压缩版的快速数论变换（NTT），用于多项式乘法 / 卷积，是信息学竞赛常用的高效算法。

1. 关键参数解析

int m=754974721;  // 模数：NTT常用质数，原根=3
int t[1<<22];     // 数组大小：4194304（2^22），存储变换数据
e=1<<22;          // 最大长度 2^22

• 模数 754974721 是 NTT 标准模数，满足 754974721 = 119×2²³ + 1，支持最大长度为 2²³ 的变换
• 函数 f(d) 是 NTT 核心函数：d=3 为正变换，d=逆元 为逆变换

2. 代码功能完整还原（标准 NTT）

把压缩代码还原为可读版：

const int MOD = 754974721; // 模数
const int MAXN = 1 << 22;  // 数组最大长度
int t[MAXN];               // 数据数组
int N;                     // 实际变换长度（必须是2的幂）

// NTT核心函数
// d=3：正向NTT   d=逆元：逆向NTT
void ntt(int d) {
    // 蝴蝶操作（NTT核心迭代实现）
    for (int s = 1 << 23; s > 0; s /= 2) {
        d = 1LL * d * d % MOD;
        if (s < N) {
            for (int *p = t; p < t + N; p += s) {
                int c = 1;
                for (int i = s; i > 0; --i) {
                    // 蝴蝶计算
                    long long b = (*p + p[s]) % MOD;
                    p[s] = (MOD + *p - p[s]) % MOD * c % MOD;
                    *p = b % MOD;
                    p++;
                    c = 1LL * c * d % MOD;
                }
            }
        }
    }

    // 位逆序置换（二进制翻转）
    int j = 0;
    for (int i = 0; i < N - 1; ++i) {
        for (int s = N / 2; !( (j ^= s) & s ); s /= 2);
        if (i < j) {
            // 交换数组元素
            int a = t[i];
            t[i] = t[j];
            t[j] = a;
        }
    }
}

3. 运行结果说明

重要前提

这段代码单独运行没有任何输出！

• 它只是定义了 NTT 函数和全局变量
• 必须手动赋值数组 t、设置长度 N、调用函数 才有结果

调用示例（完整可运行）

#include 
int m=754974721,N,t[1<<22],a,*p,i,e=1<<22,j,s,b,c,U;
f(int d){
  for(s=1<<23;s;s/=2,d=d*1LL*d%m)
    if(s

10 754974719 754974717 4