当前位置： 首页 > news >正文

数位DP入门

news 来源：原创 2024/5/19 16:11:24

考试考dp的时候时常会碰见有关数位dp的问题，每次考到就是一脸懵逼加吃惊，所以今天抽空看了一下有关数位dp的知识，网上有很多大神都说的很好，推荐看几篇blog。
入门经典
慢慢看，很不错

数位DP的套路

数位dp其实看了那么多篇blog感觉就是一个套路，一个记忆化搜索，方法无非是用两个端点的答案相减得到答案。dp主要考得是状态的设定和转移及其优化，对于数位dp来说，转移和优化其实是固定的，变的只是状态的设定，把状态设好了，套上板子处理下边界和正确性就好了，感觉还是要多做题，先贴两道题，之后慢慢更新，可以去vj上坐kuangbin带你飞系列的数位dp专题，题目很适合入门的人。

HDU2089

题面

统计区间 [a,b] 中不含 4 和 62 的数字有多少个。

分析

这其实是一道模板题看了上面两篇blog的做这题会很简单，部分注释写在代码里了。 

/*************************************************************************
     > Author: Drinkwater
     > Created Time: 2017/8/24 21:55:11
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

#prag\
ma GCC optimize("O3")

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

int read()
{
    register int sum = 0,fg = 0;char c = getchar();
    while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return fg ? -sum : sum;
}

const int inf = 1e9;
const int maxn = 100000;

int n,m,num;
int a[maxn];

void fj(int x)
{
    num = 0;
    while(x){a[num++] = x % 10;x/=10;}
}
int dp[1010][2];//dp[i][j]表示dp到i位前一位是不是6?的方案数 

int dfs(int pos,int pre,int flag,bool lim)//数位dp精华 
{
    if(pos == -1)return 1;//搜到叶子节点返回 
    if(!lim && dp[pos][flag] != -1)return dp[pos][flag];//要没有上限才能返回，因为可能引起状重复 
    int up = lim ? a[pos] : 9;//上限 
    int sum = 0;
    REP(i,0,up)
    {
        if(pre == 6 && i == 2)continue;
        if(i == 4)continue;//搜索可行状态 
        sum += dfs(pos-1,i,i==6,lim && i == a[pos]); 
    }
    if(!lim)dp[pos][flag] = sum;
    return sum;
}   

int main()
{
    while(scanf("%d%d",&n,&m) && n + m)
    {
        mem(dp,-1);fj(m);
        int ans = dfs(num-1,-1,0,1);
        fj(n-1);
        ans -= dfs(num-1,-1,0,1);//前缀和思想 
        cout<<ans<<endl;
    }
    return 0;
}

HDU3555

题面

　给一个数字n,范围在1~2^63-1，求1~n之间含有49的数字有多少个。

分析

其实又是一道模板题，只是逆向思维下用总答案减去你搜出来的不包含49的数的个数就好了（网上貌似没什么人写这种方法，都是正面刚的）

/*************************************************************************
     > Author: Drinkwater
     > Created Time: 2017/8/25 20:27:39
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

#prag\
ma GCC optimize("O3")

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

#define REP(i, a, b) for(register LL i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register LL i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

LL read()
{
    register LL sum = 0,fg = 0;char c = getchar();
    while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return fg ? -sum : sum;
}

const LL inf = 1e9;
const LL maxn = 100000;

LL T,a[maxn],num;
LL dp[maxn][2];

LL dfs(int pos,int pre,bool lim)
{
    bool flag = (pre == 4);
    if(pos == 0)return 1;
    if(!lim && dp[pos][flag]!=-1)return dp[pos][flag];
    int up = lim ? a[pos] : 9;
    LL res = 0;
    REP(i,0,up)
    {
        if(pre == 4 && i == 9)continue;
        res += dfs(pos-1,i,lim && i == a[pos]);
    }
    if(!lim) dp[pos][flag] = res;
    return res;
}

LL solve(LL x)
{
    num = 0;LL tmp = x;
    while(x) {a[++num] = x % 10;x /= 10;}
    return tmp - dfs(num,-1,1);
}

int main()
{
    T = read();
    mem(dp,-1);
    while(T--)
    {
        LL x = read();
        cout<<solve(x)+1<<endl;
    }
    return 0;
}

CF Beautiful Numbers

题面

这个数能整除它的所有位上非零整数。问[l,r]之间的Beautiful Numbers的个数。

分析

这道题首先要知道一个东西，我们设这个数为X,lcm(1−9)=2520。
如果lcm(Ai)|X,并且lcm(Ai)|2520,那么X|2520。
通过这个式子我们可以把范围下降到2520，这样我们时间复杂度和空间复杂度都可行了，但是发现还是会爆，于是我们把2520 的约数用Hash映射下就好了，具体看代码吧。

/*************************************************************************
     > Author: Drinkwater
     > Created Time: 2017/8/25 19:31:25
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

LL read()
{
    register LL sum = 0,fg = 0;char c = getchar();
    while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return fg ? -sum : sum;
}

const int inf = 1e9;
const int maxn = 100000;
const int Max_L = 2520;
int Hash[Max_L+10],cnt;

int T;
LL dp[25][50][2530],num,a[maxn];

LL gcd(LL a,LL b) {return b == 0 ? a : gcd(b,a%b);}

LL lcm(LL a,LL b) { return a / gcd(a,b) * b; }

LL dfs(int pos,int prelcm,int prenum,int lim)
{
    if(pos == 0)return prenum%prelcm == 0;
    if(!lim && dp[pos][Hash[prelcm]][prenum] != -1)return dp[pos][Hash[prelcm]][prenum];
    int up = lim ? a[pos] : 9;
    LL res = 0;
    REP(i,0,up)
    {
        int nownum = (prenum*10 + i ) % Max_L;
        int nowlcm = prelcm;
        if(i)nowlcm = lcm(nowlcm,i);
        res += dfs(pos-1,nowlcm,nownum,lim && i == up);
    }
    if(!lim)dp[pos][Hash[prelcm]][prenum] = res;
    return res;
}

LL solve(LL x)
{
    num = 0;
    while(x)a[++num] = x % 10,x /= 10;
    return dfs(num,1,0,1);
}

int main()
{
    REP(i,1,Max_L)if(Max_L % i == 0)Hash[i] = ++cnt;
    T = read();
    mem(dp,-1);
    while(T--)
    {
        LL l = read(),r = read();
        cout<<solve(r) - solve(l-1)<<endl;
    }
    return 0;
}

SAK大神今天模拟赛出了一道数位dp的题目，md又没做出来，真是的，刚刚学就出这种题目，哎，我也很无奈啊，又是一道数位dp的裸题，没办法，只能靠慢慢积累了，不栽几个跟头又怎么会印象深刻呢？

题面

问你从1到n有多少数是符合其内部没有回文串的呢？

分析

感觉看了weary的代码对这个内容有了新的理解，之前学习的板子都是从后面往前面搜的，现在还有种方法可以用vector的reverse的功能，从前往后搜索，加上&的传地址功能，代码显得很简练，我们设dp[i][j][k][0/1] 表示当前在第i位，前一位的数字为j，前两位的数字为k，是否达到了上届转移很简单了，记忆化搜索会显得很好理解，不多说了，直接上代码。

/*************************************************************************
     > Author: Drinkwater
     > Created Time: 2017/8/26 10:12:32
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>

#prag\
ma GCC optimize("O3")

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

LL read()
{
    register LL sum = 0,fg = 0;char c = getchar();
    while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return fg ? -sum : sum;
}

const int inf = 1e9;
const int maxn = 100000;

LL dp[50][11][11][2],num;
LL n,m;
vector<int>a;

LL dfs(int pos,int pre,int ppre,int lim,int lead = 0)
{
    if(pos == a.size())return 1;    
    if(dp[pos][pre][ppre][lim]!=-1)return dp[pos][pre][ppre][lim];
    int up= lim ? a[pos] : 9;
    LL res = 0;
    REP(i,lead,up)
        if(i != pre && i != ppre)
            res += dfs(pos+1,i,pre,lim && i == a[pos]); 
    return dp[pos][pre][ppre][lim] = res;
}

LL solve(LL x)
{
    a.clear();
    mem(dp,-1);
    while(x) { a.push_back(x%10); x/= 10;}
    reverse(a.begin(),a.end());
    LL res = 0;
    REP(i,0,a.size()-1)res+=dfs(i,10,10,i==0,1);
    return res + 1;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("numbers.in", "r", stdin);
    freopen("numbers.out", "w", stdout);
#endif
    int F = 0;
    n = read(),m = read();
    if(n)n--;
    else F = 1;
    cout<<solve(m) - solve(n)+F<<endl;
    return 0;
}

XHXJ’s LIS

define xhxj (Xin Hang senior sister(学姐))
If you do not know xhxj, then carefully reading the entire description is very important.
As the strongest fighting force in UESTC, xhxj grew up in Jintang, a border town of Chengdu.
Like many god cattles, xhxj has a legendary life:
2010.04, had not yet begun to learn the algorithm, xhxj won the second prize in the university contest. And in this fall, xhxj got one gold medal and one silver medal of regional contest. In the next year’s summer, xhxj was invited to Beijing to attend the astar onsite. A few months later, xhxj got two gold medals and was also qualified for world’s final. However, xhxj was defeated by zhymaoiing in the competition that determined who would go to the world’s final(there is only one team for every university to send to the world’s final) .Now, xhxj is much more stronger than ever，and she will go to the dreaming country to compete in TCO final.
As you see, xhxj always keeps a short hair(reasons unknown), so she looks like a boy( I will not tell you she is actually a lovely girl), wearing yellow T-shirt. When she is not talking, her round face feels very lovely, attracting others to touch her face gently。Unlike God Luo’s, another UESTC god cattle who has cool and noble charm, xhxj is quite approachable, lively, clever. On the other hand,xhxj is very sensitive to the beautiful properties, “this problem has a very good properties”，she always said that after ACing a very hard problem. She often helps in finding solutions, even though she is not good at the problems of that type.
Xhxj loves many games such as，Dota, ocg, mahjong, Starcraft 2, Diablo 3.etc，if you can beat her in any game above, you will get her admire and become a god cattle. She is very concerned with her younger schoolfellows, if she saw someone on a DOTA platform, she would say: “Why do not you go to improve your programming skill”. When she receives sincere compliments from others, she would say modestly: “Please don’t flatter at me.(Please don’t black).”As she will graduate after no more than one year, xhxj also wants to fall in love. However, the man in her dreams has not yet appeared, so she now prefers girls.
Another hobby of xhxj is yy(speculation) some magical problems to discover the special properties. For example, when she see a number, she would think whether the digits of a number are strictly increasing. If you consider the number as a string and can get a longest strictly increasing subsequence the length of which is equal to k, the power of this number is k.. It is very simple to determine a single number’s power, but is it also easy to solve this problem with the numbers within an interval? xhxj has a little tired，she want a god cattle to help her solve this problem,the problem is: Determine how many numbers have the power value k in [L，R] in O(1)time.
For the first one to solve this problem，xhxj will upgrade 20 favorability rate。
Input
First a integer T(T<=10000),then T lines follow, every line has three positive integer L,R,K.(
0 < L <= R < 2 63-1 and 1<=K<=10).
Output
For each query, print “Case #t: ans” in a line, in which t is the number of the test case starting from 1 and ans is the answer.

题目实际上就是让你求一串数字满足LIS==k的数字个数

分析

这道题比前面的题目都要难一些，需要用到状态压缩，把数字压缩在一个二进制位中表示这一位的数字出现在了数字中，每次|一下就好了，实际上也没什么变化。

/*************************************************************************
     > Author: Drinkwater
     > Created Time: 2017/8/26 16:24:58
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

#define REP(i, a, b) for(register LL i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register LL i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

LL read()
{
    register LL sum = 0,fg = 0;char c = getchar();
    while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return fg ? -sum : sum;
}

const LL inf = 1e9;
const LL maxn = 100000;

LL n,m,T,k;
LL dp[20][(1<<10)+10][2][11];
vector<LL>a;

LL New(LL s,LL p)
{
    REP(i,p,9)
        if(s & (1<<i)) {s ^= (1<<i);break;}
    return s|(1<<p);
}

LL dfs(LL pos,LL st,LL lim,LL lead=0)
{
    if(pos == a.size())return __builtin_popcount(st) == k;
    if(dp[pos][st][lim][k]!=-1)return dp[pos][st][lim][k];
    LL up = lim ? a[pos] : 9;
    LL res = 0;
    REP(i,lead,up)
        res += dfs(pos+1,New(st,i),lim && i == a[pos]);
    return dp[pos][st][lim][k] = res;
}

LL solve(LL x)
{
    a.clear();
    LL tmp = x;
    while(tmp) a.push_back(tmp%10),tmp/=10;
    reverse(a.begin(),a.end());
    LL res = 0;
    mem(dp,-1);
    REP(i,0,a.size()-1)res+=dfs(i,0,(i==0),1);
    return res;
}

int main()
{
    T = read();
    REP(I,1,T)
    {
        n = read(),m = read();k = read();
        cout<<"Case #"<<I<<": ";
        cout<<solve(m)-solve(n-1)<<endl;
    }
    return 0;
}

HUD3652

题面

A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string “13” and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
Output
Print each answer in a single line.

问你1到n有多少数字满足被13整除并且包含13这个数。

分析

记dp[i][j][k][l] 分别表示在第i位，前面的数mod13 为j，包不包含13，前面一位的数字是l然后记忆化搜索就好了。

/*************************************************************************
     > Author: Drinkwater
     > Created Time: 2017/8/28 20:13:56
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>

#prag\
ma GCC optimize("O3")

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

int read()
{
    register int sum = 0,fg = 0;char c = getchar();
    while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return fg ? -sum : sum;
}

const int inf = 1e9;
const int maxn = 100000;

LL n;
LL dp[20][20][2][10]; 
vector<int>a;

LL dfs(int pos,int mod,int has,int pre,int lim)
{
    if(pos == -1)return (has && (!mod));
    if(!lim && dp[pos][mod][has][pre]!=-1)return dp[pos][mod][has][pre];
    int up = lim ? a[pos] : 9;
    LL res = 0;
    REP(i,0,up)
    {
        int Has = has;
        if(pre == 1 && i == 3)Has = 1;
        int Mod = (mod * 10 + i)%13;
        res += dfs(pos-1,Mod,Has,i,lim&&i==a[pos]);
    }
    if(!lim)dp[pos][mod][has][pre] = res;
    return res;
}
LL solve(LL x)
{
    a.clear();
    while(x) a.push_back(x%10),x/=10;
    return dfs(a.size()-1,0,0,-1,1);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("G.in", "r", stdin);
    freopen("G.out", "w", stdout);
#endif
    mem(dp,-1);
    while(scanf("%lld",&n)!=EOF)
        cout<<solve(n)<<endl;
    return 0;
}

Balanced numbers

The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone’ (also known as ‘Rock, Paper, Scissors’, ‘Ro, Sham, Bo’, and a host of other names) in order to make arbitrary decisions such as who gets to be milked first. They can’t even flip a coin because it’s so hard to toss using hooves.
They have thus resorted to “round number” matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both “round numbers”, the first cow wins,
otherwise the second cow wins.
A positive integer N is said to be a “round number” if the binary representation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.
Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many “round numbers” are in a given range.
Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).

问你有多少数字在给定区间里满足以一个数为中心左右两边的力矩乘数字之和相等的数字的个数。

分析

设dp[i][j][k] 分别表示第i位，j为力矩中心，k为和然后记忆化就好了。

/*************************************************************************
     > Author: Drinkwater
     > Created Time: 2017/8/28 19:36:05
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>

#prag\
ma GCC optimize("O3")

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

#define REP(i, a, b) for(register LL i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register LL i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

LL read()
{
    register LL sum = 0,fg = 0;char c = getchar();
    while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return fg ? -sum : sum;
}

const int inf = 1e9;
const int maxn = 100000;

int T;
LL dp[30][30][2010];
vector<int>a;

LL dfs(int pos,int cen,int sum,int lim)
{
    if(pos == -1)return sum == 0;
    if(sum < 0)return 0;
    if(!lim && dp[pos][cen][sum]!=-1)return dp[pos][cen][sum];
    int up = lim ? a[pos] : 9;
    LL res = 0;
    REP(i,0,up)
        res += dfs(pos-1,cen,sum+(pos-cen)*i,lim && a[pos] == i);
    if(!lim)dp[pos][cen][sum] = res;
    return res;
}

LL solve(LL x)
{
    a.clear();
    while(x)a.push_back(x%10),x/=10;
    LL res = 0;
    REP(i,0,a.size()-1)
        res += dfs(a.size()-1,i,0,1);
    return res - a.size() + 1;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("F.in", "r", stdin);
    freopen("F.out", "w", stdout);
#endif
    T = read();
    mem(dp,-1);
    while(T--)
    {
        LL x = read(),y = read();
        cout<<solve(y)-solve(x-1)<<endl;
    }
    return 0;
}

BZOJ3209: 花神的数论题

背景
众所周知，花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
描述
话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。
花神的题目是这样的
设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你
派(Sum(i)),也就是 sum(1)—sum(N) 的乘积。

这题要转换一下思路，题目要求的是sumi−sumj 的积，我们求有多少个数字有k个1，然后快速幂就好了。

/*************************************************************************
     > Author: Drinkwater
     > Created Time: 2017/8/28 21:14:43
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>

#prag\
ma GCC optimize("O3")

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

LL read()
{
    register LL sum = 0,fg = 0;char c = getchar();
    while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return fg ? -sum : sum;
}

const int inf = 1e9;
const int maxn = 100000;
const int mod = 10000007;

LL n;
LL dp[100][100],a[maxn],cnt;

LL dfs(int pos,int num,int lim)
{
    if(num > pos)return 0;
    if(pos == 0 && num == 0)return 1;
    if(pos == 0)return 0;
    if(!lim && dp[pos][num]!=-1)return dp[pos][num];
    int up = lim ? a[pos] : 1;
    LL res = 0;
    REP(i,0,up)res = res + dfs(pos-1,num-(i==1),lim && a[pos] == i);
    if(!lim)dp[pos][num] = res;
    return res;
}

LL N[maxn];

LL qpow(LL x,LL y)
{
    LL ans = 1;
    while(y)
    {
        if(y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans%mod;
}

LL solve(LL x)
{
    while(x)a[++cnt] = x % 2, x /= 2;
    LL res = 1;
    REP(i,1,cnt)
    {
        LL k = dfs(cnt,i,1);
        if(k)res = (res * qpow(i,k))%mod;
    }
    return res;
}
int main()
 {
#ifndef ONLINE_JUDGE
    freopen("bzoj3209.in", "r", stdin);
    freopen("bzoj3209.out", "w", stdout);
#endif
    n = read();
    mem(dp,-1);
    cout<<solve(n)<<endl;
    return 0;
}

POJ3252Round Numbers

题面

有多少数的二进制零的个数大于1的个数？

分析

dp[i][j][k] 分别表示在i位，有j个0，k个1，记得特判一下第一个一放的位置就好了。

/*************************************************************************
     > Author: Drinkwater
     > Created Time: 2017/8/29 21:08:24
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>

#prag\
ma GCC optimize("O3")

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

LL read()
{
    register LL sum = 0,fg = 0;char c = getchar();
    while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return fg ? -sum : sum;
}

const int inf = 1e9;
const int maxn = 100000;

LL n,m;
LL dp[70][70][70];
vector<int>a;

LL dfs(int pos,int n0,int n1,int has,int lim)
{
    if(pos == -1) return (n0 >= n1 || has);
    if(!lim && dp[pos][n0][n1]!=-1 && !has)return dp[pos][n0][n1];
    int up = lim ? a[pos] : 1;
    LL res = 0;
    REP(i,0,up)
    {
        if(has)
        {
            if(i == 0)res += dfs(pos-1,0,0,1,lim&&a[pos]==i);
            else res += dfs(pos-1,n0,n1+1,0,lim&&a[pos]==i);
        }
        else
        {
            if(i == 0)res += dfs(pos-1,n0+1,n1,0,lim&&a[pos]==i);
            else res += dfs(pos-1,n0,n1+1,0,lim&&a[pos]==i);
        }
    }
    if(!lim && !has)dp[pos][n0][n1] = res;
    return res;
}

LL solve(LL x)
{
    a.clear();
    while(x) a.push_back(x%2),x/=2;
    return dfs(a.size()-1,0,0,1,1);
}

int main()
{
    mem(dp,-1);
    while(scanf("%lld%lld",&n,&m)!=EOF) 
        cout<<solve(m)-solve(n-1)<<endl;
    return 0;
}

HDU4734

题意

找出i在0到b之间的f(i)小于等于f(a)的数的个数。

分析

跟前面的题目差不多，记dp[i][j] 为第i位，比j小的数的个数。

/*************************************************************************
    > File Name: H.cpp
    > Author: Drinkwater-cnyali
************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;
#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))

LL read()
{
    LL sum = 0, fg = 1; char c = getchar();
    while(c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return sum * fg;
}

LL T;
vector<int>a;
LL dp[20][50010],A,B;

int f()
{
    int res = 0,len = 1;
    LL tmp = A;
    while(tmp)
    {
        res += tmp%10 * len;
        len <<= 1;tmp/=10;
    }
    return res;
}

LL dfs(int pos,int F,int lim)
{
    if(pos == -1)return F >= 0;
    if(F < 0)return 0;
    if(!lim && dp[pos][F]!=-1)return dp[pos][F];
    int up = lim ? a[pos] : 9;
    LL res = 0;
    REP(i,0,up)
        res += dfs(pos-1,F-i*(1<<pos),lim && a[pos] == i);
    if(!lim)dp[pos][F] = res;
    return res;
}

LL solve(LL x)
{
    a.clear();
    while(x) a.push_back(x%10),x/=10;
    return dfs(a.size()-1,f(),1);
}

int main()
{
    T = read();
    mem(dp,-1);
    REP(I,1,T)
    {
        A = read(),B = read();
        cout<<"Case #"<<I<<": ";
        cout<<solve(B)<<endl;
    }
    return 0;
}

转载于:https://www.cnblogs.com/brodrinkwater/p/7527982.html

相关文章：

  • js匿名函数
  • Could not resolve resource location pattern错误解决方案
  • PAT乙级-1026. 程序运行时间(15)
  • HTTP中GET与POST的区别 99%的错误认识
  • 好汉两个半第十二季/全集Two and a Half Men迅雷下载
  • Learning How to Learn
  • 一起玩树莓派3+使用Gitlab搭建专业Git服务
  • Android Finalizing a Cursor that has not been deactivated or closed
  • 土耳其重大数据泄露事件 数据库安全受关注
  • 互联网分析师：5G距离我们还有多远?
  • oracle增加sequence
  • 藏在高端智能手机芯片里的“外交官”：射频前端
  • 哈尔滨工业大学校园网运营：开放兼容，灵活认证
  • js 获取中文的拼音
  • Wi-Fi新标准HaLow正面挑战ZigBee、Z-Wave
  • 【编码】-360实习笔试编程题（二）-2016.03.29
  • 77. Combinations
  • java B2B2C 源码多租户电子商城系统-Kafka基本使用介绍
  • Java的Interrupt与线程中断
  • Java读取Properties文件的六种方法
  • SAP云平台运行环境Cloud Foundry和Neo的区别
  • Traffic-Sign Detection and Classification in the Wild 论文笔记
  • UEditor初始化失败（实例已存在，但视图未渲染出来，单页化）
  • Windows Containers 大冒险: 容器网络
  • 反思总结然后整装待发
  • 入门到放弃node系列之Hello Word篇
  • 三分钟教你同步 Visual Studio Code 设置
  • 设计模式（12）迭代器模式（讲解+应用）
  • 问:在指定的JSON数据中（最外层是数组）根据指定条件拿到匹配到的结果
  • 一个SAP顾问在美国的这些年
  • 最简单的无缝轮播
  • Spring Batch JSON 支持
  • 国内开源镜像站点
  • # 数据结构
  • （12）Linux 常见的三种进程状态
  • （2）nginx 安装、启停
  • （C语言）fread与fwrite详解
  • （机器学习-深度学习快速入门）第三章机器学习-第二节：机器学习模型之线性回归
  • （十三）Flask之特殊装饰器详解
  • （算法）前K大的和
  • (一)认识微服务
  • .bat批处理（八）：各种形式的变量%0、%i、%%i、var、%var%、!var!的含义和区别
  • .gitattributes 文件
  • .htaccess配置常用技巧
  • .net core 6 redis操作类
  • .net下简单快捷的数值高低位切换
  • /usr/bin/python: can't decompress data; zlib not available 的异常处理
  • @value 静态变量_Python彻底搞懂：变量、对象、赋值、引用、拷贝
  • [.net]官方水晶报表的使用以演示下载
  • [\u4e00-\u9fa5] //匹配中文字符
  • [2023年]-hadoop面试真题(一)
  • [2024] 十大免费电脑数据恢复软件——轻松恢复电脑上已删除文件
  • [BZOJ5250][九省联考2018]秘密袭击(DP)
  • [c]统计数字
  • [C++]priority_queue的介绍及模拟实现