题解 P3589 【[POI2015]KUR】

Yajnun · 2019-01-25 21:17:42 · 题解

若小串a的首位在c\left [ x \right ]位出现 ，则

若a\left [ i \right ]=1，p-t\leqslant ax\leqslant -t-1，令l=p-t,r=-t-1 (mod~ n)

若l\leqslant r，a*x\in S=[l,r]，否则a*x\in S=[0,l]\cup [r,n-1]

通过枚举i可得到这样一组约束条件，通过对其取交集可求出a*x的范围。对前者可直接求出，对后者不如转换成其补集的并集的补集。因为a与n互质，所以在x可以任意取的情况下，a*x与[0,n-1]是一一对应的关系，\left |S \right |即为a*x的所有取值。

因为实际上x不能完全取完1到n的值，所以对于应再枚举有哪些x\in[n-m+1,n-1],a*x\in S，用总数减去这个值即为答案。