>>117
シャッフルは要らない。n本のくじの中にm本の当たりがある場合と同じ。
それを配列番号1からn番まで引く。くじ引きは何番目に引こうが当たりが出る確率は等確率。
>>111も確かにO(N)だな。ソートと勘違いしてた。
だけどくじ方式の場合は逐一頭から取り出す場合は配列を用意する必要はないし、
必要な分だけ計算すればいい。

int array[n];
for (size_t i=0; i<n; ++i) {
bool hit = m/(n-i)の確率のrand;
if (hit) {
--m;
array[i] = 1;
} else {
array[i] = 0;
}
}