題目描述

給定一個長度為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是允許的。