题目分析

本题要求计算在 $N$ 步操作后，$M$ 位数码管显示每个可能数字的方案数。约束条件是：每 $K$ 步后必须显示合法数字。

关键观察

$1$. 五段数码管编码：

用 $5$ 位二进制表示一个数码管的状态（$a$-$e$ 段）。题目给出的 p[10] 数组就是数字 $0$-$9$ 的二进制编码。

$2$. 操作性质：

每次操作翻转一段（点亮→熄灭或熄灭→点亮），相当于对当前状态进行按位异或操作。

$3$. 约束转化：

每 $K$ 步后必须是合法数字。 可以把 $N$ 步分成 $\lfloor N/K \rfloor$ 个完整 $K$ 步块，最后剩余 $N$ 步。

每个 $K$ 步块：从合法数字 $x$ 到合法数字 $y$

最后剩余步：从合法数字 $x$ 到合法数字 $y$

$4$. 转移计算：

设 $F_t[mask]$ 表示经过 $t$ 步操作，从某个初始状态通过异或变成 $mask$ 的方案数。 由于异或操作的可交换性，$F_t$ 可以通过集合幂快速幂（xor卷积）快速计算。

算法步骤

$1$. 预处理 $K$ 步转移：

令 $C[mask] = 1$ 当 $mask$ 只有 $1$ 位为 $1$（即单段操作）。

计算 $F_K = C^K$（xor卷积幂）。

这样 $F_K[x \oplus y]$ 表示从状态 $x$ 到 $y$ 走 $K$ 步的方案数。

$2$. 构建合法数字间的转移矩阵：

对于 $M=1$：从 $F_K$ 提取 $10 \times 10$ 矩阵 $c$，其中 $c[i][j] = F_K[p[i] \oplus p[j]]$。 对于 $M=2$：两位数字组合成 $100$ 个状态，类似构建 $100 \times 100$ 矩阵。

$3$. 计算完整 $K$ 步块的转移：

需要计算 $c^{\lfloor N/K \rfloor}$，用矩阵快速幂。

$4$. 计算剩余步的转移：

类似步骤 $1$，计算 F_{N % K} = C^{N % K}。

$5$. 合并结果：

设完整块后的状态分布为 $d$，则最终到状态 $j$ 的方案数为：

时间复杂度

$M=1$：矩阵大小 $10$，集合大小 $32$，可过 $N \leq 10^{15}$。

$M=2$：矩阵大小 $100$，集合大小 $1024$，利用xor卷积优化，可过 $N \leq 10^{15}$。

关键技巧

• 用xor卷积（沃尔什变换）加速 $C^t$ 的计算，从 $O(2^{5M} \cdot t)$ 降到 $O(2^{5M} \cdot \log t)$。

• 只关注合法数字间的转移，大幅减少矩阵大小（$10^M$ vs $2^{5M}$）。

• 分离完整 $K$ 步块和剩余步，分别用矩阵快速幂和xor卷积快速幂计算。

总结

本题核心是将数码管状态用二进制编码，利用异或操作的性质，通过集合幂快速幂和矩阵快速幂结合，高效计算大规模步数下的转移方案数。

AC代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define md 1000000007
#define N 1100
#define M 110

int p[10] = {10, 2, 9, 7, 18, 21, 12, 3, 29, 23};
int vi[N];
ll d[M], ans[M];
ll f[M][M], g[M][M], c[M][M];
ll F[N], G[N], C[N];

// 矩阵快速幂: f = c^x (mod md), n为矩阵大小
void ksm(ll x, int n) {
    if (!x) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                f[i][j] = (i == j);
    } else {
        ksm(x / 2, n);
        // g = f * f
        memset(g, 0, sizeof(g));
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++)
                if (f[i][k])
                    for (int j = 0; j < n; j++)
                        g[i][j] = (g[i][j] + f[i][k] * f[k][j]) % md;
        memcpy(f, g, sizeof(f));
        
        if (x % 2) {
            // f = c * f
            memset(g, 0, sizeof(g));
            for (int i = 0; i < n; i++)
                for (int k = 0; k < n; k++)
                    if (c[i][k])
                        for (int j = 0; j < n; j++)
                            g[i][j] = (g[i][j] + c[i][k] * f[k][j]) % md;
            memcpy(f, g, sizeof(f));
        }
    }
}

