相关链接
题目传送门：http://codeforces.com/contest/747/problem/F
优雅的暴力：http://codeforces.com/blog/entry/49171?#comment-331886
官方题解：http://codeforces.com/blog/entry/49171
神犇代码：http://codeforces.com/contest/747/submission/23125896
解题报告
首先这题推一推式子发现答案最多9位的样子
于是我们就可以暴力搜索，用Meet in Middle来做就好
当然这题有更加清真的、类似数位DP的做法
假定我们能够做到给定字符串长度和每个数字可以用多少次，求有多少种合法情况的话
显然可以像数位DP一样，从高位到低位逐位确定每一位的数字应该是多少
现在问题转化为如何求的合法情况。
依次考虑每一种数字，显然对答案的贡献只与有多少个空位有关
于是f[i][j]表示现在考虑到第i种数字，还剩j个空位的方案数
这样的话，暴力转移即可。
时间复杂度：O(16^3+16*9)
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int k,t,C[21][21],res[21];
char ori[]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
inline int read() {
char c=getchar(); int f=1,ret=0;
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;
}
inline LL solve(int len, bool ty) {
static LL f[2][20]; bool w,p;
memset(f,0,sizeof(f));
f[p=0][ty] = 1; w = 1;
for (int i=0;i<16;i++,w^=1,p^=1) {
memset(f[w],0,sizeof(f[w]));
for (int j=len;~j;j--)
for (int k=min(len-j,res[i]-(ty&(i==0)));~k;k--)
f[w][j+k] += f[p][j] * C[k][len-j];
}
return f[p][len];
}
int main() {
for (int i=0;i<=20;i++) {
C[0][i] = C[i][i] = 1;
for (int j=1;j<i;j++)
C[j][i] = C[j-1][i-1] + C[j][i-1];
}
k = read(); t = read();
for (int i=0;i<=15;i++)
res[i] = t;
LL tmp; int len=1;
while ((tmp = solve(len,0) - solve(len,1)) < k)
k -= tmp, len++;
for (int i=len,ret=1;i;ret=0,i--) {
res[ret]--;
while ((tmp = solve(i-1,0)) < k)
res[ret++]++, res[ret]--, k -= tmp;
printf("%c",ori[ret]);
}
return 0;
}
Wonderful items from you, man. I’ve take into accout your stuff prior to and you’re just extremely fantastic.
I really like what you have got right here, certainly like what you’re stating and the way by which you are saying it.
You make it entertaining and you still take care of to keep it wise.
I can’t wait to learn far more from you. That
is really a terrific web site.
I’m gone to tell my little brother, that he should also go to see this website
on regular basis to obtain updated from hottest information.
hey there and thank you for your info – I’ve
definitely picked up anything new from right here.
I did however expertise some technical points using this website, since I experienced to reload the site lots of
times previous to I could get it to load correctly. I had been wondering if your web host is OK?
Not that I am complaining, but slow loading instances times will sometimes affect your placement in google and can damage your quality
score if advertising and marketing with Adwords. Anyway I’m adding
this RSS to my e-mail and can look out for a lot more of your respective exciting content.
Ensure that you update this again soon.
Hi! I understand this is kind of off-topic but I had to ask.
Does building a well-established blog such as yours
take a lot of work? I’m completely new to blogging however I do write in my journal every day.
I’d like to start a blog so I will be able to share my experience and feelings online.
Please let me know if you have any kind of ideas
or tips for brand new aspiring blog owners.
Thankyou!
What’s up, I wish for to subscribe for this blog to obtain latest
updates, so where can i do it please help.
I take pleasure in, result in I found just what I was looking for.
You have ended my four day lengthy hunt! God Bless you man. Have a nice day.
Bye
Great article, just what I wanted to find.
Very good article! We are linking to this
particularly great post on our site. Keep up the good writing.
Hi there, I found your web site by way of Google at the same time as
searching for a comparable topic, your website got here up,
it appears great. I’ve bookmarked it in my google bookmarks.
Hello there, just was aware of your weblog through Google, and located that it is
truly informative. I’m going to watch out for brussels.
I’ll appreciate for those who continue this in future. Many other folks might be
benefited from your writing. Cheers!
Nice blog here! Also your site a lot up very
fast! What host are you using? Can I get your associate hyperlink to your host?
I want my website loaded up as quickly as yours lol
I’d constantly want to be update on new posts on this site, saved to bookmarks! .
An impressive share! I have just forwarded this onto a
friend who was conducting a little research on this. And he in fact bought me breakfast simply because I discovered it for him…
lol. So let me reword this…. Thanks for the meal!!
But yeah, thanx for spending time to talk about this matter here on your site.
I am extremely inspired together with your writing
talents as smartly as with the format to your blog.
Is this a paid topic or did you customize it yourself?
Anyway stay up the nice high quality writing,
it’s rare to see a great weblog like this one these days..
Heya are using WordPress for your blog platform? I’m new to the blog world but I’m trying to get started and set up my own. Do
you need any coding expertise to make your own blog?
Any help would be greatly appreciated!
Hi, Neat post. There is an issue along with your web site in web explorer, might test this?
IE nonetheless is the marketplace leader and a huge element
of other folks will pass over your great writing because of this problem.
Wow, that’s what I was searching for, what a data! present here at this weblog, thanks admin of this website.
Hi! This is my first comment here so I just wanted
to give a quick shout out and say I truly enjoy reading through
your posts. Can you suggest any other blogs/websites/forums that go over the same
topics? Thanks!
Informative article, exactly what I wanted to find.
I was just searching for this info for a while. After 6 hours of continuous Googleing, finally I got it in your website. I wonder what’s the lack of Google strategy that do not rank this kind of informative web sites in top of the list. Generally the top web sites are full of garbage.