bzoj 2425 [HAOI2010]计数 dp+组合计数
2024-08-30 05:30:40
[HAOI2010]计数
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 451 Solved: 289
[Submit][Status][Discuss]
Description
你有一组非零数字(不一定唯一),你可以在其中插入任意个0,这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。
现在给定一个数,问在这个数之前有多少个数。(注意这个数不会有前导0).
Input
只有1行,为1个整数n.
Output
只有整数,表示N之前出现的数的个数。
Sample Input
1020
Sample Output
7
HINT
n的长度不超过50,答案不超过263-1.
Source
这个就是一个简单的组合计数问题。
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<algorithm> #define N 57
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n;
int cnt[N];
ll ans,c[N][N];
char ch[N]; void init_C()
{
c[][]=;
for (int i=;i<=;i++)
{
c[i][]=;
for (int j=;j<=i;j++)
c[i][j]=c[i-][j-]+c[i-][j];
}
}
ll cal(int x)
{
ll res=;
int now=x;
for (int j=;j<;j++)
res*=c[now][cnt[j]],now-=cnt[j];
return res;
}
int main()
{
init_C(),scanf("%s",ch+),n=strlen(ch+);
for (int i=;i<=n;i++) ++cnt[ch[i]-''];
for (int i=;i<=n;i++)
{
for (int j=;j<=(ch[i]-'')-;j++)
if (cnt[j])
{
--cnt[j];
ans+=cal(n-i);
++cnt[j];
}
--cnt[ch[i]-''];
}
printf("%lld\n",ans);
}
最新文章
- java 24 - 11 GUI之制作登陆注册页面
- AutoResetEvent waitone set进一步理解补充
- mac下Nginx+lua模块编译安装
- 双向广搜 codevs 3060 抓住那头奶牛
- win7引导项顺序
- qDebug 学习小结
- mysql 5.6 参数详解
- ios中的GCD
- NEFUOJ 500 二分法+最大流量
- Spring Cloud教程合集
- JDK源码分析(10)之 Hashtable 相关
- (10) 如何MySQL读压力大的问题
- Confluence 6 示例 - https://confluence.atlassian.com/
- UI BOL 练习 get value set attr
- linux下打开文件、编辑文本cat\gedit\nano
- dedecms 后台修改系统设置,但是config.cache.inc.php文件不能写入
- 20155313 2016-2017-2《Java程序设计》课程总结
- 织梦dede模板中广告的去除方法?
- 初涉京东及淘宝开放平台API-商品模型
- babel-preset-es2015,babel-polyfill 与 babel-plugin-transform-runtime