#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(vec[i]) << " "; } return os; } constexpr long long mask0 = 0xdb6db6dbLL; //0b000000011011011011011011011011011011011LL; constexpr long long mask1 = 0x49249249LL; //0b000000001001001001001001001001001001001LL; constexpr long long mask2 = 0x124924924LL; //0b000000100100100100100100100100100100100LL; constexpr long long mask3 = 0x104104104LL; //0b000000100000100000100000100000100000100LL; //0b000000001100001100001100001100001100001LL; constexpr long long mask4 = 0x60060060LL; //0b000000001100000000001100000000001100000LL; //0b000000000000111100000000111100000000111LL; constexpr long long mask5 = 0x7800007800LL; //0b111100000000000000000000111100000000000LL; //0b000000000000111100000000000000001111111LL; constexpr long long mask6 = 0x7F800000LL; //0b000000001111111100000000000000000000000LL; 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 = 0b00000000011000011000011000011000011000011000LL; //0b00000000001111001111001111001111001111001111LL; constexpr long long maskB = 0b00000000001111000000001111000000001111000000LL; //0b00000000000011111111000011111111000011111111LL; constexpr long long maskC = 0b11111111000000000000000011111111000000000000LL; //0b00001111111111111111000000001111111111111111LL; constexpr long long maskD = 0b00001111111111111111000000000000000000000000LL; constexpr long long maskE = 0b00000000000000000000000000001111111111111111LL; 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; } void dfs(vector& memo, int pos, int c, long long val){ if(pos == c){ //propagate long long val_ = compress_A(val); long long hoge = val + mask1; //make 4 hoge = hoge&mask2; //find carry val = val + (hoge<<1); //left shift hoge = val&mask2; //find carry hoge = hoge | (hoge>>1) | (hoge>>2); val ^= hoge; //flip 4 val &= cmask; hoge = val + mask1; //right hoge = hoge&mask2; val = val + (hoge>>5); hoge = val&mask2; hoge = hoge|(hoge>>1)|(hoge>>2); val ^= hoge; val &= cmask; 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*3))); } } #include int main(){ int r,c; cin >> 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(1<<(c*2), 0); dfs(memo, 0,c, 0); vector Prob(1< Prob_(1< dp(1< dp_(1<>j)&1)?p[i][j]:100-p[i][j]) * 0.01; if((w>>j)&1){ state += max(0,3-s[i][j]) << (3LL*j); } } for(int v=0; v<(1<>1)|(hoge>>2); int next = memo[compress_A(state_)]; int cnt = __builtin_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<