【Codeforces 55D】Beautiful numbers

题目传送门:http://codeforces.com/contest/55/problem/D
官方题解:http://codeforces.com/blog/entry/1109
中文题面:number_dp_by_zky

之前做数位dp的题目,一直强调数位间的独立性
然而现在看来,不独立也是可以上数位dp的

题解直接看上面给的“中文题面”里的题解吧,zky的题解真的是超级棒(๑•̀ㅂ•́)و✧
我来说一说代码实现的三种方式:

1)像之前的代码一样,先预处理,然后查询的时候在数组上搞一搞
优点:对于多组询问特别好用
缺点:因为是预处理,所以对于有些题目可能很麻烦,甚至不能预处理

2)对于每一次询问单独dp,记录是否达到上限
优点:代码好写(不用于处理,直接写一个dp就成)
缺点:多组询问没法处理

3)对于每一次询问DFS,如果这一位没有受到任何限制就记忆化
这种方法是我在看这位神犇的代码的时候看到的:http://codeforces.com/contest/55/submission/3692033
优点:代码更好写,且对于多组询问相对友好(仔细想一想,他的查询次数应该不会劣于方法1?)
缺点:如果位数特别大(什么1e5,1e6之类的),则效果可能不太好

总的来说,我似乎爱上了第三种写法 = ̄ω ̄=
以后数位dp的题应该是首选第三种吧!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int MOD[]={1,1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,180,210,252,280,315,360,420,504,630,840,1260,2520};
int pos[2530],lcm[50][50],sta[20]; 
LL f[20][50][2530];

LL GCD(LL a, LL b) {return b?GCD(b,a%b):a;}
LL LCM(LL a, LL b) {return a/GCD(a,b)*b;}


LL DFS(int t, int lm, int mod, bool top) {
	if (t == 0) {
		return !(mod % MOD[lm]);
	} else if (~f[t][lm][mod] && !top) {
		return f[t][lm][mod];	
	} else {
		LL ret = 0;
		for (int i=0,ty=(top>0?sta[t]:9),tmp;i<=ty;i++) {
			tmp = lcm[lm][i];
			ret += DFS(t-1,tmp,(mod*10+i)%2520,top&&i==sta[t]);
		}
		return top?ret:f[t][lm][mod] = ret;
	}
}

inline LL cal(LL lim) {
	int cnt = 0;
	while (lim) {
		sta[++cnt] = lim % 10;
		lim /= 10;
	}
	return DFS(cnt,1,0,1);
}

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

int main(){
	memset(f,-1,sizeof(f));
	for (int i=1;i<=48;i++) {
		pos[MOD[i]] = i;
	}
	for (int i=0;i<=48;i++) {
		for (int j=0;j<=48;j++) {
			lcm[i][j] = pos[LCM(MOD[i],MOD[j])];
		}
	} 
	for (int T=read();T;--T) {
		LL l = read(), r = read();
		printf("%I64d\n",cal(r)-cal(l-1));
	}
	return 0;
}

28 thoughts to “【Codeforces 55D】Beautiful numbers”

  1. I’ll right away grasp your rss as I can’t to find your email subscription link
    or newsletter service. Do you have any? Please let me recognize in order that I could
    subscribe. Thanks.

  2. Wow that was strange. I just wrote an extremely long comment but after I clicked submit my comment didn’t appear.
    Grrrr… well I’m not writing all that over again. Anyhow, just wanted to say great blog!

  3. I loved as much as you’ll receive carried out right here.
    The sketch is attractive, your authored material stylish.

    nonetheless, you command get got an shakiness over that
    you wish be delivering the following. unwell unquestionably
    come more formerly again as exactly the same nearly a
    lot often inside case you shield this increase.

  4. Hi there fantastic blog! Does running a blog similar to this take
    a massive amount work? I’ve absolutely no expertise in computer
    programming but I had been hoping to start my own blog soon. Anyways, should you have any suggestions or techniques for new blog owners please share.
    I know this is off subject but I just needed to ask.
    Many thanks!

  5. Having read this I believed it was rather informative.
    I appreciate you taking the time and effort to put this short article together.
    I once again find myself personally spending
    way too much time both reading and leaving comments.
    But so what, it was still worth it!

  6. What i do not understood is in truth how you’re now not really much more well-appreciated than you
    may be right now. You’re very intelligent.
    You recognize therefore considerably on the subject
    of this matter, made me in my opinion imagine it from numerous various angles.
    Its like women and men don’t seem to be interested until it is
    something to do with Woman gaga! Your personal stuffs outstanding.
    At all times deal with it up!

  7. You’ve made some good points there. I looked on the net to learn more about the issue and found most individuals will go along with your views on this website.

  8. My husband and i felt quite happy that John could finish off his studies from the precious recommendations he had through your web page. It is now and again perplexing just to be releasing secrets most people might have been making money from. And now we recognize we now have the blog owner to be grateful to for that. These illustrations you made, the straightforward site menu, the friendships you can assist to instill – it’s mostly astounding, and it is facilitating our son in addition to our family do think the subject is satisfying, and that is pretty indispensable. Many thanks for the whole thing!

  9. Hello just wanted to give you a quick heads up. The words in your content seem to be running off the screen in Internet explorer.
    I’m not sure if this is a format issue or something to do with internet browser compatibility but I figured I’d post to let you know.
    The style and design look great though! Hope you get the problem fixed soon. Thanks

  10. What’s up it’s me, I am also visiting this web site daily, this
    website is actually good and the visitors are really sharing pleasant thoughts.

  11. Hi my loved one! I want to say that this post is awesome, nice written and
    come with almost all important infos. I would like to peer extra posts like this .

  12. Good web site you have here.. It’s difficult to find good quality writing
    like yours these days. I honestly appreciate people like you!
    Take care!!

  13. Thank you a lot for sharing this with all of us you really recognise what you are speaking approximately!
    Bookmarked. Please also talk over with my website =). We could
    have a link alternate contract among us

  14. Very nice post. I just stumbled upon your blog and wanted to mention that I
    have really enjoyed browsing your blog posts.

    After all I’ll be subscribing to your rss feed and I hope
    you write again soon!

  15. Hey! I know this is kind of off topic but I was wondering which
    blog platform are you using for this website? I’m getting sick
    and tired of WordPress because I’ve had problems with hackers and I’m looking at options for another platform.
    I would be fantastic if you could point me in the direction of a good platform.

  16. great issues altogether, you just gained a new reader.
    What might you recommend about your submit that you simply made some days in the past?
    Any positive?

  17. This is really interesting, You are a very skilled blogger. I’ve joined your rss feed and look forward to seeking more of your great post. Also, I’ve shared your website in my social networks!

Leave a Reply to ps4 games Cancel reply

Your email address will not be published. Required fields are marked *