#include #include #include #include #include #include #include #include #include #include #include using namespace std; #include template ostream& operator << (ostream& os, vector vec){ for(int i=0; i 111 int compress_B(long long val){ val = (val+mask1)&mask2; //only carry(4) val = ((val&mask3)>>2) | (val&(mask3>>3)); val = ((val&mask4)>>4) | (val&(mask4>>6)); val = ((val&mask5)>>8) | (val&(mask5>>12)); val = ((val&mask6)>>16) | (val&(mask6>>24)); return val; } long long cmask; //0b00000000000011011011011011011011011011011011LL; constexpr long long maskA = 0b00011000011000011000011000011000011000011000LL; //0b00000000001111001111001111001111001111001111LL; constexpr long long maskB = 0b11000000001111000000001111000000001111000000LL; //0b00000000000011111111000011111111000011111111LL; constexpr long long maskC = 0b11111111000000000000000011111111000000000000LL; //0b00001111111111111111000000001111111111111111LL; constexpr long long maskD = 0b00001111111111111111000000000000000000000000LL; constexpr long long maskE = 0b00000000000000000000000000001111111111111111LL; //0b00000000000000000000001111111111111111111111LL; //011011011 -> 111111 int compress_A(long long val){ val = ((val&maskA)>>1) | (val&(maskA>>3)); val = ((val&maskB)>>2) | (val&(maskB>>6)); val = ((val&maskC)>>4) | (val&(maskC>>12)); val = ((val&maskD)>>8) | (val&maskE); return val; } long long propagate(long long val, int c){ long long ret_a = 0; { ret_a = val; int used = 0; for(long long i=0; i>i)&1) continue; if(((ret_a>>(3LL*i)) & 7LL) >= 3){ used |= 1<=0; i--){ if((used>>i)&1) continue; if(((ret_a>>(3LL*i)) & 7LL) >= 3){ used |= 1<=0; i--){ if(((ret_a>>(3LL*i)) & 7LL) >= 3){ ret_a &= ~(7LL<<(3*i)); ret_a += (3LL<<(3*i)); } } } return ret_a; } void dfs(vector& memo, int pos, int c, long long val){ if(pos == c){ //propagate long long val_ = compress_A(val); val = propagate(val,c); int next = compress_B(val); memo[val_] = next; return; } for(long long i=0; i<=3; i++){ dfs(memo, pos+1, c, val + (i<<(pos*3LL))); } } //00110011 -> 000 111 000 111 long long expander(long long val){ long long tmp=val; val = ((val&(maskD>>8))<<8) | (val&maskE); val = ((val&(maskC>>4))<<4) | (val&(maskC>>12)); val = ((val&(maskB>>2))<<2) | (val&(maskB>>6)); val = ((val&(maskA>>1))<<1) | (val&(maskA>>3)); //assert(tmp == compress_A(val)); return val; } long long unko(vector& memo, long long state, int c){ long long x = compress_A(state); if(memo[x] != -1) return memo[x]; long long val = propagate(state, c); int next = compress_B(val); return memo[x] = next; } void generate_memo(vector& memo, int c){ for(int i=0; i<(1<<(2*c)); ++i){ long long val = expander(i); long long val_ = compress_A(val); val = propagate(val,c); int next = compress_B(val); memo[val_] = next; } } int main(){ int r,c; //cin >> r >> c; scanf("%d%d", &r,&c); cmask = (1LL<<(3*c))-1; vector> p(r, vector(c)); for(int i=0; i> p[i][j]; } } vector> s(r, vector(c)); for(int i=0; i> s[i][j]; } } vector expand(1<>j)&1LL)<<(3LL*j); } expand[i] = val; } vector memo(1LL<<(c*2), -1); //dfs(memo, 0,c, 0); //generate_memo(memo, c); vector popcount(1LL< Prob(1< Prob_(1< dp(1< dp_(1<>j)&1)?p[i][j]:100-p[i][j]) * 0.01; if((w>>j)&1){ if(s[i][j]==4) zero |= 7LL<<(3LL*j); state |= max(0LL,4-s[i][j]-1LL) << (3LL*j); }else{ zero |= 7LL<<(3LL*j); } } if(tmp_p<1e-11)continue; for(int v=0; v<(1<>1)|(carry>>2); state_ &= ~zero; //state_ = compress_A(state_); //int next = memo[state_]; int next = unko(memo, state_, c); int cnt = popcount[next]; dp_[next] += (dp[v] + cnt * Prob[v]) * tmp_p; Prob_[next] += Prob[v] * tmp_p; } } swap(dp, dp_); swap(Prob, Prob_); } double ans = 0; for(int i=0; i<(1<