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

· · 题解

upd 2025.2.22：修改了格式

1. 纯暴力（只过样例，0pts）：

#include<bits/stdc++.h>
#define fast_gets ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int ans[1005];
int main(){
   fast_gets
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=9*pow(10,n-1);i++){
        for(int j=0;j<k;j++){
            if(i%k==j) ans[j]++;
        }
    }
    for(int i=0;i<k;i++) cout<<ans[i]<<' ';
   return 0;
}

代码就不解释了。

2. 差分（100pts）：

思路：

精灵的个数为 9\times 10^{n-1} 可写为 10^{n}-10^{n-1}。

同理可设有一个函数 f(n, k, i)，表示从 1 到 10^n - 1 之间所有数中模 k 余数为 i 的数的个数。那么，题目中的表达可以用以下的形式表示：

f(n, k, i) - f(n-1, k, i)

其中：

这个表达式表示的是在从 1 到 10^n - 1 之间的数中，模 k 余数为 i 的数的个数与从 1 到 10^{n-1} - 1 之间的数中，模 k 余数为 i 的数的个数之差。

每一组精灵至少有 \left \lfloor \frac{9\times 10^{n-1}}{k} \right \rfloor 个精灵，剩余 a \bmod k 个分别分到了 1 至 a \bmod k 组中。

AC 代码（纯净版）：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define fast_gets ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e6+5,MOD=1e8+7;
int cnt[N];
ll f(ll a,ll b,ll c){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ans;
}
int main(){
    fast_gets
    int n,k;
    cin>>n>>k;
    ll maxn=(f(10,n-1,k)-1+k)%k;
    ll p=(f(10,n-1,MOD)-1-maxn+MOD)*f(k,MOD-2,MOD)%MOD;
    for(int i=0;i<k;i++){
        cnt[i]=-p;
        if(i>0&&i<=maxn) cnt[i]--;
    } 
    maxn=(f(10,n,k)-1+k)%k;
    p=(f(10,n,MOD)-1-maxn+MOD)*f(k,MOD-2,MOD)%MOD;
    for(int i=0;i<k;i++){
        cnt[i]+=p;
        if(i>0&&i<=maxn) cnt[i]++;
        cnt[i]=(cnt[i]+MOD)%MOD;
        cout<<cnt[i]<<' ';
    }
    return 0;
}