UVa 12410 Disable the Wand

問題

start以上end以下で以下の条件を満たす数の総和を求めよ。

• 2進法で書いたときに1の数がmaxone個以下
• 2進法で書いたときにIdeal Numberと違う桁がk個以下

制約条件

全ての入力は10^9以下の正の整数

方針

典型的な桁DP.
ある数n以下で条件を満たす数の総和を求められればいい。

dp[i][one][diff][mod][s]を、
i桁目まで見たときの、1の数がone個、ideal numberとの違いをdiff個、
21で割った余りがmodであり、
s = 1ならn未満になっていて、
s = 0ならそうでないときの総和。

これを更新していけばいい。
今までに至る場合の数も記憶しておいて、その分だけ次の桁を足す。

ソースコード

ll s, t, one, ideal, diff;
int lim[40], id[40];
ll dp[40][40][40][21][2];
ll way[40][40][40][21][2];
 
ll solve(ll l){
    rep(i, 32) lim[i] = l % 2, l /= 2;
    reverse(lim, lim + 32);
     
    memset(dp, 0, sizeof(dp));
    memset(way, 0, sizeof(way));
     
    way[0][0][0][0][0] = 1;
    rep(i, 32) rep(j, one + 1) rep(k, diff + 1) rep(l, 21) rep(m, 2){
        if(way[i][j][k][l][m]) rep(nxt, 2){
             
            if(!m && nxt > lim[i]) continue;
            int nj = j + nxt;
            int nk = k + (id[i] != nxt);
            int nl = (l * 2 + nxt) % 21;
            int nm = m || nxt < lim[i];
             
            if(nj > one || nk > diff) continue;
             
            dp[i + 1][nj][nk][nl][nm] += dp[i][j][k][l][m] * 2 + nxt * way[i][j][k][l][m];
            way[i + 1][nj][nk][nl][nm] += way[i][j][k][l][m];
        }
    }
    ll ans = 0;
    rep(i, one + 1) rep(j, diff + 1) rep(k, 21) rep(l, 2){
         
        if(k % 3 == 0 && k % 7)
        ans += dp[32][i][j][k][l];
    }
    return ans;
}
 
int main()
{
    int CS;
    cin >> CS;
    rep(cs, CS){
        cin >> s >> t >> one >> ideal >> diff;
         
        one = min(one, 33ll);
        diff = min(diff, 33ll);
         
        rep(i, 32) id[i] = ideal % 2, ideal /= 2;
        reverse(id, id + 32);
         
        ll ans = solve(t) - solve(s - 1);
        printf("Case %d: %lld\n", cs + 1, ans);
    }
    return 0;
}