题目描述

小明所在的幼儿园有$n$个小朋友，第$i$个小朋友有$a_i$颗糖。

今天，幼儿园老师要选一些三人小组出去吃糖。如果一个小组的三个小朋友所带的糖的总数恰好是$3$的倍数，那么这三个小朋友分到的糖是一样的，都会感到开心。

每个小朋友只能参加最多一个小组（也可以不参加）。

请帮助幼儿园老师组成最多的小组，使得每个小组的小朋友都是开心的。

输入格式

第一行输入$n$。

第二行输入$n$个数，$a_1,...,a_n$。

输出格式

第一行输出$ans$，表示最多能组成多少组。

接下来$ans$行，每行三个数字，表示这一组三个小朋友的编号。

如果有多解，输出任意一种方案即可。

样例输入 #1

3
1 2 5

样例输出 #1

0

样例输入 #2

6
1 2 3 1 5 6

样例输出 #2

2
3 1 2
6 4 5

数据范围

对于30%的数据：$n\leq 20$。

对于100%的数据：$n\leq 10^5,1\leq a_i\leq 10^5$。

题目描述

小明和小红在打乒乓球比赛。

规则是这样的：对于每一颗球，如果小红赢，小红得一分，如果小明赢，小明得一分。谁的得分首先大于等于$11$分，且比对方的得分高出至少$2$分，则赢得此局比赛。

在记录了$n$颗球的胜负关系后，聪明的裁判员大翼发现：对于任意第$i(i>k)$颗球来说，第$i$颗球的胜负关系，与第$i-k$颗球的胜负关系一模一样。因此，大翼只记录了前$k$颗球的胜负关系。

然而，在记录完毕后，他发现一个重要的问题：他忘记统计两个人分别赢了几局了！

这真是好尴尬啊。还是请你帮他还原一下最终的结果吧！

输入格式

第一行输入$n,k$，如题所述。

接下来一行一个长度为$k$的字符串，第$i$个字符是A表示第$i$局小明赢了，B表示第$i$局小红赢了。

输出格式

第一行输出两个整数X:Y，分别表示最后小明/小红赢了几局。

样例输入 #1

20 3
AAB

样例输出 #1

1:0

样例解释 #1

最终的序列实际上是AABAABAABAABAABAABAA，在第$16$颗球结束时，小明和小红的部分是$11:5$，小明赢得一局。在$20$颗球记录完毕时，当前比分是$3:1$。

样例输入 #2

1000 6
AABBAB

样例输出 #2

24:23

数据范围

对于5%的数据：字符串中只包含A。

对于30%的数据：$n\leq 10^7$。

对于另外30%的数据：保证无论是谁得分到达$11$分时，必定取得这局的胜利。

对于另外15%的数据：保证$n$是$k$的倍数。

对于100%的数据：$n\leq 10^{18},k\leq 10^5$。

题目描述

小明，没错又是小明。

他有一个长度为$n$的数组，还有$k$个运算符| 以及$n-k-1$个运算符&。此处and和or就是二进制下的与以及或操作。

小明需要把这$n$个数用上述$n-1$个符号从左到右连接起来，然后从左到右计算结果。

显然，不同的安排方式可能导致不同的结果。

例如 $a=[1,2,5]$，有一个&和一个|，那么如果是1&2|5，结果是$5$，如果是1|2 &5，结果是$0$。

小明希望得到最大的结果，在这个基础上，希望整个表达式的字典序尽量小（此处|的字典序小于&），请帮助小明计算最小的字典序。

输入格式

第一行输入$n,k$。

接下来一行输入$n$个正整数表示$a_i$。

输出格式

第一行输出最大的结果。

第二行输出一个字符串表示字典序最小的符号序列。

样例输入 #1

4 2
1 3 5 7

样例输出 #1

7
||&

样例解释 #1

三种不同的符号序列产生的结果：

||&=7,|&|=7,&||=7。

都是$7$，||&字典序最小。

样例输入 #2

4 1
1 3 5 7

样例输出 #2

7
&&|

样例解释 #3

三种不同的符号序列产生的结果：

&&|=7,&|&=5,|&&=1。

数据范围

对于30%的数据：$n\leq 20$。

对于另30%的数据：$n\leq 1000,0\leq a_i<128$。

对于另10%的数据：$k=1$。

对于100%的数据：$n\leq 2\times 10^5,0\leq a_i<2^{60}$。

题目描述

小明在家打游戏，楼下在跳广场舞，吵死了。

有$n$个舞者排成一排，第$i$个舞者的属性是$a_i$。

