数字权重-题解

查看原题

一道非常简单的数论题

为什么说它非常简单呢？
可能大家刚开始看到那个式子会有点懵，但是如果你把求和函数展开就会发现，式子会变为

a[n] - a[n-1] + a[n-1] - a[n-2] + … +a[2] - a[1]

然后你就会发现这个求和函数的值只与an与a1的值有关……

于是这个题一下就简单很多了。

那么，具体该怎么做呢？

首先，既然这个式子的值与a[n]与a[1]的差有关，由于k的范围只能为 -9 ~ 8 ，我们完全可以打一张表出来（其实等表打出来了，规律也就一目了然了）。至于剩下的 n - 2 位，它们的值可以是 0 ~ 9 之间的任何一个数字。于是中间每多一位，就会使ans * 10。 附一下代码：

#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;
long long ksm(long long  x,long long y,long long  mod) //快速幂，不会的自己去百度
{
    long long ans = 1;
    while(y > 0)
    {
        if(y & 1) ans = (ans * x) % mod;
        x = (x * x) % mod;
        y = y >> 1;
    }
    return ans % mod;
}
int main()
{
    long long  mod = 1000000007, n, k, ans;
    cin >> n >> k;
    long long a = 9 - abs(k);
    if(k < 0) a++;
    if(k >= 9 || k < -9)  //特判，k在此情况下方案数一定为0
    {
        cout <<0<< endl;
        return 0;
    }
    cout << (a * ksm(10, n - 2, mod)) % mod << endl;
    return 0;
}