T29741: 神经网络之国

卷积、快速幂，http://cs101.openjudge.cn/practice/29741/

852B. Neural Network country, dp, matrices, 2000, https://codeforces.com/problemset/problem/852/B

随着深度学习的兴起，许多国家也变得越来越像神经网络。这些“神经网络国家”被构建成了层级结构，每一层代表一个城市层，具有多个城市，并且整个国家从一个入口城市出发，最终到达一个出口城市。

现在，这个神经网络国家一共有 L 层，每层有 N 个城市。对于任意两个相邻的层 L_1 和 L_2，L_1 中的每个城市都与 L_2 中的每个城市相连。更具体地说，从 L_1 的任意城市出发到 L_2 中的第 j 个城市的代价为 c_j，而这个代价与 L_1 中的起点城市无关（即所有从 L_1 出发到 L_2 的边，指向同一目标城市的代价相同）。

整个国家的路径可以分为三段：

从入口点到第 1 层中的每个城市（共 N 个代价）。
各相邻层之间的连接代价（每一对相邻层之间有 N 个代价）。
从第 L 层中的每个城市到出口点的代价（N 个代价）。

Doctor P. 现在需要你帮助他计算，有多少条从入口到出口的路径，其总代价可以被给定的整数 M 整除。

你只需输出这样的路径条数，结果对 10^9 + 7 取模。

样例图示：

输入

输入共四行。

- 第一行包含三个整数 N, L, M，分别表示每层的城市数量、层数，以及所需整除的代价模数。 - 第二行包含 N 个整数，表示从入口点到第 1 层每个城市的代价。 - 第三行包含 N 个整数，表示任意相邻层之间的代价数组 c_1, c_2, ..., c_N，其中 c_j 表示连接至每层中第 j 个城市的代价。 - 第四行包含 N 个整数，表示从第 L 层的每个城市到出口的代价。

1 <= N <= 10^6

2 <= L <= 10^5

2 <= M <= 100

0 <= cost <= M

输出

输出一个整数，表示从入口到出口总代价可以被 M 整除的路径条数，结果对 10^9 + 7 取模。

样例输入

样例输出

提示

动态规划

该国家结构如下，共有 3 层，每层有 2 个城市：

- 入口到第一层城市的代价分别为 4 和 6。 - 每对相邻层之间，连接至第一个城市的代价为 2，至第二个城市的代价为 1。 - 最后一层到出口的代价分别为 3 和 4。

共计有 N^L = 2^3 = 8 条路径。仅有两条路径的总代价可被 13 整除。

来源

TA-xjk

python

MOD = 10**9 + 7

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it)); L = int(next(it)); M_val = int(next(it))
    start = [int(next(it)) for _ in range(N)]
    mid = [int(next(it)) for _ in range(N)]
    end = [int(next(it)) for _ in range(N)]
    
    M = M_val
    
    # Precompute start_mod
    start_mod = [0] * M
    for x in start:
        start_mod[x % M] += 1
    
    # Precompute mid_mod
    mid_mod = [0] * M
    for x in mid:
        mid_mod[x % M] += 1
    
    # Precompute last_cost = mid + end
    last_mod = [0] * M
    for i in range(N):
        cost = (mid[i] + end[i]) % M
        last_mod[cost] += 1

    # Convolution function
    def convolve(a, b):
        res = [0] * M
        for i in range(M):
            if a[i]:
                ai = a[i]
                for j in range(M):
                    if b[j]:
                        res[(i + j) % M] = (res[(i + j) % M] + ai * b[j]) % MOD
        return res

    # Identity kernel
    identity = [0] * M
    identity[0] = 1

    if L == 2:
        cur = start_mod[:]
    else:
        # Compute mid_mod^(L-2) under convolution
        def power_conv(base, exp):
            result = identity[:]
            base = base[:]
            while exp:
                if exp & 1:
                    result = convolve(result, base)
                base = convolve(base, base)
                exp //= 2
            return result
        
        mid_power = power_conv(mid_mod, L - 2)
        cur = convolve(start_mod, mid_power)
    
    # Now combine with last_mod
    ans = 0
    for r in range(M):
        needed = (M - r) % M
        ans = (ans + cur[r] * last_mod[needed]) % MOD
    
    print(ans)