在每一刻，一个人可以邀请自己左侧或者右侧相邻的人跳舞，如果这两个人的属性的最大公约数$>1$，则这个人很开心，然后会开心回家睡觉。此时，他离开了跳舞的队列，他左右侧的两个人现在相邻了。

广场舞可太吵了，问：假设小明可以安排跳舞的顺序，最多能让多少个人回家睡觉！

输入格式

第一行输入$n$。

接下来一行输入$n$个正整数表示$a_i$。

输出格式

一个数字表示答案。

样例输入 #1

5
1 6 3 2 4

样例输出 #1

3

样例解释 #1

让$3$先跟$2$跳舞，跳完走人。让$4$跟$2$跳舞，跳完走人。让$5$跟$2$跳舞，跳完走人。

剩下俩人，分别属性是$1,6$，他俩去广场上站着吧。

样例输入 #2

6
6 2 3 4 15 9

样例输出 #2

5

数据范围

对于30%的数据：$n\leq 20$。

对于70%的数据：$n\leq 100$。

对于100%的数据：$n\leq 500,1\leq a_i\leq 10^9$。

题目描述

赵喜娜有一个音乐播放器（赛后回家看）。

他的音乐播放器里面一共有$n$首歌，赵喜娜对第$i$首歌的喜爱程度是$a_i$。

赵喜娜今天选择了随机播放模式，具体地：

他的播放器会随机播放一首歌，等这首歌结束后，会继续随机播放下一首歌（不排除这首歌跟刚那首歌一样的可能性）。

当赵喜娜首次听到第$i$首歌的时候，他的愉悦程度会增加$a_i$，第二次及以后听到，则没有反应了。

当赵喜娜听完某首歌后，总的愉悦程度$\geq S$，赵喜娜就会开心的关掉播放器，完成今天的听歌。

问：赵喜娜听到的最后一首歌是第$i$首歌的概率是多少？

可以证明结果一定可以被化简为一个分数$\frac{x}{y}$，你需要输出$x/y \mod 998244353$。

提示：解此题的时候也许你可能不得不在$\ mod \ p$意义下除以一个数字（此处$p$是质数），那么你就需要逆元这个东西。

如果你不会逆元的话，简单介绍一下逆元：

假设你现在需要求$x/y\mod \ p$的结果，比如$3*5/3\mod 7$，如果你直接每步$mod\ 7$计算的话，答案是$(3*5\%7)/3 \% 7=0$。但实际上结果显然是$5$。

所以你需要更高级的东西，费马小定理：假设有质数$p$以及非负整数$a<p$，那么$a^{p-1}\%p=1$。也就是说，$a^{p-1}$实际上就是$\mod\ p$意义下的数字$1$。

那么$x/y\mod p$就可以写成$x\times y^{p-1}/y\mod p$。反正乘以$1$等于没乘对吧。

也就是说，我们如果要$/y$的话，可以当成要乘以$y^{p-2}$。

$y^{p-2}$就是$y$在$\mod p$意义下的逆元。

输入格式

第一行输入$n,S$。

接下来一行输入$n$个正整数表示$a_i$。

输出格式

$n$个数字表示答案。

样例输入 #1

4 3
1 2 3 4

样例输出 #1

582309206 582309206 915057324 915057324

样例解释 #1

想要以$2$结尾或者以$1$结尾，赵喜娜必须只听到歌$1$和歌$2$。

那么听歌序列只能是$111112$或者是$222221$这样。

$12$的概率是$\frac{1}{4}^2$。

$112$的概率是$\frac{1}{4}^3$。

$1112$的概率是$\frac{1}{4}^4$。

...

所以最终以$2$结尾的概率是$\frac{\frac{1}{16}}{1-\frac{1}{4}}=\frac{1}{12}$。

以$1$结尾的概率同样是$\frac{1}{12}$。

$\frac{1}{12}$在$\mod p$意义下是$1\times 12^{p-2}=582309206$。

以$3$和$4$结尾的概率一样，都是$\frac{5}{12}$。

样例输入 #2

4 7
1 2 3 4

样例输出 #2

582309206 582309206 748683265 83187030

数据范围

对于15%的数据：$n\leq 8,S\leq 10$。

对于40%的数据：$n\leq 20,S\leq 100$。

对于60%的数据：$n\leq 20$。

对于另10%的数据：$a_i$只有两种取值。

对于85%的数据：$n\leq 100,S\leq 1000$。

对于100%的数据：$n\leq 100,S\leq 10000,1\leq a_i\leq S,\sum a_i \geq S$。