不是自己的场，补一下题。

T1

小红和小紫拿到了一个正整数x，她们每次可以选择x的一个因子k（k>1），把x除以k，但要求k必须是素数。
小红先手，谁先不能操作谁输。假设两人都足够聪明，最终谁取得胜利？

共进行t次游戏。
输入描述：
第一行输入一个正整数t，代表游戏的轮数。
接下来的行，每行输入一个正整数x，代表小红和小紫拿到的正整数
1<t<10
1<x<1e9
输出描述：
对于每次游戏：
如果小红获胜，输出一行字符串“kou”
如果小紫获胜，输出一行字符串"yukari”

input:
2
5
12

output:
kou
kou

其实就是对x进行质因子分解，看有多少质因子，根据质因子数量判断胜负。

但是正常质因子分解是O(n)的，x在1e9以内，无法通过。我们可以只判断1e5以内的素数。因为必然不可能存在2个1e5以上的素数乘积乘出来x。如果1e5以内的筛完了，剩下的数字一定一个素数。

for _ in range(int(input())):
    x = int(input())
    c = 0
    while x % 2 == 0:
        c += 1
        x //= 2

    for i in range(3, 100001, 2):
        if x == 1: break
        while x % i == 0:
            c += 1
            x //= i
    if x > 1: c += 1
    print('kou' if c & 1 else "yukari")

T2

题目描述
小红拿到了一个数组，她想知道对于每个k（k∈[1，n]），有多少个长度为k的连续上升子数组？
输入描述：
第一行输入一个正整数n，代表数组的长度。
第二行输入n个正整数ai，代表小红拿到的数组。
1 <n,ai < 2 × 1e5
输出描述：
输出几个正整数，第个正整数代表长度为i的连续上升子数组数量。

input:
5
2 3 4 4 2

output:
5 2 1 0 0

双指针。假设以某元素为结尾可以达到长度为m的连续上升子数组，那么它一定可以达到1、2、3...m-1长度的，计算之后前缀和处理。

n = int(input())
*a, = map(int, input().split())
ans = [0] * (n + 1)
l = 0
pre = -1
for r, v in enumerate(a):
    if v <= pre:
        l = r
    pre = v
    ans[r - l + 1] += 1
for i in range(n - 1, 0, -1): ans[i] += ans[i + 1]
print(*ans[1:])

T3

小红定义一个字符串是好串，当且仅当每个字母出现的次数均为偶数。
小红拿到了一个字符串，她想知道该字符串有多少子序列是好串？
子序列的定义：字符串中按原串顺序取一些字母组成的字符串（在原串中可以不连续）。
例如，"arcaea"的子序列有"aaa"、"ace"等等。
输入描述：
一个长度不超过2e5的、仅由小写字母组成的字符串。
输出描述：
好子序列的数量。
由于答案可能会很大，请对1e9+7取模后再输出。

input:
ababa

output:
7

不难看出，因为要组成的是子序列，只需要判断每个字符出现的次数即可。比如：某字符出现了m次，那么该字符出现在好子序列中的次数必然为0、2、4、6...、m次。因为出现的字符在什么位置并不重要，我们只需要在这所有字符里面任意选0、2...、m个。

根据如上思路，对每一个字符都进行如上处理，可以得到一个：(字符1出现0次+字符1出现2次+...)*(字符2出现0次+字符2出现2+...)*...

可以写出如下代码：

from collections import Counter
from math import factorial

def C(n, m):
    return factorial(n) // (factorial(n - m) * factorial(m))

s = input()
c = Counter(s)
mod = int(1e9 + 7)
if all([v == 1 for v in c.values()]):
    print(0)
else:
    ans = 1
    for v in c.values():
        cnt = 0
        for j in range(0, v + 1, 2):
            cnt += C(v, j)
        ans *= cnt
        ans %= mod

    print((ans - 1 + mod) % mod)

这样会超时，需要推一下公式简化复杂度。推导过程略过不谈，可以证明如下性质，假设某数字为m

• C(m,0)+C(m,1)+...+C(m,m)=2^m
• 如果m是偶数：C(m,0)+C(m,2)+C(m,4)+...+C(m,m)=2^(m-1)
• 如果m是奇数：C(m,0)+C(m,2)+C(m,4)+...+C(m,m-1)=2^(m-1)

可自行证明。

根据如上证明，可以写出

s = input()
mod = int(1e9 + 7)
c = Counter(s)
ans = 1
for v in c.values():
    ans *= pow(2, v - 1, mod)
    ans %= mod
print((ans - 1 + mod) % mod)

看了一眼群友的思路，其实可以再进一步，可以直接算出来：

s = input()
mod = int(1e9 + 7)
print(((1 << (len(s) - len(set(s)))) - 1 + mod) % mod)

但是我不会推）