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

传送门：

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

•感悟

　　满满的数论知识，有些知识点早就学过，但就学死了，没能做到活用；

　　看来，还是得多做题，多总结，要活学活用；

H.奇迹（暴力+欧拉筛法）

•题目描述

题目描述
相信奇迹的人，本身就和奇迹一样了不起。——笛亚 《星游记》
我们称一个日期为一个八位数，第1~4位构成年，第5~6位构成月，第7~8位构成日，不足位数用0补足。
同时，要求日期所代表的这一天真实存在，且年的范围为1~9999。
出现奇迹的日期都存在相同的特点：由“日”组成的两位数，由“月+日”组成的四位数，由“年+月+日”组成的八位数均为质数。
但并不是所有存在这样特点的日期都一定会出现奇迹。
现在，你得到了一个可能会出现奇迹的日期，然而不幸的是这个日期却是残缺的，八位中可能有若干位无法确定。
你需要知道这个日期有多少种可能，这样你才能做好充足的准备去迎接奇迹的到来。

输入
本题有多组数据。
第一行一个正整数T，表示数据组数。
接下来的T行，每行一个八位字符串。
其中第i位如果为 '-'，则表示日期的第i位无法确定，否则表示日期的第i位为字符串中第i位上的数字。

输出
对每组数据，一行一个整数，表示答案。

题目描述、输入、输出

样例输入
2
53-7-3-7
20190629

样例输出
6
0

样例输入输出

53-7-3-7 的  种可能的日期如下：
53070307
53070317
53170307
53370307
53570317
53770307

一共10个测试点，记c为八位字符串中 '-' 的个数。
对前9个测试点，在第i个测试点中保证c=i-1。
对100%的数据保证1≤T≤10。

提示

•题解（暴力+欧拉筛法预处理）

　　枚举所有可能的日期，并判断①其是否符合字符串 s；②符合正常日期；

　　在满足上述条件的请款下，并判断其是否符合出现奇迹的要求，如果符合，ans++；

•Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mem(a,b) memset(a,b,sizeof(a))
 4 const int day[2][20]={{0,31,28,31,30,31,30,31,31,30,31,30,31},
 5                       {0,31,29,31,30,31,30,31,31,30,31,30,31}/**闰年*/};
 6 char s[100];
 7 
 8 int prime[10000000];
 9 bool isPrime[99991232];
10 void Prime()
11 {
12     mem(isPrime,true);
13     int cnt=0;
14     isPrime[1]=false;
15     for(int i=2;i < 99991232;++i)
16     {
17         if(isPrime[i])
18             prime[++cnt]=i;
19         for(int j=1;j <= cnt && prime[j]*i < 99991232;++j)
20         {
21             isPrime[i*prime[j]]=false;
22             if(i%prime[j] == 0)
23                 break;
24         }
25     }
26 }
27 bool isRun(int y)
28 {
29     return (y%100 != 0 && y%4 == 0)||(y%400 == 0);
30 }
31 bool isSatY(int y)
32 {
33     if(s[1] != '-' && (s[1]-'0') != y/1000)
34         return false;
35     if(s[2] != '-' && (s[2]-'0') != y/100%10)
36         return false;
37     if(s[3] != '-' && (s[3]-'0') != y/10%10)
38         return false;
39     if(s[4] != '-' && (s[4]-'0') != y%10)
40         return false;
41 
42     return true;
43 }
44 bool isSatM(int m)
45 {
46     if(s[5] != '-' && (s[5]-'0') != m/10)
47         return false;
48     if(s[6] != '-' && (s[6]-'0') != m%10)
49         return false;
50 
51     return true;
52 }
53 bool isSatD(int d)
54 {
55     if(s[7] != '-' && (s[7]-'0') != d/10)
56         return false;
57     if(s[8] != '-' && (s[8]-'0') != d%10)
58         return false;
59 
60     return true;
61 }
62 int Solve()
63 {
64     int ans=0;
65     for(int y=1;y <= 9999;y++)
66     {
67         if(!isSatY(y))///判断y是否符合s
68             continue;
69 
70         for(int m=1;m <= 12;m++)
71         {
72             if(!isSatM(m))///判断m是否符合s
73                 continue;
74 
75             for(int d=1;d <= day[isRun(y)][m];d++)///判断m是否符合s
76                 if(isSatD(d) && isPrime[m*100+d] && isPrime[d] && isPrime[y*10000+m*100+d])
77                     ans++;
78         }
79     }
80     return ans;
81 }
82 int main()
83 {
84     Prime();///预处理1~99991232内的所有素数
85 
86     int T;
87     scanf("%d",&T);
88     while(T--)
89     {
90         scanf("%s",s+1);
91         printf("%d
",Solve());
92     }
93     return 0;
94 }

View Code

•思考

上述代码耗时：

如果将三重循环的顺序颠倒以下，改成如下顺序：

 1 int Solve()
 2 {
 3     int ans=0;
 4     for(int d=1;d <= 31;++d)
 5     {
 6         if(!isPrime[d] || !isSatD(d))
 7             continue;
 8         for(int m=1;m <= 12;++m)
 9         {
10             if(!isPrime[d+m*100] || !isSatM(m))
11                 continue;
12             for(int y=1;y <= 9999;++y)
13             {
14                 if(!isPrime[y*10000+m*100+d] || d > day[isRun(y)][m] || !isSatY(y))
15                     continue;
16                 ans++;
17             }
18         }
19     }
20     return ans;
21 }

View Code

耗时：

快了将近三百毫秒！！！

对于此题而言，颠倒一下顺序，枚举的情况会少一下；

•坑

起初，我用vector<>存储的prime，返回 TLE，改成 int 后，AC；

看来，动态分配空间还是比提前计算出所需的空间慢一些；