原题大意

给出一个大数$N$其形式为：

\overbrace{c_{k-1}\; c_{k-1}\; \cdots\; c_{k-1}}^{l_{k-1}}\cdots\overbrace{c_1\; c_1\; \cdots\; c_1}^{l_1}\overbrace{c_0\; c_0\; \cdots\; c_0}^{l_0} \tag{*}

其中 $c_i\in\{0,1,\cdots,9\} \ , \ 1 \le l_i \le 10^9 \, \ 1 \le k \le 10^5$

求 $\lfloor \frac{N}{M} \rfloor \pmod {10007}$

思路

我们考虑将向下取整符号去掉，

\because \ n=q \cdot m+r \ (0 \le r < m) \tag{**} \\ \therefore \ q=\frac{n-r}{m}=\frac{n-n\mod m}{m} \\

对于 $\text{ans}:=\lfloor \frac{n}{m} \rfloor \pmod {M}$ 可以化成：

\begin{aligned} \text{ans} :&= (n-n\mod m)\cdot \text{inv}(m) \pmod {M} \\ &=[\ (n \mod M - (n\mod m)\mod M +M) \mod M ]\cdot \text{inv}(m) \pmod {M} \\ \end{aligned}

我们记 $\text{inv}(m)$ 为 $m$ 在模 $M$ 意义下的逆元，并令：

r_m:=n \mod m \\ r_M:=n \mod M

又由 $(*)$ 式可知：

\begin{aligned} r_M&=\overbrace{c_{k-1}\; c_{k-1}\; \cdots\; c_{k-1}}^{l_{k-1}}\cdots\overbrace{c_1\; c_1\; \cdots\; c_1}^{l_1}\overbrace{c_0\; c_0\; \cdots\; c_0}^{l_0} \pmod {M} \\ &=\sum_{i=0}^{k-1} c_i 10^{l_0+l_1+\cdots+l_{i-1}}\sum_{j=0}^{l_i-1} 10^{j} \pmod {M} \ , \ \ \text{let} \ \ s_i=\sum_{j=0}^{i-1} l_j \\ &=\sum_{i=0}^{k-1}c_i10^{s_i}\sum_{j=0}^{l_i-1}10^j \pmod {M} \\ &=\sum_{i=0}^{k-1}10^{s_i}\cdot G(l_i,M) \pmod {M} \\ \end{aligned}

这里 $G(l_i,M)$ 表示 $c_i\cdot(10^0+10^1+\cdots+10^{l_i-1})\pmod M$
可以使用几何级数的递推公式求出：

G(n,M)=\begin{cases} G(l/2,M) \cdot (10^{l/2} + 1) \pmod M & l \text{ is even} \\ G(l-1) \cdot 10 + c_i \pmod M & l \text{ is odd} \end{cases}

同理：

\begin{aligned} r_m&=\overbrace{c_{k-1}\; c_{k-1}\; \cdots\; c_{k-1}}^{l_{k-1}}\cdots\overbrace{c_1\; c_1\; \cdots\; c_1}^{l_1}\overbrace{c_0\; c_0\; \cdots\; c_0}^{l_0} \pmod {m} \\ &=\sum_{i=0}^{k-1}c_i10^{s_i}\sum_{j=0}^{l_i-1}10^j \pmod {m} \\ &=\sum_{i=0}^{k-1}10^{s_i}\cdot G(l_i,m) \pmod {m} \\ \end{aligned}

然后将 $r_m$ 和 $r_M$ 改成递推的形式（从高位到低位），就可以在 $O(k)$ 的时间复杂度内求出答案。

\begin{aligned} r_m&:=(r_m\cdot 10^{l_i}+G(l_i\ ,\ m)\ ) \pmod m \\ r_M&:=(r_M\cdot 10^{l_i}+G(l_i \ ,\ M)\ ) \pmod M \\ \end{aligned}

代码

CodeBlock Loading...

扩展

M不是质数

如果M不是质数，但 $gcd(m,M)≠1$ 那么逆元 $\text{inv}(m)$ 可以用扩展欧几里得算法求出；
但 $gcd(m,M)≠1$ 时，逆元根本不存在，这是 $(**)$ 式可以变形成：

m \cdot q \equiv (r_M-r_m) \pmod M \tag{***}

一个关于q的线性同余方程组，可以先提取公因子 $g=gcd(m,M)$ 归一化，

\frac{m}{g} \equiv \frac{(r_M-r_m)}{g} \pmod {\frac{M}{g}}

