D

树形dp + 贪心

总节点数为奇数时返回-1

贪心：凑够偶数个节点就断开。

import sys
sys.setrecursionlimit(200000)

n = int(input())
from collections import defaultdict
road = defaultdict(list)
for _ in range(n-1):
    x,y = map(int,input().strip().split())
    road[x].append(y)
    road[y].append(x)

def dfs(node,last):
    t = 1
    res = 0
    for nxt in road[node]:
        if nxt == last:
            continue
        
        lt,lres = dfs(nxt,node)
        res += lres
        t += lt
        if lt % 2 == 0:
            res += 1
    return t,res
        

if n % 2 == 1:
    print(-1)
else:
    print(dfs(1,0)[1])

E

组合数学 + 乘法原理 + 枚举 + 逆元

枚举每一个数字，每个数字都有可能在第[1,k]位

mod = int(1e9+7)
n,k = map(int,input().strip().split())

# 预处理阶乘以及其逆元
max_n = int(n+1)
fac = [1] * (max_n+1)
facinv = [1] * (max_n+1)

for i in range(1,max_n+1):
    fac[i] = fac[i-1] * i % mod
    # python自带快速幂
    facinv[i] = pow(fac[i],mod-2,mod)


def myComb(n,m):    
    if m < 0 or n < m:
        return 0
    return fac[n] * facinv[m] * facinv[n-m] % mod


s = input().strip()

res = 0


for i,w in enumerate(s):
    num = int(w)
    l,r = i,n-i-1
    
    for p in range(min(l,k-1)+1):
        q = k - p - 1
        if q > r:
            continue
            
#         print(i,p,q)
        res += myComb(l,p)*myComb(r,q)*num*pow(10,k-p-1,mod)
        res %= mod
print(res)

F

期望概率数学题 + 记忆化搜索。

题目转化

首先获取x的质因子，有多少个2和3，若还有其它质因子，返回-1。 题目就转化为从(0,0) => (two,three)，一直投骰子，直到投到2和3的数目达到目标数。

要求两种极限，用作差法即可推出公式

    # 计算 (1+2q+3qq+4qqq...)
    def getNumQ(q):
        return pow(q*q-2*q+1,mod-2,mod)
#         return 1 / (q*q-2*q+1)

    # 计算 (1+q+qq+qqq...)
    def getQ(q):
        # (q^n-1)/(q-1)
        # 1 / (1-q)
        return pow(1-q,mod-2,mod)
#         return 1 / (1-q)

代码：

x = int(input())
mod = int(1e9+7)
two = 0
while x % 2 == 0:
    x //= 2
    two += 1

three = 0
while x % 3 == 0:
    x //= 3
    three += 1

if x > 1:
    print(-1)
else:
    # 计算 (1+2q+3qq+4qqq...)
    def getNumQ(q):
        return pow(q*q-2*q+1,mod-2,mod)
#         return 1 / (q*q-2*q+1)

    # 计算 (1+q+qq+qqq...)
    def getQ(q):
        # (q^n-1)/(q-1)
        # 1 / (1-q)
        return pow(1-q,mod-2,mod)
#         return 1 / (1-q)

    # 从(0,0) 抽到 (2,3)
    
    from functools import lru_cache 
    tgt = (two,three)
    @lru_cache(None)
    def dfs(a,b):
        if (a,b) == tgt:
            return 0
        
        res = 0
        
        if a == two:
            p = pow(3,mod-2,mod)
            q = 2*p % mod
            res += p * getNumQ(q) + p * getQ(q) * dfs(a,b+1)
            '''
            2/3 废牌 q
            1/3 需要 p
            
            p(1+dfs) + pq(2+dfs) + pqq(3+dfs)
            p(1+2q+3qq+...+  dfs+qdfs+qqdfs)
            '''
        # 同上
        elif b == three:
            p = pow(3,mod-2,mod)
            q = 2*p % mod
            res += p * getNumQ(q) + p * getQ(q) * dfs(a+1,b)
        else:
            '''
            1/3 废牌 q
            1/3 需要 p
            z = dfs(a+1,b)+dfs(a,b+1)
            
            p(2+z) + pq(4+z) + pqq(6+z)
            
            2p+4pq+6pqq + pz + pqz + pqqz
            2p(1+2q+3qq) + pz(1+q+qq)
            '''
            q = pow(3,mod-2,mod)
            p = q
            z = dfs(a+1,b)+dfs(a,b+1)
            res += 2*p*getNumQ(q) + p*z*getQ(q)
        res %= mod
        
        return res
    
    print(dfs(0,0))