题意分析

题目要求计算杨辉三角第$n$行的数字拼接成的$k$位补零数字$p$对$m$取模的结果。由于直接拼接数字会导致数值过大，需要通过数学方法简化计算。

解题思路

1. 数学转化：将每个数字视为$10^k$进制的一位，则$p$可以表示为$(10^k + 1)^n$在$10^k$进制下的形式。
2. 模运算性质：利用$(a \cdot b) \mod m = [(a \mod m) \cdot (b \mod m)] \mod m$的性质，避免大数计算。
3. 快速幂算法：高效计算$(10^k + 1)^n \mod m$的值。

实现步骤

1. 输入处理：读取测试用例数量$T$，然后逐个处理每个用例的$n$、$k$、$m$。
2. 快速幂计算：
   • 计算$10^k \mod m$
   • 计算$(10^k \mod m + 1) \mod m$
   • 计算$(10^k + 1)^n \mod m$
3. 输出结果：直接输出快速幂计算结果。

C++实现

#include <iostream>
#include <stdio.h>
using namespace std;
#define LL long long

// 快速幂函数：计算a^k mod m
LL qm(LL a, LL k, LL m) {
    LL re = 1, y = a % m;
    for(; k; k >>= 1, y = y * y % m) 
        if(k & 1ll) re = y * re % m;
    return re;
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        LL n, k, m;
        scanf("%lld%lld%lld", &n, &k, &m);
        // 计算(10^k + 1)^n mod m
        LL base = qm(10, k, m) + 1;
        printf("%lld\n", qm(base % m, n, m));
    }
    return 0;
}

代码说明

1. 快速幂函数qm：

   • 参数：底数$a$，指数$k$，模数$m$
   • 功能：高效计算$a^k \mod m$
   • 原理：通过二进制分解指数，将时间复杂度从$O(k)$降为$O(\log k)$

2. 主函数逻辑：

   • 读取测试用例数$t$
   • 对每个测试用例：
     • 读取$n$、$k$、$m$
     • 计算$10^k \mod m$
     • 计算$(10^k + 1) \mod m$
     • 计算$(10^k + 1)^n \mod m$并输出

3. 优化处理：

   • 所有中间结果都及时取模，防止溢出
   • 使用位运算加速幂运算
   • 采用快速输入输出处理大规模数据