TJOI 2019 简要题解

TJOI 2019 简要题解

#include#define N 55using namespace std;typedef long long ll;ll read(){ ll cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch=='-') f = -1; } while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}int T, d, typ; ll s, t;ll dp[2][N][N<<1];ll solve(ll sum, ll cnt, ll b1, ll b2){ ll mxb = 1; while((1ll << mxb) <= sum) ++mxb; for(int i = 0; i <= cnt; i++) dp[0][0][i] = dp[1][0][i] = 0; dp[0][0][0] = 1; for(int b = 1; b < mxb; b++){ sum >>= 1; for(int c = 0; c <= cnt; c++){ dp[0][b][c] = dp[sum&1][b-1][c]; dp[1][b][c] = 0; if(c && b < b1) dp[~sum&1][b][c] += dp[~sum&1][b-1][c-1]; if(c && b < b2) dp[~sum&1][b][c] += dp[~sum&1][b-1][c-1]; if(c && b < b1 && b < b2) dp[1][b][c] += dp[sum&1][b-1][c-2]; } } return dp[0][mxb-1][cnt];}ll lca(ll x, ll y){ while(x^y){ if(x>= 1;} return x;}ll pc(ll x){ ll ret = 0; while(x) x -= x&-x, ++ret; return ret;}ll calc(ll x){ return (x << 1) - pc(x);}int main(){ T = read(); while(T--){ d = read(), s = read(), t = read(), typ = read(); ll p = lca(s, t); ll sum = calc(s) + calc(t) - calc(p) - calc(p >> 1); if(typ == 1){ cout << sum << '\n'; continue;} ll ans = 0; for(int i = 0; i < d; i++){ for(int j = 0; j < d; j++){ ll ss = (1ll << i + 1) + (1ll << j + 1) - 3; if(sum < ss) break; ll pos = sum / ss; int l = 0; while(pos){ pos >>= 1; ++l; } if(l + i > d || l + j > d) continue; ll k = sum % ss - (1ll << j) + 1; if(k < 0) continue; for(int t = k&1; t <= i+j; t+=2) ans += solve(k + t, t, i, j); } } cout << ans - 1 << '\n'; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。