此时 $gcd(\frac{m}{g} , \frac{M}{g})=1$ ，就可以用扩展欧几里得算法求出特解，

q_0 \equiv \frac{(r_M-r_m)}{g} \cdot \text{inv}(\frac{m}{g}) \pmod {\frac{M}{g}}

在加上 $k$ 个 $\frac{M}{g}$ ，就可以得到通解：

q=q_0+k \cdot \frac{M}{g} \ , \ k=0,1,2,\cdots, g-1

但是 $k$ 是由 $n$ 唯一确定的，只通过 $r_m \ , \ r_M$ 而不计算 n/m 时是无法直接确定k的，应该换个思路。

显然这里 $gcd(n,M)>1$ 对于周期为 $M$ 的 $r_M$ 以及周期为 $m$ 的 $r_m$ 来说，将周期扩大到其最小公倍数 $mM$ 。
这样当n加上m时 $\lfloor n/m \rfloor$ 就增加1，继续增加到 $nM$ 后此时商就变成了M，在模M意义下又回到了0，当然是符合向下取整后取余的。
具体地，我们设n对 $mM$ 的商为Q余数为R，那么有：

n=Q(m\cdot M)+R \ , \ 0 \le R < mM

我们要算的是 $\lfloor \frac{n}{m} \rfloor \pmod M$ 。将 $n$ 代入，得：

\begin{aligned} \lfloor \frac{n}{m} \rfloor \pmod M &= \lfloor \frac{Q(m\cdot M)+R}{m} \rfloor \pmod M \\ &= \left(QM + \lfloor \frac{R}{m} \rfloor \right) \pmod M \\ &= 0+ \lfloor \frac{R}{m} \rfloor \pmod M \\ &=\frac{n \pmod {m \cdot M} }{m} \pmod M \end{aligned}

这样完美避开了逆元和k无法确定的问题。

m和l变大

如果 $1 \le m,l \le 10^{18}$ ，最暴力的方法就是直接使用大数模拟完成，例如以下程序：

CodeBlock Loading...

但是很不幸，由于防止过程中乘法溢出，这里使用了模数乘法，导致最后的时间复杂度变成 $O(k \log l \cdot \log (m\cdot M))$ ，显然会T。

如果预处理 $10^i$ 模 $m\cdot M$ 的各项/和，但由于范围过大防止溢出，还是只能通过模数乘法来计算，时间复杂度仍然不变。

拆模

{% note info no-icon %}

引理：

今有一长度为 $l$ 的十进制数 $n$ ，

n:=\sum_{i=0}^{l-1}d_i10^i \ ,\ 0 \le c_i < 10

那么其 $\lfloor n/m \rfloor \mod M$ 的结果可以表示为：

\begin{aligned} \lfloor n/m \rfloor \pmod M &= \lfloor \frac{\sum_{i=0}^{l-1}d_i10^{i}}{m} \rfloor \pmod M \\ &=\lfloor \frac{\sum_{i=2}^{l-1}d_i10^{i}}{m} +\frac{(d_1d_0)_{10}}{m} \rfloor \pmod M \\ &=\lfloor \frac{\sum_{i=2}^{l-1}d_i10^{i-2}}{m} \cdot 10^2 +\frac{(d_1d_0)_{10}}{m} \rfloor \pmod M \\ \end{aligned}

我们记数字的前i位（高i位）为 $n_i:=\sum_{j=l-i-1}^{l-1}d_j10^j$ ，那么有：

\begin{aligned} q_i:&=\lfloor \frac{n_i}{m} \rfloor \pmod M = \lfloor \frac{\sum_{j=l-i-1}^{l-1}d_j10^{j-2}}{m} \rfloor \pmod M \\ r_i:&=n_i \pmod m =\sum_{j=l-i-1}^{l-1}d_j10^{j-2} \pmod m \\ n_i&=q_i \cdot m+r_i \ ,\ 0 \le r_i < m \end{aligned}

令 $n_0=d_{l-1}$ 不难发现有递推公式：

\begin{aligned} n_{i+1}&=n_i\cdot 10+d_{l-i-1}\\ r_{i+1}&=n_{i+1} \pmod m \\ &=(10q_im+10r_i+d_{l-i-1}) \pmod m \\ &=10r_i+d_{l-i-1} \pmod m \\ q_{i+1}&=\lfloor \frac{n_{i+1}}{m} \rfloor \pmod M \\ &=\lfloor \frac{10q_im+10r_i+d_{l-i-1}}{m} \rfloor \pmod M \\ &=10q_i +\lfloor \frac{10r_i+d_{l-i-1}}{m} \rfloor \pmod M \\ \end{aligned}

