数位dp

f[i][st][w1][w2]表示到第i位，这一位a,b,c,d的数是否分别要小于ABCD的状态st，w1表示前一位a+c-b-d为几，w2表示a+d-b-c为几

由于前一位差大于等于2后，后面能始终确保a+c>b+d，所以w1, w2状态只有-1,0,1,2四种

注意这时如果按十进制诸位考虑，复杂度为18*9^4*16*4*4会超时

而逐二进制位复杂度为61*2^4*16*4*4，如此可过

1 #include
      
        2  3 using namespace std; 4 typedef long long ll; 5 const int mo=1e9+7; 6 int f[62][16][4][4],g[4][62]; 7 ll a,b,c,d; 8  9 int dfs(int i,int st,int w1,int w2)10 {11     if (i==-1)12     {13         if (w1>=2&&w2>=1) return 1;14         else return 0;15     }16     if (f[i][st][w1][w2]>-1) return f[i][st][w1][w2];17     int s=0,r[4];18     for (int j=0; j<4; j++) r[j]=((st>>j)&1)?1:g[j][i];19     for (int a0=0; a0<=r[0]; a0++)20         for (int b0=0; b0<=r[1]; b0++)21             for (int c0=0; c0<=r[2]; c0++)22                 for (int d0=0; d0<=r[3]; d0++)23                 {24                     int nw=st,q1,q2;25                     int l=a0+c0+(w1-1)*2-b0-d0;26                     if (l<-1) continue; else q1=(l>1)?2:l;27                     l=a0+d0+(w2-1)*2-b0-c0;28                     if (l<-1) continue; else q2=(l>1)?2:l;29                     if (a0