B. AND 0, Sum Big (Codeforces Round #716 (Div. 2))

問題

https://codeforces.com/contest/1514/problem/B

問題概要

整数nとkが与えられる。以下の条件をすべて満たすような長さnの配列がいくつあるか答えよ。

• すべての要素は0から2^k-1までの整数である
• すべての要素のビットごとのANDは0である
• すべての要素の合計は可能な限り大きくなければならない

考察

合計が可能な限り大きくなければならないという条件から、[2^k-1, 2^k-1, 2^k-1, ..., 2^k-1]という配列をまず考えます。2^k-1は2進法で表すと1がk個並んでいる数なので、このままではビットごとのANDをとっても0になりません。どこかを減らす必要があります。

ANDをとって0にならなければならないので、各ビットにつき最低1つは0が含まれている必要があり、合計が可能な限り大きくなければならないので2つ以上含まれていてはいけません。

各ビット毎に考えて、1つの0が含まれうる位置はn箇所考えられ、それがkビットあるので、求める組み合わせの数はn^kとなります。

#include <bits/stdc++.h>
using namespace std;
 
long long pow_mod(long long n, long long p, long long mod) {
    if (p == 0) {
        return 1;
    } else if (p % 2 == 1) {
        return pow_mod(n, p - 1, mod) * n % mod;
    } else {
        long long s = pow_mod(n, p / 2, mod);
        return s * s % mod;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        cout << pow_mod(n, k, 1000000007) << endl;
    }
}

反省

例えばn=4, k=3のときに0777, 1677, 2577, 3477という二箇所だけ0が動くパターンには気づいたのですが、6537のようにそれより多くの場所が変化するパターンに気づけず・・・。

答えを聞けばそりゃそうだとしかならないのですが、これが自分で気づけないのがなぁ・・・。