题目描述

给定一个长度为k的数字串N以及三个质数p,q,r，请你将N划分为三段非空字符串，使得第一段能被p整除，第二段能被q整除，第三段能被r整除，且每一段都不含前导0。 注意：单独的0是允许的。 2015<=p,q,r

瞎做

我们可以很容易通过前缀和后缀和处理判断一个前缀或后缀是不是p或r的倍数。 这个q的倍数呢？ 假如[i,j]是q的倍数。 q|∑jk=ia[k]∗10j−k$q|/sum_{k=i}^ja[k]*10^{j-k}$ q|10j∗∑jk=ia[k]∗(10′)k$q|10^j*/sum_{k=i}^ja[k]*(10')^k$ 注意q>=2015且是质数，所以10^j可略去。 后面sigma式子只与k有关，因此可以处理那个东西的前缀和。 [i,j]是q的倍数，被转化为 q|sum[j]−sum[i−1]$q|sum[j]-sum[i-1]$ sum[i−1]≡sum[j](mod q)$sum[i-1]/equiv sum[j](mod/ q)$ 然后就很容易做了，开个桶统计sum模q的合法后缀有多少个，瞎扫一波。 注意不能含有前导0但是一个0是允许的。