PS：本题解为 $O(n)$。

Solution

Step1：分析 $SMS$ 的性质

记：原二进制数的第 $i$ 为 $a_i$。

那么： $SMS_i = \sum_{j = i}^{i-k+1} a_j$。

我们发现：$SMS_i$ 和 $SMS_{i+1}$ 管辖的区间只有一个数不同。

记：$d_i = SMS_{i+1} - SMS_{i}$。
因为 $a_i \in \{0,1\}$，那么：$d_i\in \{0,1,-1\}$。

那么我们进行分类讨论：

• $d_i = 1$ 时：$a_i = 1,a_{i+k} = 0$。
• $d_i = 0$ 时：$a_i = a_{i+k}$。
• $d_i = -1$ 时：$a_i = 0,a_{i+k} = 1$。

那么我们发现：只有 $d_i = 0$ 是特殊的，其他的情况都已经确定。

Step2：找出所有已经确定的值。

建图是一种很好的方式。

定义一张无向图，$i$ 和 $j$ 之间有一条边，就表示：$a_i = a_j$。

记：一个连通块内的所有点所组成的集合为 $S$。
那么，$\forall x,y \in S , a_x = a_y$。

也就是说，如果连通块中有一个元素是确定的，那整个连通块就确定了。

找连通块，我们可以把图建出来，然后dfs即可。

Step3：计算答案

注意到，答案只和 $a$ 中区间 $[1,k]$ 中的元素有关。

证明：

若 $a_1$ 确定，那么，就可以通过 $d_1$ 算出 $a_{1+k}$，再通过 $d_{1+k}$ 算出 $a_{1+2k}$。

这也就是说：只要 $a_x (1 \le x \le k)$ 固定，那么：$\forall y \in \{y | y \bmod k = x\}$ 的 $a_y$ 都可以算出来。

记：$[1,k]$ 中已经确定的数的数量为 $x$，其中，$1$ 的数量为 $y$。 那么：还没确定的数的数量为 $k-x$，其中 $1$ 的数量为 $SMS_1 - y$。 那么：

Step4：分析时间复杂度

建图：$O(n)$。

dfs：$O(n+m)$，$m$ 为图的边数，$m \le n$，所以为 $O(n)$。

计算答案：$O(k) \le O(n)$。

综上：时间复杂度为 $O(n)$。

Code

#include<cstdio>
#include<vector>
#define ll long long
const int N = 1e6+5;
const ll P = 1e6+3;
ll finv[N],fac[N];
inline ll Fpow(ll a,ll b){
	ll ans = 1;
	while(b){
		if(b&1) ans = ans*a%P;
		a = a*a%P,b>>=1;
	}
	return ans;
}
inline void init(int n){
	fac[0] = 1;
	for(int i = 1;i<=n;++i) fac[i] = fac[i-1] * i % P;
	finv[n] = Fpow(fac[n],P-2);
	for(int i = n-1;i>=0;--i) finv[i] = finv[i+1] * (i+1) % P; 
}
inline ll C(int n,int m){
	return fac[n] * finv[m] % P * finv[n-m] % P;
}
struct Edge{
	int to,next;
}e[N<<1];
int head[N],cnt = 0;
inline void Link(int u,int v){
	e[++cnt] = {v,head[u]};
	head[u] = cnt;
}
int vis[N],T;
inline void dfs(int u){
	if(vis[u]) return ;
	vis[u] = T;
	for(int i = head[u];i;i = e[i].next) 
		dfs(e[i].to);
}
int SMS[N],a[N];
std::vector<int> Block[N];
int main(){
	int n,k;
	std::scanf("%d %d",&n,&k);
	for(int i = 1;i<=n;++i) a[i] = -1; 
	for(int i = 1;i<=n-k+1;++i) std::scanf("%d",SMS+i);
	for(int i = 1;i<=n-k;++i){
		int d = SMS[i] - SMS[i+1];
		if(!d) Link(i,i+k),Link(i+k,i);
		else{
			if(d == 1) a[i] = 1,a[i+k] = 0;
			else a[i+k] = 1,a[i] = 0; 
		}
	}
	for(int i = 1;i<=n;++i)
		if(!vis[i]) ++T,dfs(i);
	for(int i = 1;i<=n;++i) Block[vis[i]].push_back(i);
	for(int i = 1;i<=T;++i){
		int V = -1;
		for(int x : Block[i]) if(a[x] != -1) V = a[x];
		for(int x : Block[i]) a[x] = V;
	}
	int x = k,y = SMS[1];
	for(int i = 1;i<=k;++i) 
		if(a[i] != -1){
			--x;
			if(a[i] == 1) --y;
		}
	init(k);
	printf("%lld",C(x,y));
	return 0; 
}