题目分析

题意转化为，有 $n$个数的序列，每个数你可以让它为一个 $[1,m]$之间的取值，问任意连续 $K$个数都线性无关的序列总数。

设 $m+1=2^c$

那么若 $K>c$，因为若 $K$个数线性相关，那么它们一定可以通过异或的方式生成 $2^K$个不同的数，所以这种情况下任意 $K$个连续的数一定线性无关，答案就是 $m^n$

若 $K \leq c$，考虑统计存在 $K$个连续的数线性相关的序列数 $ans$，最终答案就是 $m^n-ans$。设 $f(i,j)$表示放了 $i$个数，后 $j$个数线性相关。

假设新添加的数与这 $j$个数都线性相关，则一定是这 $j$个数可以生成的 $2^j$个数以外的数，所以 $f(i,j+1)+=(m-2^j)f(i,j)$

假设新添加的数与后 $t(t<j)$个数线性相关，而加上从后往前数的第 $t+1$个数后，就线性无关了。那么这个数一定是后 $t$个数生成的 $2^t$个数中的某个与第 $t+1$个数异或的结果，所以 $f(i,t+1)+=2^tf(i,j)$

对于每一个 $i$，$ans+=f(i,K)m^{n-i}$

可以矩阵快速幂，但是 $f(i,K)m^{n-i}$比较难处理。将答案看做一个关于 $m$的多项式，用秦九韶定理后，可以表示为：

$…(((f(0,K)m+f(1,K))m+f(2,K))m+f(3,K))m…$

就可以用矩阵处理了。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int mod=1000000007;
int n,m,K,c,bin[30];
struct matrix{int t[30][30];}X,re;

int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
matrix operator * (matrix A,matrix B) {
    matrix C;
    for(RI i=0;i<=K;++i)
        for(RI j=0;j<=K;++j) C.t[i][j]=0;
    for(RI k=0;k<=K;++k)
        for(RI i=0;i<=K;++i)
            for(RI j=0;j<=K;++j)
                C.t[i][j]=qm(C.t[i][j]+1LL*A.t[i][k]*B.t[k][j]%mod);
    return C;
}

class YetAnotherNim{
    public:
    int solve(int kn,int km,int kK) {
        n=kn,m=km,K=kK;
        for(RI i=m+1;i!=1;i>>=1) ++c;
        if(K>c) return ksm(m,n);
        bin[0]=1;for(RI i=1;i<=c;++i) bin[i]=bin[i-1]<<1;
        for(RI i=1;i<K;++i) {
            for(RI j=0;j<i;++j) X.t[j+1][i]=bin[j];
            X.t[i+1][i]=m+1-bin[i];
        }
        X.t[0][K]=1,X.t[0][0]=m;
        for(RI i=0;i<=K;++i) re.t[i][i]=1;
        for(RI i=n;i;i>>=1,X=X*X) if(i&1) re=re*X;
        return qm(ksm(m,n)-1LL*m*re.t[0][1]%mod+mod);
    }
};