AC. 梦想

frank_c1

[HNOI 2016] 大数

发布于2016年04月20日 | 2条评论 | 1,315阅读 | 莫队算法

题目描述

小 B 有一个很大的数 S,长度达到了N位;这个数可以看成是一个串,它可能有前导 0,例如00009312345。小B还有一个素数P。现在,小 B 提出了M个询问,每个询问求 S 的一个子串中有多少子串是 P 的倍数(0 也是P的倍数)。例如 S为0077时,其子串 007有6个子串:0,0,7,00,07,007;显然0077的子串007有6个子串都是素
数7的倍数。

输入格式

第一行一个整数:P。第二行一个串:S。第三行一个整数:M。接下来M行,每行两个整数 fr,to,表示对S的子串S[fr...to]的一次询问。注意:S的最左端的数字的位置序号为 1;例如S为213567,则S[1]为 2,S[1...3]为 213。

N,M \le 100000,P \le 10 ^ {10}P为素数。

输出格式

输出M行,每行一个整数,第i行是第i个询问的答案。

题目解析

先考虑P \neq 2,5的情况,此时有10 ^ k \mod  P\neq 0。根据模运算的性质,对于一个子串S[l:r],若S[l:n] - S[r+1:n] \equiv 0 \pmod{P},则S[l:r]可以被P整除。

S[i:n] \mod P可以O(n)预处理出来。于是问题就转化成求一段区间内权值相同数对的个数,这是莫队的经典题目[BZOJ 2038] 小Z的袜子。总时间复杂度O(n \sqrt{n})

上述结论在P = 2,5时是不成立的,因为无法满足10 ^ k \mod P \neq 0。由于2,5的倍数性质比较特殊,我们可以直接特判。2的倍数末位必为2的倍数,5的倍数必为5的倍数。询问时,可以找到每一个满足条件的位置i,它对答案的贡献就是i-l+1。预处理一下就好。时间复杂度O(n)

  • sushi

    是无法满足10 ^ k % p != 0吧QAQ

    • 笔误,已改正。谢谢提醒!