首页 > 代码库 > hdu 5106 Bits Problem(数位dp)
hdu 5106 Bits Problem(数位dp)
题目链接:hdu 5106 Bits Problem
题目大意:给定n和r,要求算出[0,r)之间所有n-onebit数的和。
解题思路:数位dp,一个ct表示个数,dp表示和,然后就剩下普通的数位dp了。不过貌似正解是o(n)的算法,但是n才
1000,用o(n^2)的复杂度也是够的。
#include <cstdio>
#include <cstring>
#include <algorithm>
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 < l; i++) {
for (int k = 0; k <= n; k++) {
if (ct[i][k] == 0)
continue;
for (int j = 0; j < 2; j++) {
if (j && k == 0)
continue;
ct[i+1][k-j] = (ct[i+1][k-j] + ct[i][k]) % mod;
dp[i+1][k-j] = (dp[i+1][k-j] + dp[i][k] + bit[l-i-1] * j * ct[i][k]) % mod;
}
}
for (int j = 0; j < s[i]-‘0‘; j++) {
ct[i+1][c-j] = (ct[i+1][c-j] + 1) % mod;
dp[i+1][c-j] = (dp[i+1][c-j] + sum + bit[l-i-1] * j) % mod;
}
if (s[i] == ‘1‘) {
sum = (sum + bit[l-i-1]) % mod;
c--;
}
}
return dp[l][0];
}
int main () {
bit[0] = 1;
for (int i = 1; i <= 1000; i++)
bit[i] = bit[i-1] * 2 % mod;
while (scanf("%d%s", &n, s) == 2) {
printf("%d\n", solve());
}
return 0;
}
hdu 5106 Bits Problem(数位dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。