[競プロ]p進数でのbit全探索

2進数での通常のbit全探索

n(割と小さめ)個のものがあり、それぞれに二つの状態があるとき、全探索をする際はいわゆる「bit全探索」を行うと思います。これは2ⁿ通りを全探索しています。競プロでは「使うor使わない」や「ON/OFF」などの文脈において全探索する際に便利です。
以下がコード例です。

for(int bit=0; bit<(1<<n); bit++){
    // 右からi番目にビットが立っているかどうか(2進数で表したときに1であるか)
    for(int i=0; i<n; i++){
        if(bit & (1<<i)){
            // i番目が1である
        }else{
            // i番目が0である
        }
    }
}

p進数でのbit全探索

2進数の時と同様に、n(割と小さめ)個のものがあり、それぞれにp個の状態がある時、pⁿ通りを全探索したい時があると思います。
例えば次の問題ではp=4(Aに使う・Bに使う・Cに使う・使わない)での全探索を行いたいです。

p進数を用いることで、すべての状態を探索すること
ができます。
以下がp進数でのbit全探索のコード例です。

int p=4;
for(int bit=0; bit<pow(p, n); bit++){
    int tmp=bit;
    vector<int> state(n);
    // 右からi(0~n-1)番目の状態(0~k-1)
    for(int i=0; i<n; i++){
        state[n-1-i]=tmp%p;
        tmp/=p;
    }
    // 各状態をチェック
    for(int i=0; i<n; i++){
        cout << state[i] << " ";
    }
    cout << endl;
}

これの出力は次のようになります

0 0 0 0 0  
0 0 0 0 1  
0 0 0 0 2  
0 0 0 0 3  
0 0 0 1 0  
0 0 0 1 1  
0 0 0 1 2  
0 0 0 1 3  
0 0 0 2 0  
0 0 0 2 1
.
.
.
3 3 3 2 0
3 3 3 2 1
3 3 3 2 2
3 3 3 2 3
3 3 3 3 0
3 3 3 3 1 
3 3 3 3 2
3 3 3 3 3

n個それぞれ0~3の全ての状態について探索できました。