如果你不会CF1808E1的\(O(nK^3)\)做法，请点击这里
本题涉及：数据诈骗，这道题可以做到\(O(\log{n} + \log{K})\)的复杂度
我们发现对于所有数位的和\(S\)，满足\(2x \equiv S (\mod K)\)的\(x\)的种类只有\(1\)个或\(2\)个。具体的，当\(K\)为奇数时，\(x\)的种类有且只有一个，当\(K\)为偶数时，若\(S\)为偶数，则\(x\)的种类有\(2\)个，否则无解。因此，我们对\(K\)分奇偶考虑
- 当\(K\)为奇数时：
我们发现我们不知道值为\(x\)的位置有多少个，而如果枚举个数的话\(n \leq 10^{18}\)。正难则反，我们考虑拿总方案数\(-\)没有一个位置为\(x\)的方案数
我们发现正好有\(i\)个位置是\(x\)的方案数是难求的，但我们可以求出钦定\(i\)个位置是\(x\)，且满足\(2x \equiv S (\mod K)\)的方案数，然后用二项式反演啊
我们设\(f_s(i)\)表示钦定\(i\)个数为\(x\)，且满足\(2x \equiv S (\mod K)\)的方案数；同样的，\(g_s(i)\)表示恰好\(i\)个数为\(x\)，且满足条件的方案数，我们可以得到：
\[\begin{align} f_s(i) &= \binom{n}{i} K^{n-i-1} \ \ \ \ \ (i<n) \\ g_s(i) &= \sum_{j=i}^{n}{(-1)^{j-i} \binom{j}{i} f_s(j)} \end{align} \]其中计算\(f_s(i)\)时\(K^{n-i-1}\)的意思是剩下\(n-i-1\)位随便填，而我们只需要让最后一位填他们剩下的数，这样就能保证\(2x \equiv S (\mod K)\)的限制条件了
这里要注意\(f_s(i)\)在\(i=n\)时不满足条件，因为我们没有剩下的空位可以保证限制条件的满足，因此，对于\(i=n\)时要单独计算，计算方法后面再说
答案即为：
\[\begin{align} \sum_{s=0}^{K-1}{g_s(0)} &= \sum_{s=0}^{K-1}{\sum_{j=0}^{n}{(-1)^j f_s(j)}} \\ &= \sum_{s=0}^{K-1}{\sum_{j=0}^{n-1}{(-1)^j f_s(j)} + (-1)^n f_s(n)} \\ &= \sum_{s=0}^{K-1}{(\sum_{j=0}^{n-1}{(-1)^j \binom{n}{j} K^{n-j-1}} + (-1)^n f_s(n))} \\ &= \sum_{s=0}^{K-1}{(\frac{\sum_{j=0}^{n-1}{(-1)^j \binom{n}{j} K^{n-j}}}{K} + (-1)^n f_s(n))} \\ &= \sum_{s=0}^{K-1}{(\frac{\sum_{j=0}^{n}{(-1)^j \binom{n}{j} K^{n-j}} - (-1)^n}{K} + (-1)^n f_s(n))} \\ &= \sum_{s=0}^{K-1}{(\frac{(K-1)^n - (-1)^n}{K} + (-1)^n f_s(n))} \\ &= (K-1)^n - (-1)^n + (-1)^n \sum_{s=0}^{K-1}{f_s(n)} \\ \end{align} \]然后我们考虑\(f_s(n)\)怎么算，我们发现\(f_s(n) = [nx \equiv S (\mod K)]\)，我们把\(2x \equiv S\)带入后化简一下得到\(f_s(n) = [S(n-2) \equiv 0 (\mod K)]\)，而\(S(n-2)\)是一个定值。因此我们可以得到：\(\sum_{s=0}^{K-1}{f_s(n)} = \gcd(n-2,K)\)
这里可能有人有疑问(比如我)：为什么对于\(a,b\)，满足\(ax \equiv 0 (\mod b)\)的个数是\(\gcd(a,b)\)。我们考虑求出满足条件的最小的\(x\)，显然为\(\frac{lcm(a,b)}{a}=\frac{b}{\gcd(a,b)}\)，而对于\(0 \leq x < b\)中满足条件的\(x\)的个数即为\(\frac{b}{x} = \gcd(a,b)\)
带入化简后易得：\(ans = (K-1)^n - (-1)^n + (-1)^n \gcd(n-2,K)\)
最后不要忘记拿\(K^n\)减去\(ans\)
- 当\(K\)为偶数时：
首先，我们可以发现\(S\)为奇数时肯定无解，因此我们只考虑\(S\)为偶数的情况。此时可能的\(x\)值有\(x_1 = \frac{S}{2},x_2 = \frac{S+K}{2}\)
类似的，我们可以知道：
\[\begin{align} f_s(i) &= \binom{n}{i} 2^i K^{n-i-1} \ \ \ \ \ (i<n) \\ g_s(i) &= \sum_{j=i}^{n}{(-1)^{j-i} \binom{j}{i} f_s(j)} \end{align} \]其中\(2^i\)表示枚举这\(i\)个位置是\(x_1\)还是\(x_2\)的方案数
类似的推式子，可以得到：
\[\begin{align} \sum_{s=0,2|s}^{K-1}{g_s(0)} &= \ ...... \\ &= \sum_{s=0,2|s}^{K-1}{(\frac{(K-2)^n - (-2)^n}{K} + (-1)^n f_s(n))} \\ &= \frac{(K-2)^n - (-2)^n}{2} + (-1)^n \sum_{s=0,2|s}^{K-1}{f_s(n)} \\ \end{align} \]我们考虑如何计算\(f_s(n)\)，我们发现有\(f_s(n) = \sum_{j=0}^{n}{ \binom{n}{j}[x_2 j + x_1 (n-j) \equiv S (\mod K)] }\)，我们考虑化简式子：
\[\begin{align} f_s(n) &= \sum_{j=0}^{n}{ \binom{n}{j}[x_2 j + x_1 (n-j) \equiv S (\mod K)] } \\ &= \sum_{j=0}^{n}{ \binom{n}{j}[\frac{S+K}{2} j + \frac{S}{2} (n-j) \equiv S (\mod K)] } \\ &= \sum_{j=0}^{n}{ \binom{n}{j}[\frac{K}{2} j \equiv \frac{S}{2}(2-n) (\mod K)] } \\ \end{align} \]我们发现对于同余号左边\(\frac{K}{2} j \mod K\)的值只有\(0\)和\(\frac{K}{2}\)两种，而\(\frac{S}{2}(2-n)\)是一个定值，因此仅当\(S(2-n) \equiv 0 (\mod \frac{K}{2})\)时，\(f_s(n)\)才能取到值，否则\(f_s(n) = 0\)
我们通过二项式定理可以知道：
\[\begin{align} (1-1)^n &= \sum_{i=0}^{n}{(-1)^i \binom{n}{i}} \\ 0 &= \sum_{i=0}^{n}{(-1)^i \binom{n}{i}} \\ \sum_{i=0,2|i}^{n}{\binom{n}{i}} &= \sum_{i=1,2 \nmid i}^{n}{\binom{n}{i}} \\ \end{align} \]\[\begin{align} (1+1)^n &= \sum_{i=0}^{n}{\binom{n}{i}} \\ \sum_{i=0}^{n}{\binom{n}{i}} &= 2^n \\ \end{align} \]由这两个式子可知，\(f_s(n) = 2^{n-1}[S(2-n) \equiv 0 (\mod \frac{K}{2})]\)，然后就变成了我们已知的一个问题：
\[\begin{align} \sum_{s=0,2|s}^{K-1}{f_s(n)} &= \sum_{s=0,2|s}^{K-1}{2^{n-1}[S(2-n) \equiv 0 (\mod \frac{K}{2})]} \\ &= 2^{n-1}\sum_{s=0,2|s}^{K-1}{[S(2-n) \equiv 0 (\mod \frac{K}{2})]} \\ &= 2^{n-1}\sum_{s=0}^{K-1}{[S(2-n) \equiv 0 (\mod \frac{K}{2})]} \\ &= 2^{n-1} gcd(n-2, K) \\ \end{align} \]最后不要忘了用总方案数\(\frac{K^n}{2} -\)不满足条件的方案数
最终复杂度\(O(\log{n} + \log{K})\)
标签：CF1808E2,frac,sum,align,Minibuses,Venus,mod,binom,equiv From： https://www.cnblogs.com/fox-konata/p/17716958.html