网站开发要,荆州市网站建设,建网站的平台,合肥做网站设计C - Distinct or Not 签到题#xff0c;注意大小写和以前的不一样
D - Dice in Line 签到题2#xff0c;用个窗口即可
E - Almost Everywhere Zero 数位DP#xff08;搜索#xff09;的例题 pos表示当前搜索到的位置#xff08;开始为0#xff0c;结束为n#xff09; …C - Distinct or Not 签到题注意大小写和以前的不一样
D - Dice in Line 签到题2用个窗口即可
E - Almost Everywhere Zero 数位DP搜索的例题 pos表示当前搜索到的位置开始为0结束为n num表示已经使用的非0数字个数 cap表示搜索是否被限制当之前搜索的数字比s小时cap0否则cap1开始时cap1
# -*- 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 ) C(rc,c) C(rc,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(r_2,c_2)-g(r_2,c_1-1)-g(r_1-1,c_2)g(r_1-1,c_1-1) g(r2,c2)−g(r2,c1−1)−g(r1−1,c2)g(r1−1,c1−1) 其中 g g g函数是从0,0到(r,c)点的所有组合数的和。 将g按列分解行也一样 得到 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 ) gC(0,0)C(1,0)...C(r,0)\\ C(1,1)C(2,1)...C(r1,1) \\ ....\\ C(1c,c)C(2c,c)...C(rc,c) gC(0,0)C(1,0)...C(r,0)C(1,1)C(2,1)...C(r1,1)....C(1c,c)C(2c,c)...C(rc,c) 每一行都可以规约为 C ( r c 1 , c 1 ) C(rc1, c1) C(rc1,c1) 这样可以写出一个 O ( n ) O(n) 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()
