2021“MINIEYE杯”中国大学生算法设计超级联赛（8）

可能开学前补不完这场了。

军训期间补完了。

[1001 X-liked Counting]

solution

题面：一个数被称为好数，当且仅当存在一个它的前缀或后缀可以被 整除。 是给定的一个数。问 到 的所有不含 的数中，是好数的个数。

做法：直接算前缀或后缀不容易，于是想着算都不被整除，再用总数量减去它。总数量可以数位 ，即设 表示当前为第 位是否达到上界，不转移 就可以了。

都不被整除的方案计算，我们记录前缀的值，但此时不容易算后缀的值，于是我们再枚举总的值，利用总的值和前缀的值就可以算出后缀的值了，剩下的就是基本的数位 了，具体细节请看代码。

坑：当前缀已经是总长时，不能再算后缀了。

//2021.9.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    LL f[18][500];
    int a[19],ax;
    LL pw[19];
    int Pw[19];
    int x;
    LL dp(res len,res r,res up,res vis,const res &R){
        if(len==-1)return r==R&!vis;
        if(~f[len][r]&&(!up))return f[len][r];
        RG LL ret=0;
        res c=up?a[len]:9;
        for(res i=0;i<=c;i++){
            if(i==7)continue;
            if(i==0&&vis){
                ret+=dp(len-1,r,up&(i==c),1,R);
                continue;
            }
            res d=(r*10+i)%x;
            if(!d)continue;
            res D=d;
            if(len){
                d=d*Pw[len]%x;
                d=R-d;
                if(d<0)d+=x;
                if(!d)continue;
            }
            ret+=dp(len-1,D,up&(i==c),0,R);
        }
        if(!up)f[len][r]=ret;
        return ret;
    }
    LL g[18];
    LL G(res len,res up){
        if(len==-1)return 1;
        if(~g[len]&&(!up))return g[len];
        RG LL ret=0;
        res c=up?a[len]:9;
        for(res i=0;i<=c;i++)if(i!=7)ret+=G(len-1,up&(i==c));
        if(!up)g[len]=ret;
        return ret;
    }
    inline LL solve(RG LL up){
        ax=0;
        while(up)a[ax++]=int(up%10),up/=10;
        RG LL ret=0;
        for(res i=0;i<x;i++){
            for(res _=0;_<ax;_++)for(res __=0;__<x;__++)f[_][__]=-1;
            RG LL o=0;
            ret+=o=dp(ax-1,0,1,1,i);
        }
        for(res _=0;_<ax;_++)g[_]=-1;
        return G(ax-1,1)-ret;
    }
    inline void MAIN(){
        pw[0]=1;
        for(res i=1;i<=18;i++)pw[i]=pw[i-1]*10;
        res Case=read();
        while(Case--){
            RG LL l=Read(),r=Read();
            x=read();
            for(res i=0;i<=18;i++)Pw[i]=int(pw[i]%x);
            printf("%lld\n",solve(r)-solve(l-1));
        }
    }
}

[1002 Buying Snacks]

solution

题面： 种商品，都有大份和小份，大份 块钱，小份 块钱，购买商品时可以选择相邻的两种商品一起购买，这样可以使大份变为 块，每种商品最多买一件。对所有的，求出恰好花 元的方案数。

做法：直接从组合意义下手，是枚举用了几个打折之类的，可以写出一串 ，但不容易优化。

考虑最基础的 ，设 表示考虑到第 件商品，前面用了 元的方案数。

转移是容易的，。

这样就很简单了，设 的 为 ，于是 。

其中 。那么这直接做 + 矩乘即可，复杂度 。

能不能再给力点？

其实完全是可以的。当我们将多项式看做一个向量时，它是可以使用特征方程的。于是对递推式做特征方程，非常容易地求出了

$$F_n=\frac{[(x+1)^2]^{n+1}-(-x)^{n+1}}{(x+1)^2+x}$$

而我们要求的则是 ，这些都可以 解出，瓶颈在求逆。

然后你再冷静一下，发现分母的多项式长度是常数级别的，所以就可以 求出了。

官方题解不知道为什么没写阳间的做法。

这题行末不加空格就错了，什么逆天。

