魔数

Posted on Edited on In

题目大意：小林和亮亮是好朋友。小林有一个幸运数字 a，亮亮有一个幸运数字 b。一个数字称之为“幸运数”当且仅当它只由 a 和 b 组成。小林称一个数为“魔数”，当且仅当这个数各数位之和为“幸运数”，且这个数字本身也是“幸运数”。举个例子：小林的幸运数字为 2，亮亮的幸运数字为 6，那么 23 不是“幸运数”，而 26、222 是“幸运数”。进一步，222 是“魔数”（因为 2+2+2=6），而 26 不是“魔数”（因为 2+6=8）。亮亮想要知道，有多少个 n 位的“魔数”（一个 n 位数不包含前导 0），由于 这个数字会很大，所以亮亮只关心这个数模 1000000007（10^9+7，是一个质数）的结果。

数据范围：30%：n <= 5；60%：n<=100；100%；n<=1e6

上来其实我也不会，以为是个数位dp准备写完暴力分就拍拍屁股走人

后来发现暴力分数太少，不值得。。。

就准备想正解，先打了个表

然后发现n位数，只会产生n+1个有效数字

每一个有效数字从小到大排列的话，会发现每一个有效数字出现的次数恰好就是\(C_n^i\)

然后就做完了

其实逆元的话，最好线性求，用费马小定理的话还要带着一个log

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6 + 66, mod = 1e9 + 7;

inline int read()
{
    int s(0), w(1);
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void put(ll x)
{
    if (! x) putchar('0');
    if (x < 0) putchar('-'), x = -x;
    ll num(0); char c[66];
    while (x) c[++ num] = x % 10 + 48, x /= 10;
    while (num) putchar(c[num --]);
    return (void)(putchar('\n'));
}

ll res, fac[N], ifac[N], f[N];

inline ll ksm(ll a, ll b)
{
    ll ret = 1;
    for (; b; b >>= 1)
    {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
    }
    return ret;
}

inline ll C(ll n, ll m)
{
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

inline void pres_dou(int n)
{
    int i;
    fac[0] = 1;
    for (i = 1; i <= n; ++ i) fac[i] = fac[i - 1] * i % mod;
    ifac[n] = ksm(fac[n], mod - 2);
    for (i = n - 1; i >= 0; -- i) ifac[i] = ifac[i + 1] * (i + 1) % mod;
    
    // for (i = 0; i <= n; ++ i) ifac[i] = ksm(fac[i], mod - 2);
    for (i = 0; i <= n; ++ i) f[i] = C(n, i);
    return;
}

signed main()
{
    int i, a, b, n;
    a = read(), b = read(), n = read();
    pres_dou(n);
    for (i = 0; i <= n; ++ i)
    {
        int pd = 0, cnt = 0, fuck = b * i + a * (n - i);
        while (fuck)
        {
            int w = fuck % 10;
            fuck /= 10, ++ cnt;
            if (w == a || w == b) ++ pd;	
        }
        if (pd == cnt) res = (res % mod + f[i] % mod) % mod;
    }
    
    put(res);
    return 0;
}