传送门

题意：给一个01串，其中有些字符为 ′ ? ′ '?' ′?′， ′ ? ′ '?' ′?′可以当做 0 0 0或 1 1 1。给定一个 k k k，问能否给 ′ ? ′ '?' ′?′赋上特定值后，其所有长度为k的字串0和1数量都相等。
我们用两个指针来维护长度为k的区间。假设当前区间符合条件，当 r + 1 r+1 r+1, l + 1 l+1 l+1的时候，可以发现必须要 s [ l ] = s [ r + 1 ] s[l]=s[r+1] s[l]=s[r+1]才可以满足条件。那么就可以转换成 s [ i ] = s [ j   m o d   k ] s[i]=s[j\bmod k] s[i]=s[jmodk]，当 s [ j   m o d   k ] s[j\bmod k] s[jmodk]是 ′ ? ′ '?' ′?′的时候显然需要赋成 s [ i ] s[i] s[i]，当不是的时候只需要看看是否相等。答案只需要检查 [ 0 , k − 1 ] [0,k-1] [0,k−1]是否符合即可。

#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
using namespace std;

void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }

typedef long long LL;
typedef pair<int,int> PII;

const int N=300010,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n,k;
char s[N];

bool check(int a,int b,int c)
{
    int d=abs(a-b);
    if(c<d) return true;
    c-=d; 
    if(c&1) return true;
    return false;
}

int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);

    int _; scanf("%d",&_);
    while(_--)
    {
        scanf("%d%d%s",&n,&k,s);
        int a,b,c; a=b=c=0;
        int len=strlen(s),st=0;
        bool f=true;
        for(int i=0;i<n;i++)
        {
            if(s[i%k]!=s[i])
            {
                if(s[i]!='?'&&s[i%k]=='?') s[i%k]=s[i];
                else if(s[i]=='?') continue;
                else f=false;
            }
        }
        for(int i=0;i<k;i++)
        {
            if(s[i]=='1') a++;
            else if(s[i]=='0') b++;
            else if(s[i]=='?') c++;
        }
        // cout<<a<<' '<<b<<' '<<c<<endl;
        if(check(a,b,c)) f=false;
        if(!f) puts("NO");
        else puts("YES");
    }




	return 0;
}