数位dp D - Count The Bits
发布时间:2020-12-14 04:35:58 所属栏目:大数据 来源:网络整理
导读:题目:D - Count The Bits 博客?? ? ? #include cstdio#include cstring#include cstdlib#include algorithm#include queue#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;const int mod = 1000000009;ll dp[130][1010][130]; //dp[i][j][
题目:D - Count The Bits 博客?? ? ? #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <queue> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int mod = 1000000009; ll dp[130][1010][130]; //dp[i][j][k] 其中i代表第i位,j代表这个数的大小,因为我是要k的倍数,所以对k进行取膜即可,k就是表示这数化成二进制含有1的个数 int k,b; ll dfs(int pos,int num,int sum,bool limit) { if (pos == -1) return num ? 0 : sum; if (!limit&&dp[pos][num][sum] != -1) return dp[pos][num][sum]; ll ans = 0; for(int i=0;i<=1;i++) { ans += dfs(pos - 1,(num * 2 + i) % k,sum + i,limit&&i); ans %= mod; } if (!limit) dp[pos][num][sum] = ans; return ans; } ll solve() { return dfs(b - 1,true); } int main() { scanf("%d%d",&k,&b); memset(dp,-1,sizeof(dp)); printf("%I64dn",solve()); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |