Codeforces Round #189 Div1A Malek Dance Club
問題
ダンスクラブが2つあって、どちらも0から2^n-1までのIDをもった2^n人の人がいます。
ある数字xが(leading-zeroを含む2進数形式で)与えられ、
クラブAでIDがaのひとは、クラブBでIDが(a xor x)の人とペアになります。
クラブAでIDがaのひととクラブBでIDがbのひとがペアになるのを(a,b)と表すことにします。
2組のペア(a,b),(c,d)について、 a<c かつ b>d となる組(複雑な組)の数を求めなさい。
解法
クラブAのひとのIDを昇順に並べたとき、対応するクラブBのひとのIDは、
上半分と下半分で下位n-1ビットの並びは全く同じ並びを二度繰り返しています。
たとえば、xが1のときと01のときを考えると
x="1" A |B --+-- 0 | 1 1 | 0 x="01" A |B --+-- 00|01 01|00 10|11 11|10
というように、下位ビットでは1->0という並びが二度繰り返され、
その間最上位ビットは中央で1回だけ変わっています。
というわけで、xの最上位ビットが0であれば、下位ビットの同じ並びが二度繰り返されるので、
下位n-1ビットの複雑な組の数を2倍すればよさそうです。
さらに、xの最上位ビットが1のときはそれに加えて
(前半分のどれか),(後ろ半分のどれか)は最上位ビットが1から0になるので、必ず逆転が起きます。そのため、さらに(2^(n-1))^2の組を加えます。
下位の方のビットから1ビットずつこれを再帰的に計算していくことで答えが求まります。
xは2進数で100ケタで、余裕でオーバーフローする数なのであらゆる場所にMODを取るのをお忘れなく。
//本番では忘れて2回出しなおしたんですよね、これが・・・
プログラム
#include<iostream> #include <fstream> #include <stdio.h> #include <stdlib.h> #define _USE_MATH_DEFINES #include <math.h> #include<string> #include<vector> #include<cmath> #include<stack> #include<queue> #include<sstream> #include<algorithm> #include<map> #include<complex> using namespace std; #define li long long int #define rep(i,to) for(int i=0;i<((int)(to));i++) #define repp(i,start,to) for(int i=(int)(start);i<((int)(to));i++) #define pb push_back #define sz(v) ((li)(v).size()) #define bgn(v) ((v).begin()) #define eend(v) ((v).end()) #define allof(v) (v).begin(), (v).end() #define dodp(v,n) memset(v,(li)n,sizeof(v)) #define bit(n) (1ll<<(li)(n)) #define mp(a,b) make_pair(a,b) #define rin rep(i,n) #define EPS 1e-10 #define ETOL 1e-8 #define MOD 1000000007 #define p2(a,b) cout<<a<<"\t"<<b<<endl #define p3(a,b,c) cout<<a<<"\t"<<b<<"\t"<<c<<endl int main(){ string x; cin>>x; li n=sz(x); li res=0; li two=1; rep(i,n){ if(x[n-i-1]=='0')res=(res*2)%MOD; else{ res=(res*2+two*two)%MOD; } two=(two*2)%MOD; } cout<<res%MOD<<endl; return 0; }