hdu5106BitsProblem(数位dp)

题目链接：hdu 5106 Bits Problem

题目大意：给定n和r，要求算出[0,r)之间所有n-onebit数的和。

解题思路：数位dp，一个ct表示个数，dp表示和，然后就剩下普通的数位dp了。不过貌&＃20284;正解是o(n)的算法，但是n才

1000，用o(n^2)的复杂度也是够的。

#include 
#include 
#include 

using namespace std;

typedef long long ll;
const int mod = 1000000007;
const int maxn = 1005;

int n;
char s[maxn];
ll bit[maxn], dp[maxn][maxn], ct[maxn][maxn];

int solve () {
    memset(ct, 0, sizeof(ct));
    memset(dp, 0, sizeof(dp));

    int l = strlen(s), c = n;
    ll sum = 0;
    for (int i = 0; i for (int k = 0; k <= n; k&＃43;&＃43;) {
            if (ct[i][k] == 0)
                continue;

            for (int j = 0; j <2; j&＃43;&＃43;) {
                if (j && k == 0)
                    continue;

                ct[i&＃43;1][k-j] = (ct[i&＃43;1][k-j] &＃43; ct[i][k]) % mod;
                dp[i&＃43;1][k-j] = (dp[i&＃43;1][k-j] &＃43; dp[i][k] &＃43; bit[l-i-1] * j * ct[i][k]) % mod;
            }
        }

        for (int j = 0; j '0'; j&＃43;&＃43;) {
            ct[i&＃43;1][c-j] = (ct[i&＃43;1][c-j] &＃43; 1) % mod;
            dp[i&＃43;1][c-j] = (dp[i&＃43;1][c-j] &＃43; sum &＃43; bit[l-i-1] * j) % mod;
        }

        if (s[i] == '1') {
            sum = (sum &＃43; bit[l-i-1]) % mod;
            c--;
        }
    }

    return dp[l][0];
}

int main () {
    bit[0] = 1;
    for (int i = 1; i <= 1000; i&＃43;&＃43;)
        bit[i] = bit[i-1] * 2 % mod;
    while (scanf("%d%s", &n, s) == 2) {
        printf("%d\n", solve());
    }
    return 0;
}