bzoj1025题解
2024-10-07 20:37:26
【题意分析】
定义一个等价类为满足如下条件的一个极大的集合Q:∀t∈Q,k∈N+,若tk∈全集R,都成立tk∈Q。
给定n,记[1,n]∩N上所有排列置换的全集为R。求对于所有的等价类Q,card({x|x=card(Q),Q∈R})。
【解题思路】
很明显,一个排列置换能分解成一个或几个不相交的置换环,其所在等价类的元素个数即为所有置换环长度的最小公倍数。
显然,若一个置换所有置换环长度的最大公约数大于1,则一定有一个置换环长度的最大公约数等于1的所在等价类元素个数与之相同。
所以,我们只要统计只有互质且不等于1的长度的置换环的置换所在等价类元素个数即可。
这样问题就可以转化为如何拆分n使所有拆分出的数都是pk(p为互不相等的质数,k∈[1,+∞)∩N)。
先筛出[1,n]∩N范围内所有质数,然后DP,f[i][j]表示已经选到了第i个质数,可分配的长度还剩下j的剩余时的拆分数。
转移方程:f[i][j]=f[i-1][j]+Σf[i-1][j+p[i]k],时间复杂度O(nπ(n))。
【参考代码】
#pragma GCC optimize(2)
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#define REP(i,low,high) for(register int i=(low);i<=(high);++i)
using namespace std; static int n,cnt=; long long f[][]; bool isprime[]; int prime[]; long long DFS(const int &now,const int &rest)
{
if(now>cnt) return ; if(~f[now][rest]) return f[now][rest];
f[now][rest]=DFS(now+,rest);
for(register int i=prime[now];i<=rest;i*=prime[now])
{
f[now][rest]+=DFS(now+,rest-i);
}
return f[now][rest];
} int main()
{
scanf("%d",&n),memset(isprime,,sizeof isprime),memset(f,-,sizeof f);
REP(i,,n) if(isprime[i]) {REP(j,,n/i) isprime[i*j]=; prime[++cnt]=i;}
return printf("%lld\n",DFS(,n)),;
}
最新文章
- mac电脑http代理服务设置公司内网的相关配置
- PAT 1036. 跟奥巴马一起编程(15)
- PyQt4入门
- GDB 调试遇到??的问题
- ural 1219. Symbolic Sequence
- 仿Twitter登陆移动背景效果
- POJ 2318 TOYS &;&; POJ 2398 Toy Storage(几何)
- 8.11-8.16:usaco
- ubuntu各版本的区别
- 腾讯地图之Marker
- shell中 if else以及大于、小于、等于逻辑表达式介绍
- Abp(.NetCore)开发与发布过程2
- python全栈开发中级班全程笔记(第二模块、第四章(三、re 正则表达式))
- 昨天开始使用lr controller 已停止工作问题
- Struts2多文件上传原理和示例
- mysql5.7高版本加载低版本sql文件,时间不能为0000-00-00格式错误
- 4-51单片机ESP8266学习-AT指令(测试TCP服务器--使用串口调试助手--不连接路由器)
- MySql DATE_FORMAT函数用法
- 【BZOJ2662】【BeiJing wc2012】冻结 分层图 裸的!
- # 20155327 2016-2017-4 《Java程序设计》第9周学习总结