本番なかなか解が合わず手間取った。
https://yukicoder.me/problems/no/685
問題
正整数Nが与えられる。
(x,y)の整数対のうち、0≦x≦y≦Nかつ(x and y)<(x xor y)<(x or y)を満たすものは何通りあるか。
解法
x,yが1bitの場合、不等号を満たす条件を考える。
(x and y)<(x xor y)が生じるのは、x!=yの場合である。
そこでx≦yという条件で考えると、yの最上位ビットにおいて、xの同じビットが0であればよい。
つぎに(x xor y)<(x or y)が生じるのはx=y=1の場合のみである。
yの最上位ビットと同じ位置においてxのビットは0であることは確定しているので、それより下のビットでx=y=1となる箇所が1か所でもあれば、以下のビットはなんであれ条件を満たす。
この2つの考察を元に、DPなりメモ化再帰で上のビットから決めていくことを考えよう。
yについて以下0/1任意の値を取れるか、もしくは「N以下」の条件により0/1の値が制限されるかを考慮しつつ、桁DPでx,yに0/0,0/1,1/0,1/1の値を取ったときの遷移を考えていく。
ll N; ll mo=1000000007; map<ll,ll> M[2],R[2]; ll hoge2(ll a,int lead) { if(a==0) return 0; if(R[lead].count(a)) return R[lead][a]; ll ret=0; if(lead==1) { if(N&a) { // 11 ret+=((N&(a-1))+1)%mo*(a%mo)%mo; // 10 ret+=hoge2(a>>1,1); // 00,01 ret+=2*hoge2(a>>1,0); } else { // 00,01 ret+=2*hoge2(a>>1,1); } } else { // 11 ret+=a%mo*(a%mo)%mo; // 10,01,00 ret+=3*hoge2(a>>1,0); } //cout<<"R"<<lead<<" "<<a<<" "<<ret%mo<<endl; return R[lead][a]=ret%mo; } ll hoge1(ll a,int lead) { if(a==0) return 0; if(M[lead].count(a)) return M[lead][a]; ll ret=0; if(lead==1) { if(N&a) { // 10 ret+=hoge2(a>>1,1); // 00 ret+=hoge1(a>>1,0); } else { // 00 ret+=hoge1(a>>1,1); } } else { // 00 ret+=hoge1(a>>1,0); // 10 ret+=hoge2(a>>1,0); } //cout<<"M"<<lead<<" "<<a<<" "<<ret%mo<<endl; return M[lead][a]=ret%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; cout<<hoge1(1LL<<60,1)<<endl; return; ll ret=0; for(i=1;i<=N;i++) { for(y=1;2*y<=i;y<<=1) if(i&y) ret+=y; cout<<ret<<endl; } cout<<ret<<endl; for(y=0;y<=N;y++) { int num=0; for(x=0;x<=y;x++) { if((x&y)<(x^y) && (x^y)<(x|y)) { //cout<<x<<" "<<y<<" "<<(x&y)<<" "<<(x^y)<<" "<<(x|y)<<endl; num++; } } cout<<y<<" "<<num<<" "<<__builtin_popcount(y)<<endl; } }
まとめ
桁DP系、ほんと説明がめんどい。