- Quiz
- AC
- 解説
- ビットごとに考える
- nが奇数の時
- 等号しか作れない
- nが偶数の時
- 大なりになる列iを全探索
code
void solve(){ ll n,k;cin>>n>>k; if(n%2==0){ // even mint sum = 0; // & == xor // 等号が成り立つ場合の数--- // equalになる各列 // 001111 // 000011 // などなら、両辺共に0になる mint equal = 0; for(int i=2; i<=n; i+=2){ equal += nCr(n,i); } // それがk列ある sum += equal.pow(k); // 等号が成り立つ場合の数---ここまで // & > xor // 大なり分の場合の数---ここから // 1列を0にする場合の数 mint zero_column = 0; // 000000 // 000011 // 001111 など for(int i=2; i<=n; i+=2){ zero_column += nCr(n,i); } mint two=2; mint free = two.pow(n); // 1列に0,1を自由に置く場合の数は2^n mint bigger_sum=0; // 何列目でbiggerを確定させるかを全探索 rep(i,k){ // i列目でbiggerを確定させる mint a = zero_column.pow(i); // i-1列までは各列、&もxorも0 //a *= 1; // i列目は111111で確定 a *= free.pow(k-i-1); // i+1列以降は自由 bigger_sum += a; } sum += bigger_sum; p(sum.x); } else{ // odd // equal only // 111で1にしてequalにするか // 110で0にするか(0の個数が奇数) nC1 + nC3 + ... mint a = 1; // 111 for(int i=1; i<=n; i+=2){ // i:0の個数 a += nCr(n, i); } // それがビット数分(k)あるので mint ans = a.pow(k); p(ans.x); } } int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin>>N; prepare_nCr(); while(N--)solve(); return 0; }
other's tweet (C)
CF Round #737(Div2)
— m_99 (@m_99kyopro) August 9, 2021
A.最大の1個とそれ以外とで分ける
B.座圧して, kがa[i]+1!=a[i+1]となってる箇所+1以上か判定
C.nが奇数の時, 桁ごとに全部1か1が偶数個か
nが偶数の時, 上位bitから見て全部1となるところがあるか・あるならどこで初めてなるかで場合分け
C,
— laycrs (@laycrs) August 9, 2021
ある桁に着目して,そこで同じになるパターンは 1 が偶数個か,Nが奇数かつ全部1,でこれは二項係数で計算できる.
なので,イコールになる場合の数は,これのK乗で終わり.
Nが偶数なら,大なり,になることもあり,それはどこで大きくなるか一番上の桁を全探索して数え上げる. pic.twitter.com/JXrHeqHzTU