【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

相关文章

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

MySql基本查询之表的增删查改+聚合函数案例详解

《MySql基本查询之表的增删查改+聚合函数案例详解》本文详解SQL的CURD操作INSERT用于数据插入(单行/多行及冲突处理),SELECT实现数据检索(列选择、条件过滤、排序分页),UPDATE... 目录一、Create1.1 单行数据 + 全列插入1.2 多行数据 + 指定列插入1.3 插入否则更

Redis中Stream详解及应用小结

《Redis中Stream详解及应用小结》RedisStreams是Redis5.0引入的新功能,提供了一种类似于传统消息队列的机制,但具有更高的灵活性和可扩展性,本文给大家介绍Redis中Strea... 目录1. Redis Stream 概述2. Redis Stream 的基本操作2.1. XADD

JSONArray在Java中的应用操作实例

《JSONArray在Java中的应用操作实例》JSONArray是org.json库用于处理JSON数组的类,可将Java对象(Map/List)转换为JSON格式,提供增删改查等操作,适用于前后端... 目录1. jsONArray定义与功能1.1 JSONArray概念阐释1.1.1 什么是JSONA

PostgreSQL中rank()窗口函数实用指南与示例

《PostgreSQL中rank()窗口函数实用指南与示例》在数据分析和数据库管理中,经常需要对数据进行排名操作,PostgreSQL提供了强大的窗口函数rank(),可以方便地对结果集中的行进行排名... 目录一、rank()函数简介二、基础示例:部门内员工薪资排名示例数据排名查询三、高级应用示例1. 每

nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析(结合应用场景)

《nginx-t、nginx-sstop和nginx-sreload命令的详细解析(结合应用场景)》本文解析Nginx的-t、-sstop、-sreload命令,分别用于配置语法检... 以下是关于 nginx -t、nginx -s stop 和 nginx -s reload 命令的详细解析,结合实际应

全面掌握 SQL 中的 DATEDIFF函数及用法最佳实践

《全面掌握SQL中的DATEDIFF函数及用法最佳实践》本文解析DATEDIFF在不同数据库中的差异,强调其边界计算原理,探讨应用场景及陷阱,推荐根据需求选择TIMESTAMPDIFF或inte... 目录1. 核心概念:DATEDIFF 究竟在计算什么?2. 主流数据库中的 DATEDIFF 实现2.1

MySQL中的LENGTH()函数用法详解与实例分析

《MySQL中的LENGTH()函数用法详解与实例分析》MySQLLENGTH()函数用于计算字符串的字节长度,区别于CHAR_LENGTH()的字符长度,适用于多字节字符集(如UTF-8)的数据验证... 目录1. LENGTH()函数的基本语法2. LENGTH()函数的返回值2.1 示例1:计算字符串