都要考省选了大脑还在这里下线
场上看到这道题很快推出了 \(k\) 为奇数的搞法，发现可以直接做到 \(O(k\log n)\)，一阵狂喜然后肝起了 E3，结果 E1 都没过。
事实上这道题可以直接做到 \(O(\log n)\)，不过需要细致的观察自己场上推的式子。
题意：
对长度为 \(n\)，值域为 \([0,k)\) 的整数数组 \(a\) 计数，要求 \(a\) 满足 \(\exists i\in [1,n],\sum_{j\neq i} a_j\equiv a_i\pmod k\)。
思路：
这道题的分析频繁用到了一次同余方程式的有解性分析，也就是说对于 \(a\equiv b \pmod k\)，当 \(\gcd(a,k)|b\) 时有 \(\gcd(a,k)\) 个解，否则无解。
显然可以先枚举一波 \(sum=(\sum_{i=1}^n a_i) \bmod k\)，那么题目的条件相当于 \(\exists i\in [1,n],2a_i\equiv sum \pmod k\)。
\(k\) 是奇数时上述方程始终有唯一解，题目的限制相当于强制 \(\frac{sum}{2}\) 必须出现。
考虑计数强制 \(x=\frac{sum}{2}\) 必须不出现，然后对着这个限制上容斥，钦定 \(x\) 至少出现了 \(i\) 次。
剩下的部分如果 \(n-i>0\)，那么通过调整最后一个数的取值总可以满足 \(\sum_{i=1}^n a_i \equiv sum \pmod k\)。如果 \(i=n\) 那么只需要判断 \(nx\) 是否同余于 \(sum\)。
方案数就是：
对于所有 \(sum=2x\)，考虑 \([nx\equiv 2x\pmod k]\) 的有解性，总方案数就是：
\(k\) 是偶数时更复杂一点。这时 \(2a_i\equiv sum \pmod k\) 在 \(sum\) 是偶数时有两个解，记为 \(x\) 和 \(x+\frac{k}{2}\)。
现在要求序列中这两个解必须至少出现一个，那么考虑计数两个解都没有出现的方案数。
依然考虑对于“没有出现”这一限制施加容斥，枚举 \(x\)，\(x+\frac{k}{2}\) 的出现次数。
用三项式定理做一下右边的部分，就是：
左边的线性同余方程的解是一个等差数列，相当于是要组合数等差数列位置的和。这里场后被 zhy 教育了，可以直接循环卷积快速幂 \(O(k^2\log n)\) 做。
然而这个同余式太有性质了！整理一下：
也就是：
右边只与 \(i\) 奇偶性有关！左边只与 \(n,x\) 有关！而众所周知组合数奇数偶数位置求和都是 \(2^{n-1}\)。
我们现在只需要求出满足 \([(2-n)x \equiv 0 \pmod k]\) 或 \([(2-n)x \equiv \frac{k}{2} \pmod k]\) 的 \(x\) 的个数。
注意 \(x\) 本来就满足 \(x<\frac{k}{2}\)可以统一写成 \([(2-n)x\equiv 0 \pmod{\frac{k}{2}}]\)，\(x\) 的个数就是 \(\gcd(\frac{k}{2},n-2)\)。
总的式子就是：
这道题就做完了。
#include <cstdio>
using namespace std;
template<typename T>
T read(){
char c=getchar();T x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
typedef long long ll;
ll n;int k,p;
int qp(int a,ll b){
int res=1;
b%=(p-1);
while(b){
if(b&1) res=(ll)res*a%p;
a=(ll)a*a%p;b>>=1;
}
return res;
}
ll gcd(ll a,ll b){
if(!b) return a;
return gcd(b,a%b);
}
void inc(int &x,int v){if((x+=v)>=p) x-=p;}
void dec(int &x,int v){if((x-=v)<0) x+=p;}
int main(){
n=read<ll>();k=read<int>();p=read<int>();
if(n==1){puts("1");return 0;}
if(k&1){
int g=gcd(n-2,k);
int res=qp(k,n);
dec(res,qp(k-1,n));
if(n&1) inc(res,g-1);
else dec(res,g-1);
printf("%d\n",res);
}
else{
int g=gcd(n-2,k>>1);
int res=qp(k,n);
dec(res,qp(k-2,n));
inc(res,qp(p-2,n));
if(res&1) res=(res+p)>>1;
else res>>=1;
if(n&1) inc(res,(ll)qp(2,n-1)*g%p);
else dec(res,(ll)qp(2,n-1)*g%p);
printf("%d\n",res);
}
return 0;
}