这样就可以递推处理商了，而且很好地避免了逆元等情况。

{% endnote %}

为了处理乘法范围过大，同时复杂度又不能接受，由上面的引理我们可以想到维护 $q\ ,\ r$ 模M，通过之前的递推公式，我们知道从高位到低位读入时有：

\begin{aligned} n_{i+1}&=n_i\cdot 10^{l_i}+c_i \sum_{j=0}^{l_i-1}10^j \\ \end{aligned}

那么其商和余数的递推公式可以写成：

\begin{aligned} r_{i+1}&=(10^{l_i} r_i+c_i\sum_{j=0}^{l_i-1}10^j) \pmod m \\ q_{i+1}&=\left( 10^{l_i}q_i + \left \lfloor \frac{10^{l_i} r_i+c_i\sum_{j=0}^{l_i-1}10^j}{m} \right \rfloor \right) \pmod M \end{aligned}

这里使用预处理 $10^i$ 分别模M和m的个项和合，然后把长度 $l$ 用二进制拆成若干个 $2^i$ 的和，这样就可以在 $O(k \log l)$ 的时间复杂度内求出答案。

{% note warning no-icon %}

CodeBlock Loading...

但是这样写WA了，原因是对于 $q_{i+1}$ 的向下取整的分子应该是除了 $r_i$ 剩下都不应该取模，以上程序计算 $10^{l_i} r_i+c_i\sum_{j=0}^{l_i-1}10^j$ 时，对于10的次幂以及和都做了取模处理，这显然是错误的。

如果使用模数为 $mM$ ，同样地，中间过程计算的积肯定会溢出，此时又用懒乘法，导致时间复杂度又变回去了。

{% endnote %}

{% note success no-icon %}

下面给出正确~~至少可以ac~~的代码 ~~虽然是pypy版本~~ ，直接完整地算出其分子：

CodeBlock Loading...

得益于pypy的JIT，这个代码既可以简洁地保持高精度，又可以在2.5s内跑完。

{% endnote %}

拆彻底

原题大意

给出一个大数$N$其形式为：

\overbrace{c_{k-1}\; c_{k-1}\; \cdots\; c_{k-1}}^{l_{k-1}}\cdots\overbrace{c_1\; c_1\; \cdots\; c_1}^{l_1}\overbrace{c_0\; c_0\; \cdots\; c_0}^{l_0} \tag{*}

其中 $c_i\in\{0,1,\cdots,9\} \ , \ 1 \le l_i \le 10^9 \, \ 1 \le k \le 10^5$

求 $\lfloor \frac{N}{M} \rfloor \pmod {10007}$

思路

我们考虑将向下取整符号去掉，

\because \ n=q \cdot m+r \ (0 \le r < m) \tag{**} \\ \therefore \ q=\frac{n-r}{m}=\frac{n-n\mod m}{m} \\

对于 $\text{ans}:=\lfloor \frac{n}{m} \rfloor \pmod {M}$ 可以化成：

\begin{aligned} \text{ans} :&= (n-n\mod m)\cdot \text{inv}(m) \pmod {M} \\ &=[\ (n \mod M - (n\mod m)\mod M +M) \mod M ]\cdot \text{inv}(m) \pmod {M} \\ \end{aligned}

我们记 $\text{inv}(m)$ 为 $m$ 在模 $M$ 意义下的逆元，并令：

r_m:=n \mod m \\ r_M:=n \mod M

又由 $(*)$ 式可知：

\begin{aligned} r_M&=\overbrace{c_{k-1}\; c_{k-1}\; \cdots\; c_{k-1}}^{l_{k-1}}\cdots\overbrace{c_1\; c_1\; \cdots\; c_1}^{l_1}\overbrace{c_0\; c_0\; \cdots\; c_0}^{l_0} \pmod {M} \\ &=\sum_{i=0}^{k-1} c_i 10^{l_0+l_1+\cdots+l_{i-1}}\sum_{j=0}^{l_i-1} 10^{j} \pmod {M} \ , \ \ \text{let} \ \ s_i=\sum_{j=0}^{i-1} l_j \\ &=\sum_{i=0}^{k-1}c_i10^{s_i}\sum_{j=0}^{l_i-1}10^j \pmod {M} \\ &=\sum_{i=0}^{k-1}10^{s_i}\cdot G(l_i,M) \pmod {M} \\ \end{aligned}

