将三进制当成二进制搞搞就好

#include
     
      #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i) using namespace std;template
      
       inline void rd(T&x){     char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;} ll n,m,K,f[10005][100],sta[250],mod=1000000;//判断当前状态是否合法 inline bool judge(int x){    int tmp=4;    inc(i,1,m)    {        if(tmp==x%3)re 0;        tmp=x%3;x/=3;    }    re 1;}//判断当前状态与上一行状态是否互配 inline bool check(int x,int y){        inc(i,1,m)    {        if(x%3==y%3)re 0;        x/=3,y/=3;    }         re 1;}int main(){        rd(n),rd(m);rd(K);    ll tot=1,now=0,x,pos=0,cnt=0;        inc(i,1,m)tot*=3;    inc(i,0,tot-1)        if(judge(i))sta[++cnt]=i;//弄出三进制所有状态，并判断合法性         inc(i,1,m)    {        rd(x);        now=now*3+x-1;    }    inc(i,1,cnt)if(sta[i]==now){        pos=i;        break;    }     if(!pos){        printf("0");        re 0;    }    //判断已涂行是否合法         inc(i,1,n)    {        if(i==K)//已涂行         {            if(i==1)f[i][pos]=1;            else inc(j,1,cnt)            {                if(check(sta[pos],sta[j]))                    f[i][pos]=(f[i][pos]+f[i-1][j])%mod;            }        }                else //未涂行         {            if(i==1)            inc(j,1,cnt)f[i][j]=1;            else             {                inc(j,1,cnt)                inc(k,1,cnt)                if(check(sta[j],sta[k]))                f[i][j]=(f[i][j]+f[i-1][k])%mod;            }        }    }            ll ans=0;//统计答案     inc(i,1,cnt)    ans=(ans+f[n][i])%mod;        printf("%lld",ans);    re 0;}