【HDU】5321 Beautiful Set【枚举k求贡献,欧拉函数应用】

2024-09-05 14:08

本文主要是介绍【HDU】5321 Beautiful Set【枚举k求贡献,欧拉函数应用】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门: 【HDU】5321 Beautiful Set

my  code:

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 100005 ;
const int mod = 258280327 ;bool prime[MAXN] ;
int phi[MAXN] ;
int cnt[MAXN] ;
int id[MAXN] ;
int f[MAXN] ;
int vf[MAXN] ;
int n ;void exgcd ( int a , int b , int& x , int& y ) {if ( b ) {exgcd ( b , a % b , y , x ) ;y -= a / b * x ;} else x = 1 , y = 0 ;
}int inv ( int a ) {int x , y , b = mod ;exgcd ( a , b , x , y ) ;if ( x < 0 ) x += mod ;return x ;
}int cmp ( int a , int b ) {return cnt[a] > cnt[b] ;
}void calc () {for ( int i = 1 ; i < MAXN ; ++ i ) {id[i] = i ;for ( int j = i + i ; j < MAXN ; j += i ) {cnt[i] += cnt[j] ;}}sort ( id + 1 , id + MAXN , cmp ) ;
}void preprocess () {f[0] = vf[0] = 1 ;for ( int i = 1 ; i < MAXN ; ++ i ) {phi[i] = i ;f[i] = ( LL ) i * f[i - 1] % mod ;vf[i] = inv ( f[i] ) ;}for ( int i = 2 ; i < MAXN ; ++ i ) if ( !prime[i] ) {for ( int j = i ; j < MAXN ; j += i ) {phi[j] = phi[j] / i * ( i - 1 ) ;prime[j] = 1 ;}}
}int c ( int a , int b ) {return ( LL ) f[a] * vf[b] % mod * vf[a - b] % mod ;
}void solve () {int x ;int ans1 = 0 , ans2 = 0 ;clr ( cnt , 0 ) ;for ( int i = 1 ; i <= n ; ++ i ) {scanf ( "%d" , &x ) ;cnt[x] ++ ;}calc () ;for ( int i = 1 ; i < MAXN ; ++ i ) {int tmp = 0 ;for ( int j = 1 ; j < MAXN ; ++ j ) {int idx = id[j] ;if ( cnt[idx] < i ) break ;int t = ( LL ) c ( cnt[idx] , i ) * phi[idx] % mod ;tmp = ( tmp + t ) % mod ;}ans2 = ( ans2 + ( LL ) i * tmp ) % mod ;tmp = ( LL ) tmp * f[i] % mod * f[n - i + 1] % mod ;ans1 = ( ans1 + tmp ) % mod ;}if ( ans1 > ans2 ) printf ( "Mr. Zstu %d\n" , ans1 ) ;else if ( ans1 < ans2 ) printf ( "Mr. Hdu %d\n" , ans2 ) ;else printf ( "Equal %d\n" , ans1 ) ;
}int main () {preprocess () ;while ( ~scanf ( "%d" , &n ) ) solve () ;return 0 ;
}

这篇关于【HDU】5321 Beautiful Set【枚举k求贡献,欧拉函数应用】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139172

相关文章

Python内置函数之classmethod函数使用详解

《Python内置函数之classmethod函数使用详解》:本文主要介绍Python内置函数之classmethod函数使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 类方法定义与基本语法2. 类方法 vs 实例方法 vs 静态方法3. 核心特性与用法(1编程客

Python函数作用域示例详解

《Python函数作用域示例详解》本文介绍了Python中的LEGB作用域规则,详细解析了变量查找的四个层级,通过具体代码示例,展示了各层级的变量访问规则和特性,对python函数作用域相关知识感兴趣... 目录一、LEGB 规则二、作用域实例2.1 局部作用域(Local)2.2 闭包作用域(Enclos

Python中re模块结合正则表达式的实际应用案例

《Python中re模块结合正则表达式的实际应用案例》Python中的re模块是用于处理正则表达式的强大工具,正则表达式是一种用来匹配字符串的模式,它可以在文本中搜索和匹配特定的字符串模式,这篇文章主... 目录前言re模块常用函数一、查看文本中是否包含 A 或 B 字符串二、替换多个关键词为统一格式三、提

MySQL count()聚合函数详解

《MySQLcount()聚合函数详解》MySQL中的COUNT()函数,它是SQL中最常用的聚合函数之一,用于计算表中符合特定条件的行数,本文给大家介绍MySQLcount()聚合函数,感兴趣的朋... 目录核心功能语法形式重要特性与行为如何选择使用哪种形式?总结深入剖析一下 mysql 中的 COUNT

Java MQTT实战应用

《JavaMQTT实战应用》本文详解MQTT协议,涵盖其发布/订阅机制、低功耗高效特性、三种服务质量等级(QoS0/1/2),以及客户端、代理、主题的核心概念,最后提供Linux部署教程、Sprin... 目录一、MQTT协议二、MQTT优点三、三种服务质量等级四、客户端、代理、主题1. 客户端(Clien

MySQL 中 ROW_NUMBER() 函数最佳实践

《MySQL中ROW_NUMBER()函数最佳实践》MySQL中ROW_NUMBER()函数,作为窗口函数为每行分配唯一连续序号,区别于RANK()和DENSE_RANK(),特别适合分页、去重... 目录mysql 中 ROW_NUMBER() 函数详解一、基础语法二、核心特点三、典型应用场景1. 数据分

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C

Python get()函数用法案例详解

《Pythonget()函数用法案例详解》在Python中,get()是字典(dict)类型的内置方法,用于安全地获取字典中指定键对应的值,它的核心作用是避免因访问不存在的键而引发KeyError错... 目录简介基本语法一、用法二、案例:安全访问未知键三、案例:配置参数默认值简介python是一种高级编