这里 $G(l_i,M)$ 表示 $c_i\cdot(10^0+10^1+\cdots+10^{l_i-1})\pmod M$
可以使用几何级数的递推公式求出：

G(n,M)=\begin{cases} G(l/2,M) \cdot (10^{l/2} + 1) \pmod M & l \text{ is even} \\ G(l-1) \cdot 10 + c_i \pmod M & l \text{ is odd} \end{cases}

同理：

\begin{aligned} r_m&=\overbrace{c_{k-1}\; c_{k-1}\; \cdots\; c_{k-1}}^{l_{k-1}}\cdots\overbrace{c_1\; c_1\; \cdots\; c_1}^{l_1}\overbrace{c_0\; c_0\; \cdots\; c_0}^{l_0} \pmod {m} \\ &=\sum_{i=0}^{k-1}c_i10^{s_i}\sum_{j=0}^{l_i-1}10^j \pmod {m} \\ &=\sum_{i=0}^{k-1}10^{s_i}\cdot G(l_i,m) \pmod {m} \\ \end{aligned}

然后将 $r_m$ 和 $r_M$ 改成递推的形式（从高位到低位），就可以在 $O(k)$ 的时间复杂度内求出答案。

\begin{aligned} r_m&:=(r_m\cdot 10^{l_i}+G(l_i\ ,\ m)\ ) \pmod m \\ r_M&:=(r_M\cdot 10^{l_i}+G(l_i \ ,\ M)\ ) \pmod M \\ \end{aligned}

代码

const ll M=10007;

ll qpow(ll a, ll b, ll m)
{
    ll res=1;
    a%=m;
    while(b)
    {
        if(b&1)res=res*a%m;
        a=a*a%m;
        b>>=1;
    }
    return res;
}

ll inv(ll x)
{
    return qpow(x,M-2,M);
}

ll sum(ll l, ll m)
{
    if(l==0)return 0;
    if(l==1)return 1;
    if(~l&1)return sum(l>>1, m)*(qpow(10, l>>1, m)+1)%m;
    return (sum(l-1,m)*10+1)%m;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll k,m; cin >> k >> m;
    vector<pll> A(k);
    for(int i=k-1; i>=0; i--)
        cin >> A[i].first >> A[i].second;

    ll a=0, rm=0, p=1, pm=1;
    
    // 这里是从低位到高位递推的
    for(auto [c,l]:A)
    {
        ll ca=c*sum(l,M)%M;
        a=(a+ca*p)%M;
        p=p*qpow(10,l,M)%M;
        
        ll cm=c*sum(l,m)%m;
        rm=(rm+cm*pm)%m;
        pm=pm*qpow(10,l,m)%m;
    }
    
    ll ans=(a-(rm%M)+M)%M*inv(m)%M;
    cout<<ans;

    return 0;
}

CodeBlock Loading...

扩展

M不是质数

如果M不是质数，但 $gcd(m,M)≠1$ 那么逆元 $\text{inv}(m)$ 可以用扩展欧几里得算法求出；
但 $gcd(m,M)≠1$ 时，逆元根本不存在，这是 $(**)$ 式可以变形成：

m \cdot q \equiv (r_M-r_m) \pmod M \tag{***}

一个关于q的线性同余方程组，可以先提取公因子 $g=gcd(m,M)$ 归一化，

\frac{m}{g} \equiv \frac{(r_M-r_m)}{g} \pmod {\frac{M}{g}}

此时 $gcd(\frac{m}{g} , \frac{M}{g})=1$ ，就可以用扩展欧几里得算法求出特解，

q_0 \equiv \frac{(r_M-r_m)}{g} \cdot \text{inv}(\frac{m}{g}) \pmod {\frac{M}{g}}

在加上 $k$ 个 $\frac{M}{g}$ ，就可以得到通解：

q=q_0+k \cdot \frac{M}{g} \ , \ k=0,1,2,\cdots, g-1

但是 $k$ 是由 $n$ 唯一确定的，只通过 $r_m \ , \ r_M$ 而不计算 n/m 时是无法直接确定k的，应该换个思路。

n=Q(m\cdot M)+R \ , \ 0 \le R < mM

