c++ - ブルートフォースを使用せずに、先行ゼロのない数値(文字列S)の順列が11で割り切れる数を見つける方法は?

Question

文字列S = {2,0,9,0}があるとします。条件を満たす値は2009、 2090、2900、9002、9020、および9200です (S = {2,0,9,0} のすべての順列)。その中で、2090 と 9020 だけが 2 番目の条件 (11 で割り切れる) を満たすため、S = {2,0,9,0} の答えは2です。

文字列 S が最大 100 桁になるとしたら? ブルートフォースは決して終わらないでしょう。

前もって感謝します。

Answer 1

総当たりで、n！考慮する文字列。

数字について重要なのは、それが奇数か偶数の位置にあるかどうかだけであることに気付いた場合、それは n!/(n/2)! に減少します。² .

次に、可能な桁数がそれほど多くないことを思い出します。各数値がいくつあるかを数えることができます。その後、それぞれの可能なすべてのパーティションを 2 つのビン (奇数と偶数の位置) に反復処理するだけです。これにはコストがかかりますが、完全に手に負えないわけではありません。

文字列が非常に大きく、数千桁の場合、どちらのビンでも 11 桁の同じ数字はゼロに相当するという事実を考慮する価値がありますが、わずか 100 桁の場合、おそらく努力する価値はありません。

特定のパーティションが 11 で割り切れる数に対応することを確認したら、1 つのビン内のすべての数字を使用可能なすべての位置 (O(1)) に配置する方法を数えることができます。