//2021.8.30 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int f[N],inv[N];
    int n,m;
    inline void MAIN(){
        inv[0]=inv[1]=1;
        for(res i=2;i<=N-10;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        res Case=read();
        while(Case--){
            n=read(),m=read();
            res fac=1;
            for(res i=0;i<=m;i++){
                if(2*n+2>=i)f[i]=fac,fac=mul(fac,mul(2*n+2-i,inv[i+1]));
                else f[i]=0;
            }
            if(n+1<=m)add(f[n+1],n&1?kcz-1:1);
            for(res i=0;i<=m;i++)add(f[i+1],kcz-Add(Add(f[i],f[i]),f[i])),add(f[i+2],kcz-f[i]);
            for(res i=1;i<=m;i++)printf("%d ",f[i]);
            puts("");
        }
    }
}

[1003 Ink on paper]

solution

题面：二维平面上 个点，每个点每秒会向外围延伸一单位，问什么时候全部联通。

做法：最多连接 次，而且每个点肯定是要和最小的点连接，那么直接做就是 。

冷静一下就是 。

//2021.8.29 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=5e3+10;
namespace MAIN{
    int n;
    inline LL getdis(const RG Pair &x,const RG Pair &y){
        return 1ll*(x.fi-y.fi)*(x.fi-y.fi)+1ll*(x.se-y.se)*(x.se-y.se);
    }
    LL dis[N],ans;
    Pair a[N];
    int vis[N];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),ans=0;
            for(res i=1;i<=n;i++){
                res x=read(),y=read();
                a[i]=mp(x,y),dis[i]=getdis(a[i],a[1]),vis[i]=0;
            }
            vis[1]=1;
            for(res _=1;_<n;_++){
                res j=0;
                for(res i=2;i<=n;i++)if(!vis[i]&&(!j||dis[i]<dis[j]))j=i;
                ans=max(ans,dis[j]),vis[j]=1;
                for(res i=2;i<=n;i++)if(!vis[i])dis[i]=min(dis[i],getdis(a[i],a[j]));
            }
            printf("%lld\n",ans);
        }
    }
}

[1004 Counting Stars]

solution

题面：三种操作，区间 ，区间 ，区间加最高位 。

做法：发现总共的 的数量是一直在减少的，直接暴力的数量就是 了。

区间修改就用线段树直接维护，那只要对最高位特殊处理即可，复杂度就是 。

//2021.8.29 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,a[N];
    int tr[N<<2],laz[N<<2];
    LL sz[N<<2];
    inline void change(const res &rt,const res &v){
        laz[rt]=mul(laz[rt],v),tr[rt]=mul(tr[rt],v);
    }
    inline void pushdown(const res &rt){
        if(laz[rt]==1)return;
        change(rt<<1,laz[rt]),change(rt<<1|1,laz[rt]),laz[rt]=1;
    }
    inline void pushup(const res &rt){
        sz[rt]=sz[rt<<1]+sz[rt<<1|1];
        tr[rt]=Add(tr[rt<<1],tr[rt<<1|1]);
    }
    void build(res rt,res l,res r){
        laz[rt]=1;
        if(l==r){
            for(res i=30;~i;i--)if((a[l]>>i)&1){tr[rt]=1<<i;break;}
            sz[rt]=a[l]-tr[rt];
            return;
        }
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);
        pushup(rt);
    }
    void modify(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R){change(rt,2);return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify(rt<<1,l,mid,L,R);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R);
        pushup(rt);
    }
    void modify_dec(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R&&!sz[rt]){change(rt,0);return;}
        if(l==r){sz[rt]&=sz[rt]-1;return;}
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify_dec(rt<<1,l,mid,L,R);
        if(R>mid)modify_dec(rt<<1|1,mid+1,r,L,R);
        pushup(rt);
    }
    int query(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R)return int((tr[rt]+sz[rt])%kcz);
        pushdown(rt);
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=query(rt<<1,l,mid,L,R);
        if(R>mid)add(ret,query(rt<<1|1,mid+1,r,L,R));
        pushup(rt);
        return ret;
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read();
            for(res i=1;i<=n;i++)a[i]=read();
            build(1,1,n);
            res q=read();
            while(q--){
                res opt=read(),l=read(),r=read();
                if(opt==1)printf("%d\n",query(1,1,n,l,r));
                else if(opt==2)modify_dec(1,1,n,l,r);
                else modify(1,1,n,l,r);
            }
        }
    }
}

