题目分析

题意理解

我们有一个有向图，需要计算所有可能的旅行方案的个数，其中：

• 每次旅行：任意起点 → 走至少1步 → 任意终点
• 愉悦值 = 起点编号 & 终点编号（按位与）
• 总步数 = x，所有旅行愉悦值的按位与 = y
• 求所有 x∈[1,m], y∈[0,n) 的方案数异或和

关键难点

1. 多个旅行：可以分成多次旅行，每次独立
2. 按位与约束：所有旅行的愉悦值按位与等于 y
3. 组合爆炸：需要高效计算所有可能的分配方式

算法思路

核心思想：生成函数与容斥

1. 基本计数

定义 f[t][i][j] = 从 i 出发走 t 步到 j 的方案数 这可以通过矩阵幂的思想计算。

2. 愉悦值处理

定义 w[t][y] = 走 t 步且愉悦值 = y 的方案数 其中愉悦值 = 起点 & 终点

3. 关键转化：按位与的容斥

对于"所有旅行的愉悦值按位与 = y"这个条件，使用莫比乌斯反演（FWT）：

• 设 F[y] = 所有旅行的愉悦值都包含 y 的方案数
• 设 G[y] = 所有旅行的愉悦值按位与恰好等于 y 的方案数

通过 FWT 可以在两者间转换。

4. 生成函数方法

对于总步数 x 分成若干次旅行，使用生成函数：

• 设 H_y(z) = ∑_{x≥1} 走 x 步且所有旅行愉悦值按位与 = y 的方案数 · z^x
• 通过容斥原理计算

算法步骤详解

代码详解

#include <bits/stdc++.h>
using lint = long long;
using u32 = unsigned;
using u64 = unsigned long long;

const int N = 64, M = 20007, T = M * 8;
const u32 mod = 998244353, P = 1313131, G = 3;

int n, m, mat[N][N];
u32 ans;
u32 f[N * 2][N][N], A[N * 2], w[M][N];
u32 a[N];
std::mt19937 rd(251); // 随机数生成器
u32 t1[T], t2[T];

// 模运算工具函数
inline u32 add(u32 x, u32 y) { return x += y - mod, x += mod & -(x >> 31), x; }
inline u32 cut(u32 x, u32 y) { return x -= y, x += mod & -(x >> 31), x; }
inline u32 mul(u32 x, u32 y) { return u64(x) * y % mod; }
inline u32 pow(u32 a, int n) {
    u32 r(1);
    while (n) {
        if (n & 1) r = mul(r, a);
        a = mul(a, a), n >>= 1;
    }
    return r;
}

// 快速数论变换 (NTT)
int r[T], mem_n;
inline void terp(int n) {
    if (mem_n == n) return;
    for (int i = 1; i < n; ++i) {
        r[i] = r[i >> 1] >> 1;
        if (i & 1) r[i] |= (n >> 1);
    }
}

inline void NTT(u32 *f, int n, int b) {
    terp(n);
    static u64 w1[T], w2[T];
    
    for (int i = 0; i < n; ++i) w1[i] = f[r[i]];
    w2[0] = 1;
    
    for (int i = 1; i < n; i <<= 1) {
        u64 w = pow(b ? G : ivG, (mod - 1) / (i + i));
        for (int j = 1; j < i; ++j) w2[j] = mul(w2[j - 1], w);
        
        for (int j = 0; j < n; j += i + i)
            for (int k = 0; k < i; ++k) {
                u64 t = w1[i | j | k] * w2[k] % mod;
                w1[i | j | k] = w1[j | k] + mod - t;
                w1[j | k] += t;
            }
    }
    
    if (b)
        for (int i = 0; i < n; ++i) f[i] = w1[i] % mod;
    else {
        u32 iv = inv(n);
        for (int i = 0; i < n; ++i) f[i] = mul(w1[i] % mod, iv);
    }
}

// 快速沃尔什变换 (FWT) - 用于按位与卷积
inline void FWT(u32 *f, int n, int b) {
    for (int i = 1; i < n; i <<= 1)
        for (int j = 0; j < n; j += i + i)
            for (int k = 0; k < i; ++k) {
                if (b) addt(f[j | k], f[i | j | k]);  // 正变换
                else cutt(f[j | k], f[i | j | k]);    // 逆变换
            }
}

