\[\sum_{i=0}^{\lfloor\frac{n}{k}\rfloor}\binom{n}{i\times k}F_{i\times k}
\]
花里胡哨。
\[\sum_{i=0}^{n}\binom{n}{i}F_i[k\mid i]
\]
\[\sum_{i=0}^{n}\binom{n}{i}F_i\frac{1}{k}\sum_{j=0}^{k-1}w_k^{ij}
\]
\[\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^{n}\binom{n}{i}F_iw^{ij}
\]
\[\sum_{i=0}^{n}\binom{n}{i}F_i(w^j)^i
\]
\[\sum_{i=0}^{n}\binom{n}{i}(xw^j)^i\bmod(1-x-x^2)
\]
\[(xw^j+1)^n\bmod(1-x-x^2)
\]
写个快速幂即可。
复杂度 \(O(k2^2\log n)\)。
这道题的难点居然是太久没复习常系数齐次线性递推忘记怎么写了。。。
#include<cstdio>
typedef unsigned ui;
typedef __uint128_t LL;
typedef unsigned long long ull;
ull n;ui T,g,p,k;ui m,idx[15];
struct Barrett{
ull m;LL B;
Barrett(const ull&m):m(m),B((LL(1)<<64)/m){}
friend inline ull operator%(const ull&a,const Barrett&mod){
ull r=a-ull(a*mod.B>>64)*mod.m;return r>=mod.m?r-mod.m:r;
}
}mod(2);
struct poly{
ui f0,f1;
poly(const ui&f0=0,const ui&f1=0):f0(f0),f1(f1){}
inline poly operator*(const poly&it){
const ui&g0=(1ull*f0*it.f0)%mod,&g1=(1ull*f0*it.f1+1ull*f1*it.f0)%mod,&g2=(1ull*f1*it.f1)%mod;
return poly((g0+g2)%mod,(g1+g2)%mod);
}
};
inline ui pow(ui a,ui b){
ui ans(1);for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;return ans;
}
inline ui Solve(const ui&c,ull n){
poly a(1,c),ans(1,0);for(;n;n>>=1,a=a*a)if(n&1)ans=ans*a;return(ans.f0+ans.f1)%mod;
}
inline ui find_g(ui p){
const ui P=--p;ui g=2;m=0;
for(ui i=2;i*i<=p;++i)if(!(p%i)){
idx[m++]=P/i;while(!(p%i))p/=i;
}
if(p^1)idx[m++]=P/p;
while(true){
bool typ(true);
for(ui i=0;i^m;++i)if(pow(g,idx[i])==1){
typ=false;break;
}
if(typ)return g;++g;
}
}
signed main(){
scanf("%u",&T);
while(T--){
scanf("%llu%u%u",&n,&k,&p);mod=Barrett(p);g=find_g(p);
ui x(1),y(pow(g,(p-1)/k));ull ans(0);
for(ui i=0;i<k;++i,x=1ull*x*y%mod)ans+=Solve(x,n);printf("%u\n",1ull*(ans%mod)*pow(k,p-2)%mod);
}
}