[1005 Separated Number]

solution

题面：一个长度为 的数字，问分割成小于等于 段的数之和的和。

做法：我开始想的直接 ，结果怎么优化都是 的。然后就放手给廷廷做了。

实际上考虑每个点的贡献，枚举它在第 位，那么第 位的数的总贡献就是

$$a_i(\sum_{j=0}^{n-i-1}10^j\sum_{m=0}^{k-2}\binom{n-j-2}{m}+10^{n-i}\sum_{m=0}^{k-1}\binom{i-1}{m})$$

发现瓶颈在 是固定的。

当时廷廷问我这个怎么求，我也不知道为什么他不会（bushi）。 固定是存在递推式的，就只要前者乘 ，再一一配对就可以出来了。当然如果 固定就是基础的 ， 维护下即可。

复杂度 。

//2021.8.29 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+10;
namespace MAIN{
    int k;
    char str[N];
    int n;
    int fac[N],inv[N];
    inline int C(const res &x,const res &y){
        return mul(fac[x],mul(inv[y],inv[x-y]));
    }
    int f[N],g[N],pw[N],p[N],p2[N];
    inline void MAIN(){
        fac[0]=fac[1]=inv[0]=inv[1]=pw[0]=p2[0]=1;
        for(res i=1;i<=N-10;i++)pw[i]=mul(pw[i-1],10),p2[i]=Add(p2[i-1],p2[i-1]);
        for(res i=2;i<=N-10;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        for(res i=2;i<=N-10;i++)inv[i]=mul(inv[i-1],inv[i]);
        res Case=read();
        while(Case--){
            k=read(),scanf("%s",str+1),n=int(strlen(str+1));
            res ans=0;
            if(k==1){
                for(res i=1;i<=n;i++)add(ans,mul(str[i]-'0',pw[n-i]));
                printf("%d\n",ans);
                continue;
            }
            for(res i=0;i<=k-2;i++)f[i]=g[i]=p2[i];
            g[k-1]=p2[k-1],f[k-1]=Add(Add(f[k-2],f[k-2]),kcz-1);
            for(res i=k;i<=n;i++)f[i]=Add(Add(f[i-1],f[i-1]),kcz-C(i-1,k-2)),g[i]=Add(Add(g[i-1],g[i-1]),kcz-C(i-1,k-1));
            for(res i=1;i<=n;i++)p[i]=Add(p[i-1],mul(pw[i-1],f[n-i-1]));
            for(res i=1;i<=n;i++)add(ans,mul(str[i]-'0',Add(p[n-i],mul(pw[n-i],g[i-1]))));
            printf("%d\n",ans);
        }
    }
}

[1006 GCD Game]

solution

题面：两人在博弈，有 堆石子，操作是选取一个任意的 使 。问谁先手胜。

做法：平等博弈，直接求 函数，发现 ，于是预处理好就结束了。另外一种理解是把 看成 的质因数个数，那这题就是 博弈了。

//2021.8.12 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e7+10;
namespace MAIN{
    int prim[N/10],tot,mn[N],sg[N];
    bool vis[N];
    inline void MAIN(){
        for(res i=2;i<=N-10;i++){
            if(!vis[i])prim[++tot]=i,mn[i]=i;
            for(res j=1;j<=tot&&prim[j]*i<=N-10;j++){
                vis[prim[j]*i]=1,mn[prim[j]*i]=prim[j];
                if(i%prim[j]==0)break;

            }
        }
        sg[1]=0;
        for(res i=2;i<=N-10;i++){
            sg[i]=sg[i/mn[i]]+1;
        }
        res Case=read();
        while(Case--){
            res n=read(),ret=0;
            for(res i=1;i<=n;i++)ret^=sg[read()];
            puts(ret?"Alice":"Bob");
        }
    }
}

[1007 A Simple Problem]

solution

题面：一个长度为 的序列 初始值都为 ，给定一个数 ，现有两个操作：一是 区间加 ，二是给出 ，询问

$$\min_{i=l}^{r-k+1}(\max_{j=i}^{i+k-1} A_j),r-l+1\geq k$$

做法：首先要注意到一个重要的性质，合并相邻区间的答案是可以二分的。

准确来说，我们想查找 的答案，是可以从 这两个区间合并时二分得来的。在 和 部分的答案可以在原来的区间维护好，现考虑跨过 的情况。我们二分 ，比较 与 的大小关系，当左大于右时， 更小是一定不优的，因为此时的答案取决于左，而左只会不减。左不大于右同理。于是我们就设计了这样一个二分，做到了在 的时间内合并两个区间。

重新回到这道题，利用上述二分，我们直接用动态开点线段树维护整个序列，合并时利用二分就可以做到 了。

官方题解做法实在有点麻烦，它是将整个序列分成了每段长度为 的小块，然后利用这些小块分别建线段树，由于这些线段树形态一致，因此可以直接在线段树上二分来求出小块间的答案，于是就降下了两个 。

实现上，为了减少下传标记的麻烦（因为有两种维护不同信息的线段树），我使用了标记永久化（其实是懒得写了，照抄了一下）。

//2021.9.1 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100000*30+10;
namespace MAIN{
    int n,k,q,d;
    int ls[N],rs[N],rt,tot;
    int par[N],laz[N],onl[N],all[N];
    inline void change(const res &rt,const res &v){
        par[rt]+=v,onl[rt]+=v,laz[rt]+=v,all[rt]+=v;
    }
    void modify(res &rt,res l,res r,const res &L,const res &R,const res &v){
        if(!rt)rt=++tot;
        if(L<=l&&r<=R){change(rt,v);return;}
        res mid=(l+r)>>1;
        if(L<=mid)modify(ls[rt],l,mid,L,R,v);
        if(R>mid)modify(rs[rt],mid+1,r,L,R,v);
        onl[rt]=max(onl[ls[rt]],onl[rs[rt]])+laz[rt];
    }
    inline int solve(res rt,res l,res r,const res &L,const res &R){
        res mid=(l+r)>>1,l1=l,r1=mid,rt1=ls[rt],rt2=rs[rt],l2=mid+1,r2=r,tg1=laz[rt1],tg2=laz[rt2],s=inf,o=-inf,fl=0;
        while(l1!=r1)rt1=rs[rt1],tg1+=laz[rt1],l1=((l1+r1)>>1)+1;
        while(l2!=r2)rt2=ls[rt2],tg2+=laz[rt2],r2=(l2+r2)>>1;
        l=0,r=k-1;
        while(l<r){
            mid=(l+r)>>1;
            if(L<=mid+1&&mid+1<=R)s=min(s,max(o,max(tg1+onl[rs[rt1]],tg2+onl[ls[rt2]])));
            if(R<mid+1)fl=0;
            else{
                if(mid+1<L)fl=1;
                else fl=tg1+onl[rs[rt1]]>=tg2+onl[ls[rt2]];
            }
            if(fl)o=max(o,tg2+onl[ls[rt2]]),l=mid+1,rt1=rs[rt1],rt2=rs[rt2];
            else o=max(o,tg1+onl[rs[rt1]]),r=mid,rt1=ls[rt1],rt2=ls[rt2];
            tg1+=laz[rt1],tg2+=laz[rt2];
        }
        return s;
    }
    void modify1(res &rt,res l,res r,const res &L,const res &R,const res &v){
        if(!rt)rt=++tot;
        if(L<=l*k&&r*k+k-1<=R){change(rt,v);return;}
        if(l==r){modify(rt,l*k,r*k+k-1,L,R,v),par[rt]=onl[rt];return;}
        res mid=(l+r)>>1;
        if(L<=mid*k+k-1)modify1(ls[rt],l,mid,L,R,v);
        if(R>=(mid+1)*k)modify1(rs[rt],mid+1,r,L,R,v);
        onl[rt]=max(onl[ls[rt]],onl[rs[rt]])+laz[rt];
        if(L<=mid*k&&(mid+1)*k+k-1<=R)all[rt]+=v;
        else if(L<=(mid+1)*k+k-1||mid*k<=R)all[rt]=solve(rt,l,r,0,k-1)+laz[rt];
        par[rt]=min(min(par[ls[rt]],par[rs[rt]])+laz[rt],all[rt]);
    }
    int query(res rt,res l,res r,const res &L,const res &R){
        if(R<l*k+k-1||r*k<L)return inf;
        if(!rt)return 0;
        if(L<=l*k&&r*k+k-1<=R)return par[rt];
        if(l==r)return inf;
        res mid=(l+r)>>1,o;
        if(R<=mid*k+k-1)return query(ls[rt],l,mid,L,R)+laz[rt];
        if((mid+1)*k<=L)return query(rs[rt],mid+1,r,L,R)+laz[rt];
        if(mid*k<L||R<(mid+1)*k+k-1)o=solve(rt,l,r,max(0,L-mid*k),min(k-1,R-(mid+1)*k+1))+laz[rt];
        else o=all[rt];
        return min(o,min(query(ls[rt],l,mid,L,R),query(rs[rt],mid+1,r,L,R))+laz[rt]);
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),k=read(),q=read(),d=(n-1)/k,n=(d+1)*k;
            for(res i=1;i<=tot;i++)ls[i]=rs[i]=all[i]=onl[i]=laz[i]=par[i]=0;
            rt=tot=0;
            while(q--){
                res op=read(),l=read()-1,r=read()-1;
                if(op==1){
                    res x=read();
                    modify1(rt,0,d,l,r,x);
                }
                else printf("%d\n",query(rt,0,d,l,r));
            }
        }
    }
}

