博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVa 12377 - Number Coding
阅读量:5819 次
发布时间:2019-06-18

本文共 1275 字,大约阅读时间需要 4 分钟。

题目:一个数能够用一种素数元素的个数表示的形式,43560=23×32×51×112表示成41223;

            第一个数是素因子的种类,第二个是每一个素因子的个数递增排列。给你一个这样的形式的串,

            问原来的数可能有几种情况。

分析:数论,计数原理,组合数学。

            对于每一个串,第一个数字一定是素因子的种类数。

            首先,利用搜索找到全部剩余串的可能组合形式。

            然后。求出每种情况下的组合数。加和就可以。

说明:注意一个新的数字不能以0開始。

#include 
#include
#include
#include
using namespace std;int p[11],f[11];char buf[22];long long value(int s, int t){ long long V = 0LL; for (int i = s ; i <= t ; ++ i) { V *= 10LL; V += buf[i]-'0'; } return V;}long long save[11];long long temp[11];long long dfs(int s, int l, int d, int n){ long long sum = 0LL; if (d == n && s == l) { sum = 0LL+p[n]; //去掉同样元素的内部排列 int count = 1; for (int i = 1 ; i < d ; ++ i) { if (save[i] == save[i-1]) count ++; else { sum /= f[count]; count = 1; } } sum /= f[count]; } for (int i = s ; i < l ; ++ i) { save[d] = value(s, i); if ((!d || save[d] >= save[d-1]) && buf[i+1] != '0') { temp[d] = save[d]; sum += dfs(i+1, l, d+1, n); save[d] = temp[d]; } } return sum;}int main(){ p[0] = 1; f[0] = 1; for (int i = 1 ; i < 10 ; ++ i) { p[i] = p[i-1]*(10-i); f[i] = f[i-1]*i; } int n,l,d; while (~scanf("%d",&n)) for (int i = 1 ; i <= n ; ++ i) { scanf("%s",buf); l = strlen(buf); cout << dfs(1, l, 0, buf[0]-'0') << endl; } return 0;}

转载地址:http://ijwdx.baihongyu.com/

你可能感兴趣的文章
Material Design使用集合
查看>>
什么是CountDownLatch
查看>>
C类地址的子网划分
查看>>
《IE恶搞迷》扩展功能使用
查看>>
通过Dockerfile构建nginx实例
查看>>
Linux 初学浅知(基础认知篇)
查看>>
限制MySQL数据库单个用户最大连接数等的方法
查看>>
我的友情链接
查看>>
这个貼的帐号是
查看>>
我的友情链接
查看>>
openfiler创建iscsi网络存储
查看>>
静态路由的主要特点
查看>>
思杰北京公司参观和交流
查看>>
we are programmable
查看>>
在RHEL6.4下审计root用户的行为
查看>>
微软桌面虚拟化所需产品及RemoteFX要求介绍
查看>>
在VS.NET的VC++中运行控制台程序后暂停
查看>>
专题的学习
查看>>
chrome启用win8模式后打不开解决办法
查看>>
命名管道和套接字的区别
查看>>