UPC 2019年第二阶段我要变强个人训练赛第十六场

分类: IT文章 • 2025-01-11 10:52:19

传送门：

　　[1]:UPC比赛场

　　[2]:UPC补题场

F.gu集合（数论）

•题目描述

 1 题目描述：
 2 Dew有一个长为n的集合S。
 3 有一天，他想选k个不同的元素出来做游戏。
 4 但是Dew只有两只手，所以他只能先选出k个元素，然后拿出这k个元素中最小的两个。
 5 事实上，Dew更喜欢这k个元素中第二小的那个。
 6 因此他会记一个集合T的第二小值为g(T)。
 7 此时Dew可以获得c^g(T)!的得分，其中c是一个常数，!表示阶乘。
 8 现在你需要求出Dew从集合S中选出k个元素后，他的期望得分对998244353取模的结果。
 9 
10 输入：
11 输入共两行。
12 第一行三个正整数n,k,c，分别表示集合S的大小，Dew要选的元素个数，和常数c。
13 第二行n个互不相同的正整数ai，表示集合S中的元素。保证集合s升序。
14 
15 输出：
16 输出一行一个非负整数，表示Dew的期望得分对998244353取模的结果。

题目描述、输入、输出

1 样例输入
2 5 3 2
3 1 2 3 4 5
4 
5 样例输出
6 803628674

样例输入输出

样例解释

•题解

　　在tyk的帮助下顺利AC；

　　下面开始扯淡；

　　第 i 个数 ai 可以作为第二小的数的条件是：

　　　　①存在比 a_i 小的数，即 i > 1；

　　　　②比 a_i 大的数的个数要多于 k-2，即 n-i ≥ k-2；

　　对于满足条件的 ai，共有

　　，

　　那么得到 ai 的概率为：

　　

　　最终答案就是 ∑ P_i×c^a_i!；

•细节处理

　　对于除法取模Pi%MOD直接用逆元处理即可，关键是 c^a_i! 该如何处理？

　　根据费马小定理：a^p-1 ≡ 1 (mod p) 可知循环节为 p-1（a^p-1 ≡ a⁰ (mod p) ⇔ 0~p-2 为一个循环） ；

　　即 a^x ≡ a^x%(p-1) (mod p) ；

　　那么 c^a_i! ≡ c^a_i!%(p-1)(mod p)；

　　而 a_i!%(p-1) 可以提前预处理出来；

•Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int MOD=998244353;
 5 const int maxn=5e5+50;
 6 
 7 int n,k,c;
 8 int a[maxn];
 9 ll fact[maxn];///fact只开到5e5就足够了，如果开到1e7，返回内存超限
10 ll g[(int)1e7+50];
11 
12 ll qPow(ll a,ll b)
13 {
14     ll ans=1;
15     a %= MOD;
16     while(b)
17     {
18         if(b&1)
19             ans=ans*a%MOD;
20 
21         a=a*a%MOD;
22         b >>= 1;
23     }
24     return ans;
25 }
26 int Solve()
27 {
28     fact[0]=g[0]=1;
29     for(int i=1;i < maxn;++i)
30         fact[i]=i*fact[i-1]%MOD;
31     for(int i=1;i <= (int)1e7;++i)
32         g[i]=i*g[i-1]%(MOD-1);
33 
34     ll ans=0;
35     for(int i=2;i <= n;++i)
36     {
37         if(n-i < k-2)
38             break;
39 
40         ll b=fact[k-2]*fact[n-i-k+2]%MOD*fact[n]%MOD;///概率的分母取模后的结果
41         ///qPow(b,MOD-2)为逆元
42         ll p=(i-1)*fact[n-i]%MOD*fact[k]%MOD*fact[n-k]%MOD*qPow(b,MOD-2)%MOD;
43 
44         ans += p*qPow(c,g[a[i]]);
45         ans %= MOD;
46     }
47     return ans;
48 }
49 int main()
50 {
51     scanf("%d%d%d",&n,&k,&c);
52     for(int i=1;i <= n;++i)
53         scanf("%d",a+i);
54 
55     printf("%d
",Solve());
56 
57     return 0;
58 }

View Code