if __name__ == '__main__':
    main()

python

import sys

# 设置模数
MOD = 10**9 + 7

# 一次性读取所有输入数据，处理速度比 input() 快
data = list(map(int, sys.stdin.read().split()))
idx = 0

# 读取 N, L, M
N = data[idx]; idx += 1
L = data[idx]; idx += 1
M = data[idx]; idx += 1

# 读取三段代价数组
# sta: 入口 -> 第1层
sta = data[idx:idx+N]; idx += N
# mid: 层与层之间 (第i层 -> 第i+1层)
mid = data[idx:idx+N]; idx += N
# end: 第L层 -> 出口
end = data[idx:idx+N]

def convolution(a, b, m):
    """
    循环卷积函数
    输入: 两个长度为 m 的数组 a, b，分别代表两个阶段的余数频数分布
    输出: 卷积后的新分布数组 c
    含义: 如果阶段1余数为i，阶段2余数为j，则总余数为 (i+j)%m
    """
    c = [0] * m
    for i in range(m):
        for j in range(m):
            # 核心状态转移方程：
            # 新余数 = (i + j) % m
            # 路径数 = 方案a的数量 * 方案b的数量
            c[(i + j) % m] = (c[(i + j) % m] + a[i] * b[j]) % MOD
    return c

def fast_power(f, t, m):
    """
    基于卷积的快速幂
    计算分布 f 自身卷积 t 次的结果
    """
    # 初始化“单位元”数组
    # 在加法卷积中，单位元是 [1, 0, 0, ..., 0]
    # 代表“增加的代价为0”这一种情况，不改变原有的余数分布
    re = [0] * m
    re[0] = 1
    
    while t > 0:
        if t & 1 == 1:
            re = convolution(re, f, m)
        f = convolution(f, f, m)
        t >>= 1
    return re

# --- 1. 预处理各阶段的余数分布 ---

# m_sta: 入口到第一层的余数分布
m_sta = [0] * M
for i in sta:
    m_sta[i % M] = (m_sta[i % M] + 1) % MOD

# m_mid: 层间转移的余数分布 (用于快速幂)
m_mid = [0] * M
for i in mid:
    m_mid[i % M] = (m_mid[i % M] + 1) % MOD

# m_end: 最后一层到出口的余数分布
# 注意：这里做了一个巧妙的合并
# 把 "L-1层 -> L层 (代价mid)" 和 "L层 -> 出口 (代价end)" 
# 合并成一步处理：mid[i] + end[i]
m_end = [0] * M
for i in range(N):
    # 路径：L-1层任意点 -> L层第i个点 -> 出口
    total_cost = (mid[i] + end[i]) % M
    m_end[total_cost] = (m_end[total_cost] + 1) % MOD

# --- 2. 计算过程 ---

# 中间层一共要走 L-1 次转移。
# 其中最后一次转移 (L-1 -> L) 我们已经合并到了 m_end 中。
# 所以中间纯粹的层间转移还需要走 (L-1) - 1 = L-2 次。
if L > 2:
    m_mid = fast_power(m_mid, L - 2, M)
else:
    # 特殊情况：如果 L=2，中间不需要走纯层间转移，
    # 快速幂次数为0，fast_power返回单位元，不影响结果
    m_mid = fast_power(m_mid, 0, M)

# --- 3. 合并所有阶段 ---

# 第一步：入口分布 * 中间层分布
ans = convolution(m_sta, m_mid, M)

# 第二步：结果 * (最后一层+出口)的分布
ans = convolution(ans, m_end, M)

# --- 4. 输出结果 ---
# ans[0] 表示总代价模 M 余数为 0 的路径条数
print(ans[0])

T29741: 神经网络之国 ​

T29741: 神经网络之国