[1008 Square Card]

solution

题面：两个圆，随机丢一个长度为 的正方形，问当这个正方形在一个圆中时在另一个圆中的概率。定义在一个圆中是看正方形旋转到一个位置在圆中。

做法：正方形肯定是正对着最好，那剩下来的就是圆的面积交。

//2021.8.29 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    db xa,ya,ra,xb,yb,rb,t,d,ans;
    inline void MAIN(){
        res Case=read();
        while(Case--){
            scanf("%lf%lf%lf%lf%lf%lf%lf",&ra,&xa,&ya,&rb,&xb,&yb,&t),t/=2;
            if(rb<sqrt(2)*t)ans=0;
            else {
                ra=sqrt(ra*ra-t*t)-t,rb=sqrt(rb*rb-t*t)-t,d=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
                if(d>=ra+rb)ans=0;
                else if(d<=ra-rb)ans=(rb*rb)/(ra*ra);
                else if(d<=rb-ra)ans=1;
                else {
                    t=acos((d*d+ra*ra-rb*rb)/(2*d*ra));
                    ans=-sin(t)*ra*d+ra*ra*t;
                    t=acos((d*d+rb*rb-ra*ra)/(2*d*rb));
                    ans+=rb*rb*t;
                    ans/=pi*ra*ra;
                }
            }
            printf("%.6lf\n",ans);
        }
    }
}