我们要算的是 $\lfloor \frac{n}{m} \rfloor \pmod M$ 。将 $n$ 代入，得：

\begin{aligned} \lfloor \frac{n}{m} \rfloor \pmod M &= \lfloor \frac{Q(m\cdot M)+R}{m} \rfloor \pmod M \\ &= \left(QM + \lfloor \frac{R}{m} \rfloor \right) \pmod M \\ &= 0+ \lfloor \frac{R}{m} \rfloor \pmod M \\ &=\frac{n \pmod {m \cdot M} }{m} \pmod M \end{aligned}

这样完美避开了逆元和k无法确定的问题。

m和l变大

如果 $1 \le m,l \le 10^{18}$ ，最暴力的方法就是直接使用大数模拟完成，例如以下程序：

#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;
using ll = long long;

i128 mul(i128 a, i128 b, i128 m)
{
    i128 res=0;
    while(b)
    {
        if(b&1) res=(res+a)%m;
        a=(a+a)%m;
        b>>=1;
    }
    return res;
}

pair<i128,i128> calc(i128 l,i128 m)
{
    if(l==0) return {1%m,0};
    if(l==1) return {10%m,1%m};
    auto [p,s]=calc(l>>1,m);
    i128 p2=mul(p,p,m), s2=(mul(s,p,m)+s)%m;
    if(~l&1) return {p2,s2};
    else return {mul(p2,10,m),(mul(s2,10,m)+1)%m};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;ll m,M;
    cin >> k >> m >> M;

    i128 mM=(i128)m*M, cur=0;
    for(int i=0;i<k;i++)
    {
        ll c,l; cin >> c >> l;
        auto [p,g]=calc(l,mM);
        i128 add=mul((i128)c,g,mM);
        cur=(mul(cur,p,mM)+add)%mM;
    }

    i128 ans=(cur/m)%M;
    cout<<(ll)ans;
}

CodeBlock Loading...

但是很不幸，由于防止过程中乘法溢出，这里使用了模数乘法，导致最后的时间复杂度变成 $O(k \log l \cdot \log (m\cdot M))$ ，显然会T。

如果预处理 $10^i$ 模 $m\cdot M$ 的各项/和，但由于范围过大防止溢出，还是只能通过模数乘法来计算，时间复杂度仍然不变。

拆模

{% note info no-icon %}

引理：

今有一长度为 $l$ 的十进制数 $n$ ，

n:=\sum_{i=0}^{l-1}d_i10^i \ ,\ 0 \le c_i < 10

那么其 $\lfloor n/m \rfloor \mod M$ 的结果可以表示为：

\begin{aligned} \lfloor n/m \rfloor \pmod M &= \lfloor \frac{\sum_{i=0}^{l-1}d_i10^{i}}{m} \rfloor \pmod M \\ &=\lfloor \frac{\sum_{i=2}^{l-1}d_i10^{i}}{m} +\frac{(d_1d_0)_{10}}{m} \rfloor \pmod M \\ &=\lfloor \frac{\sum_{i=2}^{l-1}d_i10^{i-2}}{m} \cdot 10^2 +\frac{(d_1d_0)_{10}}{m} \rfloor \pmod M \\ \end{aligned}

我们记数字的前i位（高i位）为 $n_i:=\sum_{j=l-i-1}^{l-1}d_j10^j$ ，那么有：

\begin{aligned} q_i:&=\lfloor \frac{n_i}{m} \rfloor \pmod M = \lfloor \frac{\sum_{j=l-i-1}^{l-1}d_j10^{j-2}}{m} \rfloor \pmod M \\ r_i:&=n_i \pmod m =\sum_{j=l-i-1}^{l-1}d_j10^{j-2} \pmod m \\ n_i&=q_i \cdot m+r_i \ ,\ 0 \le r_i < m \end{aligned}

令 $n_0=d_{l-1}$ 不难发现有递推公式：

\begin{aligned} n_{i+1}&=n_i\cdot 10+d_{l-i-1}\\ r_{i+1}&=n_{i+1} \pmod m \\ &=(10q_im+10r_i+d_{l-i-1}) \pmod m \\ &=10r_i+d_{l-i-1} \pmod m \\ q_{i+1}&=\lfloor \frac{n_{i+1}}{m} \rfloor \pmod M \\ &=\lfloor \frac{10q_im+10r_i+d_{l-i-1}}{m} \rfloor \pmod M \\ &=10q_i +\lfloor \frac{10r_i+d_{l-i-1}}{m} \rfloor \pmod M \\ \end{aligned}

