洛谷P2481 [SDOI2010] 代码拍卖会题解

题目链接：P2481 [SDOI2010] 代码拍卖会

题意：

随着 iPig 在 P++ 语言上的造诣日益提升，他形成了自己一套完整的代码库。猪王国想参加 POI 的童鞋们都争先恐后问 iPig 索要代码库。iPig 不想把代码库给所有想要的小猪，只想给其中的一部分既关系好又肯出钱的小猪，于是他决定举行了一个超大型拍卖会。

在拍卖会上，所有的 $N$ 头小猪将会按照和 iPig 的好感度从低到高，从左到右地在 iPig 面前站成一排。每个小猪身上都有 $9$ 猪币（与人民币汇率不明），从最左边开始，每个小猪依次举起一块牌子，上面写上想付出的买代码库的猪币数量（$1$ 到 $9$ 之间的一个整数）。大家都知道，如果自己付的钱比左边的猪少，肯定得不到梦寐以求的代码库，因此从第二只起，每只猪出的钱都大于等于左边猪出的价钱。最终出的钱最多的小猪（们）会得到 iPig 的代码库真传，向着保送 PKU（Pig Kingdom University）的梦想前进。

iPig 对自己想到的这个点子感到十分满意，在去现场的路上，iPig 就在想象拍卖会上会出现的场景，例如一共会出现多少种出价情况之类的问题，但这些问题都太简单了，iPig 早已不感兴趣了，他想要去研究更加困难的问题。iPig 发现如果他从台上往下看，所有小猪举的牌子从左到右将会正好构成一个 $N$ 位的整数，他现在想要挑战的问题是所有可能构成的整数中能正好被 $P$ 整除的有多少个。由于答案过大，他只想要知道答案$\bmod 999911659$ 就行了。

输入格式：

有且仅有一行两个数 $N\ (1 \le N \le 10^{18})$ 和 $P\ (1 \le P \le 500)$，用一个空格分开。

输出格式：

有且仅有一行一个数，表示答案除以 $999911659$ 的余数。

看上去挺像数位dp的，然而无从下手。

注意到这些数都是形如 $111222333445$ 的数，我们可以把它转化成

$\begin{aligned} &111111111111 \\[4pt]&000111111111 \\[4pt]&000000111111 \\[4pt]&000000000111 \\[4pt]+&000000000001 \\[4pt]\hline&111222333445 \end{aligned}$

这有什么用呢？注意到这几个 $111$ 的长度是严格不增的，并且至多有 $9$ 行这样的 $111$ 。

根据经典的转化，被 $p$ 恰好整除，意味着模 $p$ 意义下同余 $0$ 。

如果我们记 $f_1 = 1,~f_2=11$ ，那么 $f_i = 10f_{i-1} + 1$ 。

可以发现，这个式子在模 $p$ 意义下一定存在循环节，其长度不会超过 $p$ 。

考虑统计不同长度的 $111$ 构成的模意义下的等价类，不妨记 $g_i$ 表示模 $p$ 为 $i$ 的 $111$ 的个数。

那么问题就变为了，在所有的 $g_i$ 中选出不超过 $9$ 个数，使得他们的 $i$ 加起来模 $p$ 为 $0$ 。

考虑设 $f(i,j,k)$ 为选完了 $0$ 到 $i-1$ 的 $g_i$ 中的数，选了 $k$ 个，他们的和模 $p$ 为 $j$ 的方案数。

初值是 $f(0,m,0)=1$ ，这里 $m$ 表示最长的那个 $111$ 模 $p$ 的结果。

转移枚举 $g_i$ 中选了 $l$ 个数，这 $l$ 个数可以重复，那么

$f(i+1,\,(j+l\cdot i)\bmod p,\,k + l) \operatorname{\big\uparrow} f(i,j,k)\cdot \binom{g_i + l-1}{l}$

这里 $\uparrow$ 表示增量。答案就是 $\sum_{i=0}^8 f(p, 0, i)$ 。

时间复杂度 $\mathcal{O}(81p^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 999911659;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
template<typename T> void add(T &x, T y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(505))

int n, p, m, g[N], f[N][N][12], inv[N], C[N][N], a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> p; inv[1] = 1;
    if(n <= p) { 
        rep(i, 1, n) { m = (m * 10 + 1) % p, ++g[m]; }
    } else {
        int now = 1 % p, t, l;
        rep(i, 1, p + 1)
        {
            if(a[now]) { l = a[now], t = i - l; break; }
            a[now] = i; ++g[now]; now = (now * 10 + 1) % p;
        }
        rep(i, 0, p - 1) if(a[i] && a[i] >= l)
        {
            g[i] += (n - a[i]) / t % mod;
            if((a[i] - l + 1) % t == (n - l + 1) % t) m = i;
        }
    }
    rep(i, 2, 9) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    rep(i, 0, p - 1) C[i][0] = 1;
    rep(i, 0, p - 1) if(g[i])
        rep(j, 1, 8) 
        {
            C[i][j] = C[i][j - 1] * g[i] % mod * inv[j] % mod;
            g[i] = (g[i] + 1) % mod;
        }
    f[0][m][0] = 1;
    rep(i, 0, p - 1) rep(j, 0, p - 1)
        rep(k, 0, 8) rep(l, 0, 8 - k)
            add(f[i + 1][(j + l * i) % p][l + k], f[i][j][k] * C[i][l] % mod);
    int res = 0;
    rep(i, 0, 8) add(res, f[p][0][i]);
    cout << res << '\n';
    return 0;
}