[1009 Singing Superstar]

solution

题面：一个长度为 的字符串，多次询问一个串，问这个串在大串里不相交的最多出现次数。

做法：注意到小串长度小于等于 ，直接暴力枚举每个长度小于等于 的串，预处理下就是线段不交问题，贪心即可。复杂度 。

这些都用 维护就是正常复杂度，我懒了，写个 ，就多个 ，好像过不太去。

//2021.8.28 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    char s[N];
    int q,n;
    map<string,int> M;
    inline int solve(const RG string &t,const res &len){
        res ax=0;
        for(res i=1;i<=n-len+1;){
            RG string o;
            for(res j=i;j<=i+len-1;j++)o.pb(s[j]);
            if(o==t){
                i+=len;
                ax++;
            }
            else i++;
        }
        return ax;
    }
    int a[N*30];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            scanf("%s",s+1),n=int(strlen(s+1)),q=read(),map<string,int>().swap(M);
            res idx=0;
            for(res l=1;l<=30;l++){
                for(res i=1;i<=n-l+1;i++){
                    RG string t;
                    for(res j=i;j<=i+l-1;j++)t.pb(s[j]);
                    if(M[t])continue;
                    M[t]=++idx,a[idx]=solve(t,l);
                }
            }
            while(q--){
                scanf("%s",s+1),n=int(strlen(s+1));
                RG string t;
                for(res i=1;i<=n;i++)t.pb(s[i]);
                if(!M[t])puts("0");
                else printf("%d\n",a[M[t]]);
            }
        }
    }
}

