题目链接 https://loj.ac/problem/2053
题目描述
小 B 有一个很大的数 $ S $, 长度达到了 $ N $ 位; 这个数可以看成是一个串, 它可能有前导 $ 0 $, 例如 00009312345 . 小 B 还有一个素数 $ P $.
现在, 小 B 提出了 $ M $ 个询问, 每个询问求 $ S $ 的一个子串中有多少子串是 $ P $ 的倍数 ($ 0 $ 也是 $ P $ 的倍数). 例如 $ S $ 为 0077 时, 其子串 007 有六个子串: 0, 0, 7, 00, 07, 007; 显然 0077 的子串 077 的六个子串都是素数 $ 7 $ 的倍数.
输入格式
第一行一个整数:$ P $.
第二行一个串:$ S $.
第三行一个整数:$ M $.
接下来 $ M $ 行, 每行两个整数 $ \text{fr}, \text{to}$, 表示对 $ S $ 的子串 \(S[\text{fr} \ldots \text {to}]\) 的一次询问.
注意:$ S $ 的最左端的数字的位置序号为 $ 1 $; 例如 $ S $ 为 $ 213567 $, 则 $ S[1] $ 为 $ 2 \(,\) S[1 \ldots 3] $ 为 $ 213 $.
输出格式
输出 $ M $ 行, 每行一个整数, 第 $ i $ 行是第 $ i $ 个询问的答案.
样例
样例输入
- 11
- 121121
- 3
- 1 6
- 1 5
- 1 4
样例输出
5 3 2
样例解释
第一个询问问的是整个串, 满足条件的子串分别有: 121121,2112,11,121,121.
数据范围与提示
对于所有的数据,$ N,M \leq 100000 \(,\) P $ 为素数.
参考题解
我们要求的是
\[ \displaystyle \begin{align} ans&=\sum_{i=l}^r\sum_{j=i}^r [\sum_{k=i}^js_k\cdot 10^{j-k} ==0\ mod\ p]\&=\sum_{i=l}^r\sum_{j=i}^r10^{j}[\sum_{k=i}^js_k\cdot 10^{-k} ==0\ mod\ p] \end{align} \]
如果质数 \(P\) 不等于 \(2\) 或 \(5\), 那么 \(10^j\) 不可能等于 \(0\), 并且 \(10^k\) 是有逆元的.
我们设 \(s_k\cdot 10^{-k}\) 的前缀和为 \(sum_k\), 则我们要求的就是:
\[ \displaystyle \sum_{i=l}^r\sum_{j=i}^r[sum_j==sum_i] \]
这就是一个经典的莫队问题.
类似的题还有 [CQOI2018] 异或序列.
当 \(P\) 等于 \(2\) 或者 \(5\) 的时候, 我们知道只需要判断一个字串的最后一位就可以了, 所以很好做.
代码:
- #include<bits/stdc++.h>
- #define ll long long
- #define N 200005
- using namespace std;
- inline ll Get() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
- ll p;
- char s[N];
- int n,m;
- int bel[N];
- ll ans[N];
- ll sum[N],d[N];
- ll cnt[N];
- const int blk=450;
- struct query {
- int l,r;
- int id;
- bool operator <(const query &a)const {
- if(bel[l]!=bel[a.l]) return l<a.l;
- return bel[l]&1?r<a.r:r>a.r;
- }
- }q[N];
- ll ksm(ll t,ll x,ll mod) {
- ll ans=1;
- for(;x;x>>=1,t=t*t%mod)
- if(x&1) ans=ans*t%mod;
- return ans;
- }
- ll now=0;
- void add(int v) {
- now+=cnt[sum[v]];
- cnt[sum[v]]++;
- }
- void del(int v) {
- cnt[sum[v]]--;
- now-=cnt[sum[v]];
- }
- ll tot[N],size[N];
- int main() {
- p=Get();
- scanf("%s",s+1);
- n=strlen(s+1);
- m=Get();
- for(int i=1;i<=m;i++) {
- q[i].l=Get()-1,q[i].r=Get();
- q[i].id=i;
- }
- if(p!=2&&p!=5) {
- for(int i=0;i<=n;i++) bel[i]=i/blk+1;
- sort(q+1,q+1+m);
- d[++d[0]]=0;
- ll inv10=ksm(10,p-2,p),t=inv10;
- for(int i=1;i<=n;i++) {
- sum[i]=(sum[i-1]+(s[i]-'0')*t)%p;
- t=t*inv10%p;
- d[++d[0]]=sum[i];
- }
- sort(d+1,d+1+d[0]);
- int cc=unique(d+1,d+1+d[0])-d-1;
- for(int i=0;i<=n;i++) sum[i]=lower_bound(d+1,d+1+cc,sum[i])-d;
- int l=0,r=-1;
- for(int i=1;i<=m;i++) {
- while(r<q[i].r) add(++r);
- while(l>q[i].l) add(--l);
- while(r>q[i].r) del(r--);
- while(l<q[i].l) del(l++);
- ans[q[i].id]=now;
- }
- for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
- } else {
- if(p==2) {
- for(int i=1;i<=n;i++) {
- tot[i]=tot[i-1];
- size[i]=size[i-1];
- if((s[i]-'0')%2==0) {
- tot[i]+=i;
- size[i]++;
- }
- }
- } else {
- for(int i=1;i<=n;i++) {
- tot[i]=tot[i-1];
- size[i]=size[i-1];
- if((s[i]-'0')%5==0) {
- tot[i]+=i;
- size[i]++;
- }
- }
- }
- for(int i=1;i<=m;i++) {
- cout<<(tot[q[i].r]-tot[q[i].l])-(size[q[i].r]-size[q[i].l])*q[i].l<<"\n";
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2977609.html