BZOJ 1025 游戏
Description
windy学会了一种游戏。对于1到N这N个数字,都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1,2,3,……,N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为1,2,3,……,N。 如: 1 2 3 4 5 6 对应的关系为 1->2 2->3 3->1 4->5 5->4 6->6 windy的操作如下 1 2 3 4 5 6 2 3 1 5 4 6 3 1 2 4 5 6 1 2 3 5 4 6 2 3 1 4 5 6 3 1 2 5 4 6 1 2 3 4 5 6 这时,我们就有若干排1到N的排列,上例中有7排。现在windy想知道,对于所有可能的对应关系,有多少种可能的排数。
Input
包含一个整数,N。
Output
包含一个整数,可能的排数。
Sample Input
3
【输入样例二】
10
Sample Output
3
【输出样例二】
16
HINT
【数据规模和约定】
100%的数据,满足 1 <= N <= 1000 。
Source
首先,我们可以这样思考,每个置换排列都有若干个循环结。e.g. 3 2 1 5 4 6的循环结就是(1,2,3)(4,5)(6),所以它所能变换的排列数为(lcm为最小公倍数)lcm(1,2,3)=6。而1+2+3=6。
所以我们只需要求出满足x1+x2+x3+x4+...xm=n,lcm(x1,x2,x3,...,xm)有多少种。
蒟蒻的我也只能YY到这里了,暴力枚举肯定没戏,剩下的是题解做的了,其实想想应该是能自己策清的。
首先我们令x1+x2+x3+...+xm<=n(如果少了我们可以补1嘛)。再令x1=p1^t1,x2=p2^t2...其中pi为质数且pi≠pj(i≠j),则lcm=∏xi,明显不重复。
然后,我们只需要证明若xi=pi*pj,也可以用lcm也包含在上面的情况。
不妨设pi<pj,则因为p是质数,明显有pi*pj>pi+pj,所以对于这种情况我们在pi,pj的情况中枚举了(少了仍然可以补1)。
因此,我们可以dp了,哈哈哈。
f[i][j]表示前i个质数,何为j的方案数(我们都是拆分成pi^ti的形式,刚刚已经证明了其不可能重复,也包含了所有方案)。转移自己脑补一下吧!!!
#include<cstdio>
#include<cstdlib>
using namespace std; #define maxn 1010
int n,tot,prime[maxn]; long long f[maxn][maxn],ans; bool exist[maxn]; inline void find()
{
for (int i = ;i <= n;++i)
if (!exist[i])
{
prime[++tot] = i;
for (int j = i*i;j <= n;j += i) exist[j] = true;
}
} inline void dp()
{
f[][] = ;
for (int i = ;i <= tot;++i)
{
for (int j = ;j <= n;++j) f[i][j] = f[i-][j];
for (int j = prime[i];j <= n;j *= prime[i])
{
for (int k = ;k + j <= n;++k)
f[i][k+j] += f[i-][k];
}
}
for (int i = ;i <= n;++i) ans += f[tot][i];
} int main()
{
freopen("1025.in","r",stdin);
freopen("1025.out","w",stdout);
scanf("%d",&n);
find();
dp();
printf("%lld",ans);
fclose(stdin); fclose(stdout);
return ;
}
最新文章
- Facebook的Web开发三板斧:React.js、Relay和GraphQL
- mac iterm2配置
- Android中将布局文件转成bitmap
- Bellman-Ford 算法及其优化
- Android手机tcpdump抓包
- SQL Server AlwaysOn articles
- NeHe OpenGL教程 第三十五课:播放AVI
- sharepoint 2010 切换域
- DES加密系统的实现
- JavaSctipr 兼容、技巧、牛角尖
- LINUX 暂停、继续进程
- POJ1611 The Suspects (并查集)
- shell 脚本——判断条件
- 基于Consul的数据库高可用架构【转】
- 【VirtualBox】共享文件夹失效问题
- elk6.3 centos集群搭建 head插件安装
- Photoshop制作Android UI: 怎样将图片背景变为透明
- 【AngularJS】AngularJS整合Springmvc、Mybatis环境搭建
- 通过一个例子感受C# 6.0新特性
- iOS:网络编程解析协议一:HTTP超文本传输协议
热门文章
- 树莓派入手(烧写系统,调整分区,配置Java环境,串口GPS配置) 分类: Raspberry Pi 2015-04-09 21:13 145人阅读 评论(0) 收藏
- docker 镜像和容器的批量清理
- Cocos2d-x游戏开发中的消息机制:CCNotificationCenter的使用
- viewpager+fragment学习笔记
- iOS进度指示器——NSProgress
- Unity3D 游戏的碰撞
- CentOS 5.4下的Memcache安装步骤(Linux+Nginx+PHP+Memcached)
- Android开发 --微信支付开发(转载!)(开发工具:Eclipse)
- WCF系列学习5天速成
- 如何设置MySQL Workbench EER Diagram 尺寸?