[1010 Yinyang]

solution

题面：每个点要么染成黑色要么染成白色，黑色和白色必须成一个连通块，同时一个小正方形不能为同一个颜色，问染色方案数。

做法：插头 ，用最小表示法或者括号序列都能过。复杂度 。

注意一些基础的卡常技巧，比如三进制用四进制表示之类的。

//2021.8.31 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
const int M=2e5+10;
const int ljc=199999;
namespace MAIN{
    int n,m;
    int a[N][N],b[N][N];
    struct Hash{
        int cnt,head[M];
        struct E{
            int next,col,s,f;
            E() {}
            E(res next,res col,res s,res f):next(next),col(col),s(s),f(f) {}
        }edge[M];
        inline void init(){
            cnt=-1,memset(head,-1,sizeof(head));
        }
        inline void push(const res &s,const res &col,const res &val){
            res u=s%ljc;
            for(res i=head[u];~i;i=edge[i].next)if(edge[i].s==s&&edge[i].col==col){add(edge[i].f,val);return;}
            edge[++cnt]=E(head[u],col,s,val),head[u]=cnt;
        }
    }dp[2];
    int cur;
    int sig[N],num[N];
    inline void get(res s){
        for(res i=m-1;~i;i--)sig[i]=s&7,s>>=3;
    }
    inline int zip(){
        for(res i=0;i<=m;i++)num[i]=-1;
        res k=-1,ret=0;
        for(res i=0;i<m;i++){
            if(num[sig[i]]==-1)num[sig[i]]=++k;
            ret=(ret<<3)|num[sig[i]];
        }
        return ret;
    }
    inline void change(res x,res y){
        for(res i=0;i<m;i++)if(sig[i]==x)sig[i]=y;
    }
    inline void f(const res &x,const res &y,const res &c){
        for(res i=0;i<=dp[cur].cnt;i++){
            res col=dp[cur].edge[i].col;
            res U=0,L=0;
            if(x>0)U=(col>>y&1)==c;
            if(y>0)L=(col>>(y-1)&1)==c;
            res UL=(col>>m)==c;
            if(L&&UL&&U)continue;
            if(x==n-1&&y==m-1&&!U&&!L&&UL)continue;
            get(dp[cur].edge[i].s);
            if(x>0&&!U){
                res s1=0,s2=0;
                for(res t=0;t<m;t++){
                    if(sig[t]==sig[y])s1++;
                    if((col>>t&1)!=c)s2++;
                }
                if(s1==1&&(s2>1||x<n-1||y<m-2))continue;
            }
            if(U&&L){if(sig[y]!=sig[y-1])change(sig[y],sig[y-1]);}
            else if(!U&&L)sig[y]=sig[y-1];
            else if(!U)sig[y]=m;
            if(col&(1<<y))col|=1<<m;
            else col&=~(1<<m);
            if(c)col|=1<<y;
            else col&=~(1<<y);
            dp[cur^1].push(zip(),col,dp[cur].edge[i].f);
        }
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),m=read();
            for(res i=0;i<n;i++)for(res j=0;j<m;j++)a[i][j]=read();
            if(n<m){
                for(res i=0;i<n;i++)for(res j=0;j<m;j++)b[j][i]=a[i][j];
                swap(n,m);
                for(res i=0;i<n;i++)for(res j=0;j<m;j++)a[i][j]=b[i][j];
            }
            dp[cur=0].init(),dp[0].push(0,0,1);
            for(res i=0;i<n;i++)for(res j=0;j<m;j++){
                dp[cur^1].init();
                if(a[i][j]!=0)f(i,j,0);
                if(a[i][j]!=1)f(i,j,1);
                cur^=1;
            }
            res ret=0;
            for(res i=0;i<=dp[cur].cnt;i++){
                res mx=0;
                get(dp[cur].edge[i].s);
                for(res j=0;j<m;j++)mx=max(mx,sig[j]);
                if(mx>1)continue;
                add(ret,dp[cur].edge[i].f);
            }
            printf("%d\n",ret);
        }
    }
}