题意:很简单了,不再赘述。
做法:
首先去掉一种很明显不行的方案即数的和为 \(P\) 的倍数,那不为 \(P\) 的倍数的有多少种呢?
因为不像正常的一样有 \(a_i=0\),不能说每次后面怎么填都有唯一一个对应,我们考虑记两个东西 \(f,g\) 代表长度为 \(n\) 的序列有多少个模 \(P\) 为 \(0\) 的和不为 \(0\) 的,有转移式:
然后我们就要算有多少个和不为 \(P\) 倍数且满足条件的数组。
首先我们不妨设最多的为 \(1\),如果不是我们乘上众数的逆元即可。
那么我们想一个事情,最后的序列一定是形如一段 \(1\) 然后间隔一个非 \(1\) 的数 \(b_i\),其实等同于我们一直在按 \(1\) 这样的小步在长度为 \(P\) 的环上走,然后一个大步,那我们的大步肯定是尽量用来跨过 \(0\) 的位置,因此我们其实可以很方便地得出来一个必要条件,假设有 \(k\) 个非 \(1\) 的元素 \(b_1,b_2\cdots b_k\),我们肯定要满足 \(n-k\le\sum\limits_{i=1}^k{P-b_i} + P-1\) 的,可以很方便用构造证明必要性。
那么是否一定是充分的呢?我们考虑反证,如果这个必要条件不成立,那么就要求我这个序列总和一定是至少为 \(\sum\limits_{i=1}^k{P-b_i} + P + \sum\limits_{i=1}^k b_i = P(k+1)\),同时不能是 \(P\) 的倍数,所以我们需要跨过 \(0\) 这个位置 \(k+1\) 次,但是只有 \(k\) 个数帮我们跨,所以矛盾了,充分性证毕。
然后我们就可以用这个条件去计算,计算合法的比较困难,我们考虑计算不合法的,这样右侧的柿子就直接被限制在 \(n\) 的范围内了,可以直接跑背包算右边的东西。注意到 \(P-b_i\) 其实是一个区间状物,所以可以前缀和优化做到 \(O(n^2)\)。
那么还剩最后一步,因为我们 dp 出来这个东西是没有加入众数排位置的,所以对于 \(dp_{i,j}\) 即 \(b\) 用了 \(i\) 个数且 \(\sum P-b_k = j\),要求 \(n-i-j\) 这个东西不能是 \(P\) 的倍数,贡献为 \(dp_{i,j}\times\binom{n}{i}\times(P-1)\),最后这个 \(P-1\) 是众数有 \(P-1\) 种。
按上述过程计算即可。