// 集合幂快速幂: F = C^x (xor卷积), n为集合大小(2^5或2^10)
void Ksm(ll x, int n) {
    if (!x) {
        memset(F, 0, sizeof(F));
        F[0] = 1;
    } else {
        Ksm(x / 2, n);
        // G = F xor F
        memset(G, 0, sizeof(G));
        for (int i = 0; i < n; i++)
            if (F[i])
                for (int j = 0; j < n; j++)
                    G[i ^ j] = (G[i ^ j] + F[i] * F[j]) % md;
        memcpy(F, G, sizeof(F));
        
        if (x % 2) {
            // F = C xor F
            memset(G, 0, sizeof(G));
            for (int i = 0; i < n; i++)
                if (C[i])
                    for (int j = 0; j < n; j++)
                        G[i ^ j] = (G[i ^ j] + C[i] * F[j]) % md;
            memcpy(F, G, sizeof(F));
        }
    }
}

int main() {
    ll n, K;
    int m, X;
    scanf("%d%lld%lld%d", &m, &n, &K, &X);
    
    if (m == 1) {
        // 一位数码管
        for (int i = 0; i < 5; i++)
            C[1 << i] = 1;
        Ksm(K, 32); // 计算K步的xor卷积转移
        
        memset(vi, -1, sizeof(vi));
        for (int i = 0; i < 10; i++)
            vi[p[i]] = i;
        
        // 从xor卷积得到数字间转移矩阵c[10][10]
        memset(c, 0, sizeof(c));
        for (int i = 0; i < 32; i++)
            if (vi[i] >= 0)
                for (int j = 0; j < 32; j++)
                    if (vi[j] >= 0)
                        c[vi[i]][vi[j]] = F[i ^ j];
        
        // 矩阵快速幂: 计算(n/K)个完整K步的转移
        ksm(n / K, 10);
        
        // 初始状态X经过(n/K)*K步后的分布
        for (int i = 0; i < 10; i++)
            d[i] = f[X][i];
        
        // 计算剩余n%K步的xor卷积
        Ksm(n % K, 32);
        
        // 合并最后剩余步数的转移
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++)
                if (F[p[i] ^ p[j]])
                    ans[j] = (ans[j] + d[i] * F[p[i] ^ p[j]]) % md;
        
        for (int i = 0; i < 10; i++)
            printf("%lld\n", ans[i]);
    } else {
        // 两位数码管
        for (int i = 0; i < 10; i++)
            C[1 << i] = 1;
        Ksm(K, 1024); // 2^10=1024
        
        memset(vi, -1, sizeof(vi));
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++)
                vi[p[i] * 32 + p[j]] = i * 10 + j;
        
        // 构建100*100的转移矩阵
        memset(c, 0, sizeof(c));
        for (int i = 0; i < 1024; i++)
            if (vi[i] >= 0)
                for (int j = 0; j < 1024; j++)
                    if (vi[j] >= 0)
                        c[vi[i]][vi[j]] = F[i ^ j];
        
        // 矩阵快速幂
        ksm(n / K, 100);
        
        for (int i = 0; i < 100; i++)
            d[i] = f[X][i];
        
        // 剩余步数
        Ksm(n % K, 1024);
        
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < 100; i++)
            for (int j = 0; j < 100; j++) {
                int from = (p[i / 10] * 32 + p[i % 10]);
                int to = (p[j / 10] * 32 + p[j % 10]);
                if (F[from ^ to])
                    ans[j] = (ans[j] + d[i] * F[from ^ to]) % md;
            }
        
        for (int i = 0; i < 100; i++)
            printf("%lld\n", ans[i]);
    }
    return 0;
}