int main() {
    scanf("%d%d", &n, &m);
    
    // 读入邻接矩阵
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &mat[i][j]);
    
    // 步骤1: 计算f[t][i][j] - 从i走t步到j的方案数
    for (int i = 0; i < n; ++i) {
        f[0][i][i] = 1;  // 0步：只能停留在自身
        
        for (int k = 1; k < 2 * n; ++k)
            for (int j = 0; j < n; ++j)
                for (int x = 0; x < n; ++x)
                    f[k][i][j] = add(f[k][i][j], mul(f[k - 1][i][x], mat[x][j]));
    }
    
    // 步骤2: 计算w[t][y] - 走t步且愉悦值(起点&终点)=y的方案数
    for (int t = 0; t < 2 * n; ++t)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                addt(w[t][i & j], f[t][i][j]);
    
    // 步骤3: 使用随机向量进行线性递推的Berlekamp-Massey算法
    for (int i = 0; i < n; ++i) a[i] = rd() % mod;
    
    for (int t = 0; t < 2 * n; ++t) {
        for (int i = 0; i < n; ++i)
            addt(A[t], mul(a[i], w[t][i]));
    }
    
    // Berlekamp-Massey算法求线性递推式
    std::vector<u32> f, last;
    int k = -1;
    u32 d = 0;
    
    for (int i = 0; i < 2 * n; ++i) {
        u32 nw = 0;
        
        // 用当前的递推式预测A[i]
        for (int j = 0; j < f.size(); ++j)
            addt(nw, mul(A[i - j - 1], f[j]));
        
        if (nw == A[i]) continue;  // 预测正确
        
        if (k == -1) {
            // 第一次发现错误，初始化递推式
            k = i, d = cut(A[i], nw);
            f = std::vector<u32>(i + 1);
        } else {
            // 更新递推式
            std::vector<u32> c = f;
            u32 w = div(cut(A[i], nw), d);
            
            if (f.size() < last.size() + i - k)
                f.resize(last.size() + i - k);
            
            addt(f[i - k - 1], w);
            
            for (int j = 0; j < last.size(); ++j)
                cutt(f[i - k + j], mul(last[j], w));
            
            if ((int)c.size() - i < (int)last.size() - k)
                k = i, d = cut(A[i], nw), last = c;
        }
    }
    
    // 步骤4: 使用递推式计算w[t][i] (t > 2n)
    for (int t = 2 * n; t <= m; ++t)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < f.size(); ++j)
                addt(w[t][i], mul(w[t - j - 1][i], f[j]));
    
    // 步骤5: FWT容斥计算"按位与恰好等于y"的方案数
    for (int i = 1; i <= m; ++i)
        FWT(w[i], n, 1);  // 正变换：计算包含关系
    
    for (int i = 0; i < n; ++i) {
        // 生成函数求逆：计算恰好等于的方案数
        for (int j = 1; j <= m; ++j)
            t1[j] = cut(0, w[j][i]);
        t1[0] = 1;
        
        invp(t1, t2, m + 1);  // 多项式求逆
        
        for (int j = 1; j <= m; ++j)
            w[j][i] = t2[j];
    }
    
    // 步骤6: FWT逆变换得到最终答案
    for (int i = 1; i <= m; ++i) {
        FWT(w[i], n, 0);  // 逆变换：得到恰好等于
        
        for (int j = 0; j < n; ++j)
            ans ^= w[i][j];  // 计算异或和
    }
    
    printf("%u\n", ans);
    return 0;
}

算法核心要点详解

1. 线性递推发现 (Berlekamp-Massey)

• 通过前 2n 项发现 w[t][*] 满足的线性递推关系
• 利用随机向量压缩维度，避免 O(n³) 的复杂度
• 找到递推式后可以快速计算 w[t][i] (t > 2n)

2. 生成函数与容斥原理

对于固定 y，设：

• F(z) = ∑_{x≥1} w[x][y] · z^x
• 则答案的生成函数为 1/(1 - F(z)) - 1

这是因为：

• 1/(1 - F(z)) 表示可以分成任意次旅行（包括0次）
• 减去1表示至少一次旅行

3. FWT容斥原理

对于"按位与恰好等于y"的条件：

• 设 F[y] = 所有旅行愉悦值都包含y的方案数
• 设 G[y] = 所有旅行愉悦值按位与恰好等于y的方案数

则有：F[y] = ∑_{y⊆x} G[x] 通过FWT逆变换：G = FWT⁻¹(F)

4. 复杂度优化

• BM算法：O(n²) 发现递推式
• 递推计算：O(n²m) 计算所有w[t][i]
• FWT：O(nm log n) 容斥计算
• 总体复杂度可以接受 n=64, m=20000 的数据

总结

这道题综合运用了：

1. 线性递推 (Berlekamp-Massey)
2. 生成函数 处理组合计数
3. 快速沃尔什变换 处理按位与约束
4. 多项式求逆 计算生成函数
5. 动态规划 计算路径方案数

是一个很好的综合题目，考察了生成函数、容斥原理、线性递推等多个重要算法思想。