这样就可以递推处理商了，而且很好地避免了逆元等情况。

{% endnote %}

\begin{aligned} n_{i+1}&=n_i\cdot 10^{l_i}+c_i \sum_{j=0}^{l_i-1}10^j \\ \end{aligned}

那么其商和余数的递推公式可以写成：

\begin{aligned} r_{i+1}&=(10^{l_i} r_i+c_i\sum_{j=0}^{l_i-1}10^j) \pmod m \\ q_{i+1}&=\left( 10^{l_i}q_i + \left \lfloor \frac{10^{l_i} r_i+c_i\sum_{j=0}^{l_i-1}10^j}{m} \right \rfloor \right) \pmod M \end{aligned}

这里使用预处理 $10^i$ 分别模M和m的个项和合，然后把长度 $l$ 用二进制拆成若干个 $2^i$ 的和，这样就可以在 $O(k \log l)$ 的时间复杂度内求出答案。

{% note warning no-icon %}

#include <bits/stdc++.h>
using namespace std;

using i128 = __int128;
using ll = long long;

const int LOG=60;
vector<ll> p10m(LOG), p10M(LOG);
vector<ll> s10m(LOG), s10M(LOG);

void init(ll m, ll M)
{
    p10m[0]=10%m,p10M[0]=10%M;
    s10m[0]=1%m,s10M[0]=1%M;

    for(int i=1;i<LOG;i++)
    {
        p10m[i]=(i128)p10m[i-1]*p10m[i-1]%m;
        p10M[i]=(i128)p10M[i-1]*p10M[i-1]%M;
        s10m[i]=((i128)s10m[i-1]*p10m[i-1]+s10m[i-1])%m;
        s10M[i]=((i128)s10M[i-1]*p10M[i-1]+s10M[i-1])%M;
    }
}

pair<i128,i128> calc(i128 l,i128 mod,
                     const vector<ll>& p10,
                     const vector<ll>& s10)
{
    i128 p=1,s=0;
    for(int i=0;l;i++,l>>=1)
        if(l&1)
        {
            p=p*p10[i]%mod;
            s=(s*p10[i]+s10[i])%mod;
        }
    return {p,s};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;ll m,M;
    cin >> k >> m >> M;
    init(m,M);  
    i128 r=0, q=0;
    for(int i=0;i<k;i++)
    {
        ll c,l; 
        cin >> c >> l;
        auto [p,s]=calc(l,m,p10m,s10m);
        auto [P,S]=calc(l,M,p10M,s10M);  
        i128 t=(i128)p*r+(i128)c*s;
        r=t%m;
        q=((i128)P*q+t/m) % M;
    }
    cout << (ll)q;
}

CodeBlock Loading...

如果使用模数为 $mM$ ，同样地，中间过程计算的积肯定会溢出，此时又用懒乘法，导致时间复杂度又变回去了。

{% endnote %}

{% note success no-icon %}

下面给出正确~~至少可以ac~~的代码 ~~虽然是pypy版本~~ ，直接完整地算出其分子：

import sys

def sol():
    it=iter(map(int, sys.stdin.read().split()))
    try:
        K=next(it); m=next(it); M=next(it)
    except StopIteration: return

    mM = m * M
    P, S = [10%mM], [1%mM]
    for i in range(62):
        S.append((S[i]*P[i]+S[i])%mM)
        P.append((P[i]*P[i])%mM)

    r, q = 0, 0
    for _ in range(K):
        c, l = next(it), next(it)
        p, s, i = 1, 0, 0
        l = l
        while l:
            if l&1:
                s=(s*P[i]+S[i])%mM
                p=(p*P[i])%mM
            l>>=1
            i+=1
        t = r*p+c*s
        q = (q*(p%M)+(t%mM//m))%M # 这里利用之前的结论扩大模数mM
        r = t%m
        
    sys.stdout.write(str(q))

if __name__ == "__main__":
    sol()

CodeBlock Loading...

得益于pypy的JIT，这个代码既可以简洁地保持高精度，又可以在2.5s内跑完。

{% endnote %}

基于ABC448E的启发探索

阅读此文章之前，你可能需要首先阅读以下的文章才能更好的理解上下文。

原题大意

思路

代码

扩展

M不是质数

m和l变大

拆模

拆彻底

原题大意

思路

代码

扩展

M不是质数

m和l变大

拆模

拆彻底