题解：P9006 [入门赛 #9] 神树大人挥动魔杖 (Hard Version)

Ag2WO4 · 2025-02-11 16:11:19 · 题解

发现其他题解都用了比较复杂的方法，这里就上一个极其简单（甚至复杂度更低）的做法吧：

核心思路：快速幂取余

考虑到整个数组每 100000007\times k 次相加就会清零，于是快速幂取余计算前 10^n 个数中最后有多少个数不能被抵消，再将这些数分成 k 的商数和余数即可。最后和前 10^{n-1} 个数的结果简单在模数下相减就可以了。优秀的 O(k+\log n) 复杂度甚至让 Python 的代码成功挤进了本人撰文时最优解的第一页，而 C/C++ 代码更在最优解最前列。

代码

Python 代码相对简单：

n,k=map(int,input().split());p=pow(10,n,k*100000007)//k;p=[p]*k;q=pow(10,n-1,k*100000007)//k;q=[q]*k#快速幂取余后的商数
for i in range(pow(10,n,k*100000007)%k):p[i]+=1#快速幂取余后的余数
for i in range(pow(10,n-1,k*100000007)%k):q[i]+=1
print(*((p[i]-q[i])%100000007 for i in range(k)))#相减

C/C++ 小心模 100000007\times k 的快速幂取余是会爆 long long 的，这里使用 __int128 解决。

#include<stdio.h>
#define t 100000007
__int128 m[13],n,k,i,u,v,p;
int main()
{
    scanf("%d%d",&n,&k);
    u=v=1;m[0]=10;
    for(i=0;i<12;)m[++i]=(m[i]*m[i])%(k*t);
    for(i=0;i<13;i++)if(n&(1<<i))u=u*m[i]%(k*t);
    n--;
    for(i=0;i<13;i++)if(n&(1<<i))v=v*m[i]%(k*t);
    p=u/k-v/k;u%=k;v%=k;
    while(p<t)p+=t;
    i=0;printf("%d",(p+(i<u)-(i<v))%t);
    for(i=1;i<k;i++)printf(" %d",(p+(i<u)-(i<v))%t);
}