AtCoder ABC154

C - Distinct or Not
签到题，注意大小写和以前的不一样

D - Dice in Line
签到题2，用个窗口即可

E - Almost Everywhere Zero
数位DP（搜索）的例题
pos表示当前搜索到的位置（开始为0，结束为n）
num表示已经使用的非0数字个数
cap表示搜索是否被限制，当之前搜索的数字比s小时cap=0，否则cap=1，开始时cap=1

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @file     : atcoder.py
# @software : PyCharmimport bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(1000)def main():items = sys.version.split()if items[0] == '3.10.6':fp = open("in.txt")else:fp = sys.stdins = fp.readline().strip()n = len(s)k = int(fp.readline())@lru_cache(None)def get(pos, cap, num):if num == k:return 1if pos == n:return 0ret = 0si = int(s[pos])if cap == 0:ret += get(pos + 1, cap, num)ret += get(pos + 1, cap, num + 1) * 9else:if si == 0:ret += get(pos + 1, cap, num)else:ret += get(pos + 1, cap, num + 1)ret += get(pos + 1, 0, num + 1) * (si - 1)ret += get(pos + 1, 0, num)return retans = get(0, 1, 0)print(ans)if __name__ == "__main__":main()

F - Many Many Paths

组合数学
显见
1.每个(r,c)点上的数都是一个组合数$C(r+c,c)$
2.可以用容斥原理将ans拆成$g(r_2,c_2)-g(r_2,c_1-1)-g(r_1-1,c_2)+g(r_1-1,c_1-1)$
其中$g$函数是从（0,0）到(r,c)点的所有组合数的和。
将g按列分解（行也一样）
得到$$\begin{gathered} g=C(0,0)+C(1,0)+...+C(r,0)+ \\ C(1,1)+C(2,1)+...+C(r+1,1)+ \\ .... \\ C(1+c,c)+C(2+c,c)+...+C(r+c,c) \end{gathered}$$
每一行都可以规约为$C(r+c+1,c+1)$
这样可以写出一个$O(n)$算法

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @file     : atcoder.py
# @software : PyCharmimport bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(1000)def main():items = sys.version.split()if items[0] == '3.10.6':fp = open("in.txt")else:fp = sys.stdinr1, c1, r2, c2 = map(int, fp.readline().split())mod = 10 ** 9 + 7fac = [1] * 2000002iv = [1] * 2000002for i in range(1, 2000002):fac[i] = fac[i - 1] * i % moddef pw(a, x):if x == 1:return atemp = pw(a, x >> 1)if x & 1:return temp * temp * a % modelse:return temp * temp % modiv[1000001] = pw(fac[1000001], mod - 2)for i in range(1000000, -1, -1):iv[i] = (iv[i + 1] * (i + 1)) % moddef cmb(x, y):return fac[x] * iv[y] * iv[x - y] % moddef get(r, c):ret = 0for i in range(1, r + 2):ret = (ret + cmb(i + c, c)) % modreturn reta0, a1, a2, a3 = get(r2, c2), get(r1 - 1, c2), get(r2, c1 - 1), get(r1 - 1, c1 - 1)ans = (a0 - a1 - a2 + a3) % modprint(ans)if __name__ == "__main__":main()