CODE FESTIVAL 2018 qual A - C 半分 - Senの競技プログラミング備忘録

問題文

問題概要

長さN、要素が最大10^18の数列がある。あなたはK回、このうちの要素のうちの1つを選んで、それを2で割って商を切り捨てる。
K回操作を終えた時、数列のバリエーションを10^9+7で割ったあまりで求めよ。操作の手順が違っても最終的に同じならば同じとカウントする。

制約

N<= 50
K <= 10^9

ACするまで

1. 数学的な規則はなさそうな数え上げはDP。
2. 10^18 は大体2^60くらいなので、1つの数でたかだか60回の操作。それが50個あったとしてもたかだか3000回しか操作できなさそうだから、とっても大きいKは上限回の操作と言い換えてよい。
3. DPの漸化式は、前から順に何回操作するか、って感じでやる。ただし、一旦0を作った、もしくはもとからあったら最終的にmin(K, limit)回の操作をせずに余らせても、0で使い切ればいいので0ができたら場合分けだなー　(DPをかく)
4. 答えの集計で急に頭が働かなかった (は？)

5. 0で回数を余らせることができるかどうかを中心に考えればすぐにできる。

考察

ひとまず、それぞれの要素が0に至るまで何回の操作が必要か、
まずはすべての要素が十分に大きく、どの要素も0まで減らないとする。
この時、次のような簡単な動的計画法で実装できる。

ll dp[51][3000];
dp[0][0] = 1;
for(int i = 0; i < N; i++){
    for(int j = 0; j <= total_limit; j++){
        for(int use = 0; use <= limit[i] && j + use <= total_limit; use++){
            dp[i + 1][j + use] += dp[i][use];
        }
    }
}
cout << dp[N][K] << endl;//ここらへんはKの大きさで変わるけど

さて、0になりうる、もしくは最初から0が要素として含まれてる時を考えてみる。0を含んでないときはちょうどK回使い切らないといけなかったけど、0があれば、割った回数は関係なくなる。
つまり、動的計画法の状態で「前から何番目」、「何回操作した」、以外にも「0をここまで含んだかどうか」の2値フラグも持たせればよい。

dp[0][0][0] = 1;

for(int i = 0; i < N; i++){
    for(int j = 0; j <= total_limit; j++){
        for(int flg = 0; flg < 2; flg++){//flgが1ならすでに0を含んでる
            for(int use = 0; use <= limit[i] && j + use <= total_limit; use++){
                dp[i + 1][j + use][flg || use == limit[i]] += dp[i][use][flg];
                //もともとflgが立ってるものは立ってるモノに加算、たってないものも同様
                //ただし、i番目の数はlimit[i]操作すると0になるので、その時は0を作れたということで加算先のflgは1
            }
        }
    }
}