又是没做出来的简单题

· · 题解

思路

先想暴力做法，显然把重复的也拆开来，每一小段都算一遍贡献，然后相加，这样的时间复杂度是 O(\log_2{V}\displaystyle\sum_{i=1}^{n}{y_i}) 的。

思考优化，推一波式子。设第 i 重复段起始位置前已有 pre_i 位数， x_i 的位数为 len_i 。则答案为：

\displaystyle\sum_{i=1}^{n}{x_i\times 10^{pre} \times \displaystyle\sum_{j=1}^{y_i}{(10^{len_i})^{j-1}} }

实际上可以发现，后面求和求的是一个等比数列的和，只要我们快速算出这个和即可。设 sum(1,n)=\displaystyle\sum_{i=1}^{n}{q^{i-1}} ，根据高中数学知识可得求和公式：

sum(1,n)=\frac{1-q^n}{1-q}

这里有个除法，只要我们求出对应模意义下的乘法逆元即可，时间复杂度为 O(n\log_2{n}) 。

但是，题目给定的模数可不一定是质数，我赛时没看到直接挂没了，尽管你在 AT 可以获得几乎满分。思考如何去掉除法。

考虑给定的 y_i 的数据范围，当我们没有思路的时候就想想可不可以分块做。可以想到一种分治的做法，这种做法类似二分，后半部分的贡献可以由前半部分快速推出。具体的式子是这样：

(1+(10^{len})^{\frac{n}{2}})\ sum(1,\frac{n}{2}) &\text{if } n\equiv0 (\bmod 2) \\ (1+(10^{len})^{\frac{n}{2}})\ sum(1,\frac{n}{2})+(10^{len})^{n-1} &\text{if } n\equiv1 (\bmod 2) \end{cases}

看起来很像快速幂，最后的时间复杂度是 O(n\log_2^2{n}) 。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<list>
#include<set>
using namespace std;
typedef pair<int,int> PII;
const int N=1e4+10;
int n,p,len[N],q[N];
long long ans;
PII ar[N];
long long qpow(long long y,long long z){
    long long res=1;
    while(z){
        if(z&1)
            res=(res*y)%p;
        y=(y*y)%p;
        z>>=1;
    }
    return res;
}
long long sov(long long d,long long y){
    if(y==1)
        return 1;
    long long res;
    res=sov(d,y>>1);
    res=(res+res*qpow(d,y>>1))%p;
    if(y&1)
        res=(res+qpow(d,y-1))%p;
    return res;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&ar[i].first,&ar[i].second);
    scanf("%d",&p);
    long long pre=1;
    for(int i=1;i<=n;++i){
        int tem=ar[i].first;
        while(tem){
            tem/=10;
            ++len[i];
        }
        q[i]=qpow(10,len[i]);
    }
    for(int i=n;i>=1;--i){
        ans=(ans+ar[i].first*pre%p*sov(q[i],ar[i].second))%p;
        pre=pre*qpow(q[i],ar[i].second)%p;
    }
    printf("%lld\n",ans);
}