<span>省选模拟3 题解</span>
A. 好题
很神仙的做法。
考虑颜色数较小的情况，可以直接通过状压$dp$实现。
对于颜色数较大，不妨通过随机数将每种颜色都映射到$k$的范围内。
显然这个玩意不会使答案更优，但是这样不一定能找出正确的答案。
然而算一下就可以发现，这个玩意的正确性高达$\frac{k!}{k^k}$，所以多次随机化就好了。
B. 坏题
显然这个题要用AC自动机来做，所以直接建出trie图来。
对于一个合法的串，它在trie图中一定可以表示为一个简单环，或者一个简单环连上一条链到达一个简单环。
所以tarjan缩完环之后在DAG上dp就好了。
C. 不好不坏题
正解似乎是洲阁筛，然而不会这个东西。
通过本题的特殊性质，$yy$出一个容斥做法。
考虑模数为$2$，只具有奇偶性的差别，所以只有$2^k*x^2$是非法的，扣掉这些数的贡献就好了。
考虑模数为$2017$，$2017$为一个质数，只要考虑在什么情况下模这个数为$0$。
将最终的数质因数分解，可以发现$p+1\ mod\ 2017=0$存在很多种情况，其中最小的情况$p=12101$。
$p^2+p+1\ mod\ 2017=0$存在$12$种情况，其中最小的情况$p=2311$。
$p^3+p^2+p+1\ mod\ 2017=0$只存在一种情况，即$p=229$。
打完这个表之后发现只要把这些玩意都通过$miller\ robin$预处理之后容斥一下就好了。
韶音科技二面141人在聊
