板子练习

基础算法：

一维前缀和

import sys
input=lambda:sys.stdin.readline().strip()
n=input()
a=[0]+list(map(int,input().split()))
m=int(input())
for i in range(1,len(a)):
    a[i]+=a[i-1]
for i in range(m):
    l,r=list(map(int,input().split()))
    print(a[r]-a[l-1])

二位前缀和（xy1-1）

#对于多个数读入时，不需要n, m, q = list(map(int, input_str.split()))，直接map映射即可
import sys
input=lambda:sys.stdin.readline().strip()
n,m,q=map(int,input().split())
a=[[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
    row=[0]+list(map(int,input().split()))
    for j in range(1,m+1):
        a[i][j]=row[j]
        a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]
for i in range(m):
    x1,y1,x2,y2=map(int,input().split())
    print(a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1])

一维差分

"""
d要多开
d差分数组进行前缀和得到操作后的数组
diff是关键
"""

import sys
input=lambda:sys.stdin.readline().strip()
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
d=[0]*(len(a)+1)
def diff(i,j,c):
    d[i]+=c
    d[j+1]-=c
for i in range(1,n+1):
    diff(i,i,a[i])
for i in range(m):
    l,r,c=map(int,input().split())
    diff(l,r,c)
for i in range(1,n+1):
    d[i]+=d[i-1]
print(*d[1:n+1])

二维差分

"""
xy2+1
d要多开一位
diff是构造的关键
"""
import sys
input=lambda:sys.stdin.readline().strip()
n,m,q=map(int,input().split())
a=[[0]*(m+1) for i in range(n+1)]
d=[[0]*(m+2) for i in range(n+2)]

def diff(x1,y1,x2,y2,c):
    d[x1][y1]+=c
    d[x2+1][y1]-=c
    d[x1][y2+1]-=c
    d[x2+1][y2+1]+=c

for i in range(1,n+1):
    row=[0]+list(map(int,input().split()))
    for j in range(1,m+1):
        a[i][j]=row[j]
        diff(i,j,i,j,a[i][j])

for i in range(q):
    x1,y1,x2,y2,c=map(int,input().split())
    diff(x1,y1,x2,y2,c)

for i in range(1,n+1):
    for j in range(1,m+1):
        d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1]
        print(d[i][j],end=" ")
    print()

双指针（滑动窗口）

最长不重复子序列 给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

(本体也可用快慢指针结合桶思想)

"""
具体步骤
下面是使用滑动窗口算法解决问题的一般步骤：
1. 初始化指针和数据结构
初始化两个指针 left 和 right，通常都从数组或字符串的起始位置开始（即 left = 0，right = 0）。
根据问题的需要，初始化一个数据结构（如哈希表、集合、数组等）来记录窗口内的元素信息。
2. 移动右指针扩展窗口
不断移动右指针 right，将新的元素加入窗口中。
在加入新元素后，更新窗口内的元素信息，例如更新哈希表中元素的计数，或者判断新元素是否满足特定条件。
3. 判断窗口是否需要收缩
根据问题的条件，判断窗口是否需要收缩。如果窗口内的元素不满足条件，就需要移动左指针 left 来缩小窗口。
在缩小窗口的过程中，更新窗口内的元素信息，例如减少哈希表中元素的计数。
4. 更新结果
在每次移动指针后，根据问题的要求更新最终结果。例如，更新最长或最短子数组的长度，或者记录满足条件的子数组。
5. 重复步骤 2 - 4
重复上述步骤，直到右指针 right 到达数组或字符串的末尾。"""

import sys
input=lambda:sys.stdin.readline().strip()
n=input()
a=list(map(int,input().split()))
res=0
wind=set()
l,r=0,0
while r<len(a):
    if a[r] not in wind:
        wind.add(a[r])
    else:
        while a[r] in wind :
               wind.remove(a[l])
               l+=1
        wind.add(a[r])
    res=max(res,r-l+1)
##    print(a[l:r+1])
    r+=1
print(res)

数据结构

栈的基本操作（多组操作数据）

## 题目描述

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式， push 和 pop 。push 一个值会将其压入栈顶，而 pop 则会将栈顶 top 的值弹出。现在我们就来验证一下堆栈的使用。

## 输入格式

本题有多组测试数据 。对于每组测试数据，第一行是一个正整数 n，0<n≤10000n，0<n≤10000 ( n=0n=0 结束)。而后的 nn 行，每行的第一个字符可能是 P 或者 O 或者 A ；如果是 P ，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是 O ，表示将栈顶的值 pop 出来，如果堆栈中没有元素时，忽略本次操作；如果是 A ，表示询问当前栈顶的值，如果当时栈为空，则输出 E 。堆栈开始为空。

## 输出格式

对于每组测试数据，根据其中的命令字符来处理堆栈；并对所有的 A 操作，输出当时栈顶的值，每个占据一行，如果当时栈为空，则输出 E 。当每组测试数据完成后，输出一个空行。

## 样例

### 输入#1

none 5 P 75 O O P 60 A 7 A O P 73 P 49 A O P 3 0

### 输出#1

```none
60

E
49
```

## 数据范围

无

#列表尾部模拟栈顶
while True:
    try:
        n=int(input())
        if n==0:
            break
        st=[]
##        列表尾部是栈顶
        for i in range(n):
            op=list(input().split())
            if op[0]=='P':
                st.append(int(op[1]))
            elif op[0]=='O':
                if st:
                    st.pop()
            else:
                if st:
                    print(st[-1])
                else:
                    print('E')
        print()
    except EOFError:
        break

队列操作（deque模拟）

实现一个队列，队列初始为空，支持四种操作：

1. push x – 向队尾插入一个数 xx；
2. pop – 从队头弹出一个数，如果队列为空，则忽略该操作；
3. empty – 判断队列是否为空；
4. query – 查询队头元素，如果队列为空，则提示错误信息。

现在要对队列进行 MM 个操作，其中的每个操作 33 和操作 44 都要输出相应的结果。

## 输入格式

第一行包含整数 MM，表示操作次数。

接下来 MM 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

## 输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值，如果队列为空，则输出 ERR。

## 样例

## 输入数据 1

input1 10 push 6 empty query pop empty push 3 push 4 pop query push 6

## 输出数据 1

output1 NO 6 YES 4

## 数据范围

1≤M≤1000001≤M≤100000，1≤x≤1091≤x≤109

import sys
from collections import deque
q=deque()
m=int(input())
for i in range(m):
    op=list(input().split())
    if op[0]=="push":
        q.append(int(op[1]))
    elif op[0]=="pop":
        if q:
            q.popleft()
    elif op[0]=="empty":
        if q:
            print("NO")
        else:
            print("YES")
    else:
        if q:
            print(q[0])
        else:
            print("ERR")

单调栈

import os
import sys

n = int(input())
a = list(map(int, input().split()))

# 统一更新完答案再入栈
st = [] 
# 左边第一个比其大的数字
zd = [-1] * n
for r, x in enumerate(a):
    while st and a[st[-1]] <= x:
        # 只要新来的数大于等于之前的，之前的数就没用了
        # 横看成岭侧成峰你，新来的高一点，之前的就全看不到了
        st.pop()
    if st:
        zd[r] = a[st[-1]]
    st.append(r)

st = []
# 右边第一个比其大的数字
yd = [-1] * n
for r, x in enumerate(a):
    #如果新来的数比他大，那么就直接找到答案了，在弹出的同时进行答案的赋值
    while st and x > a[st[-1]]:
        yd[st.pop()] = x
    st.append(r)

st = []
# 左边第一个比其小的数字
zx = [-1] * n
for r, x in enumerate(a):
    while st and a[st[-1]] >= x:
        st.pop()
    if st:
        zx[r] = a[st[-1]]
    st.append(r)

st = []
# 右边第一个比其小的数字
yx = [-1] * n
for r, x in enumerate(a):
    while st and x < a[st[-1]]:
        yx[st.pop()] = x
    st.append(r)

print(*zd)
print(*yd)
print(*zx)
print(*yx)

单调队列

求一个窗口内的最大值和最小值

import os
import sys
from collections import deque

# 读取输入的 n 和 k
n, k = map(int, input().split())
# 读取输入的数组 a
a = list(map(int, input().split()))

# 用于存储每个窗口的最大值
resmax = []
# 初始化单调队列
q = deque()

# 处理最大值的滑动窗口
for r, x in enumerate(a):
    # 当队列不为空且当前元素大于队列末尾元素时，弹出队列末尾元素
    while q and x > a[q[-1]]:
        q.pop()
    # 将当前元素的索引加入队列
    q.append(r)
    # 如果队列头部元素超出当前窗口范围，弹出队列头部元素

#当前窗口的右边界是 r，那么左边界就是 r - k + 1。
#当q[0]<r-k+1时滑出，这个逻辑更容易理解

    if q[0]<r-k+1:
        q.popleft()
    # 当窗口形成后，将队列头部元素对应的数组值加入结果列表
    if r >= k - 1:
        resmax.append(a[q[0]])
# 0到k-1，r==k-1时形成了窗口


# 用于存储每个窗口的最小值
resmin = []
# 重新初始化单调队列
q = deque()

# 处理最小值的滑动窗口
for r, x in enumerate(a):
    # 当队列不为空且当前元素小于队列末尾元素时，弹出队列末尾元素
    while q and x < a[q[-1]]:
        q.pop()
    # 将当前元素的索引加入队列
    q.append(r)
    # 如果队列头部元素超出当前窗口范围，弹出队列头部元素
    if q[0]<r-k+1:
        q.popleft()
    # 当窗口形成后，将队列头部元素对应的数组值加入结果列表
    if r >= k - 1:
        resmin.append(a[q[0]])

# 输出每个窗口的最小值
print(*resmin)
# 输出每个窗口的最大值
print(*resmax)

字符串哈希

1. 不能有字母映射成0

   如a=0，则aa=0冲突

2. 假定rp无敌

   p=131或13331

   Q=2^26

3. h[i]=h[i−1]×p+ord(str[i])

4. p[i]存储的是P^i的mod

5. L−R的hash值=h[R]−h[L]×p(R−L+1) 提升差距的位次

N = 100010
P = 131
Q = 1 << 64
h = [0]*N
p = [0]*N

def find(l, r):
    return (h[r] - h[l - 1] * p[r - l + 1]) % Q

n,m = map(int,input().split())

s = ' '+ input()

p[0] = 1
for i in range(1,n+1):
    p[i] = p[i - 1] * P % Q   #预处理p的位次
    h[i] = (h[i - 1] * P + ord(s[i])) % Q  #字符哈希

while m:
    m -= 1
    l1, r1, l2, r2 = map(int,input().split())
    if find(l1, r1) == find(l2, r2):
        print("Yes")
    else:
        print("No")

并查集

n, m = map(int, input().split())
p = list(range(n + 1))
朴素并查集
# 返回x的祖宗节点
def find(x):
    if x != p[x]:
        p[x] = find(p[x])
    return p[x]

# 合并a和b所在的两个集合
def union(a, b):
    ra = find(a)
    rb = find(b)
    if ra != rb:
        p[ra] = rb

# 处理操作
for i in range(m):
    op = list(input().split())
    if op[0] == 'M':
        union(int(op[1]), int(op[2]))
    else:
        if find(int(op[1])) == find(int(op[2])):
            print("Yes")
        else:
            print("No")



维护 size 的并查集

# 读取输入的 n 和 m
n, m = map(int, input().split())
# p 存储每个点的祖宗节点，size 只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
p = list(range(n + 1))
size = [1] * (n + 1)

# 返回 x 的祖宗节点
def find(x):
    if x != p[x]:
        p[x] = find(p[x])
    return p[x]

# 合并 a 和 b 所在的两个集合
def union(a, b):
    ra = find(a)
    rb = find(b)
    if ra != rb:
        size[rb] += size[ra]
        p[ra] = rb


# 示例操作
for i in range(m):
    op = input().split()
    if op[0] == 'M':
        union(int(op[1]), int(op[2]))
    else:
        if find(int(op[1])) == find(int(op[2])):
            print("Yes")
        else:
            print("No")
维护到祖宗节点距离的并查集

# 读取输入的 n 和 m
n, m = map(int, input().split())
# p 存储每个点的祖宗节点，d 存储 x 到 p[x] 的距离
p = list(range(n + 1))
d = [0] * (n + 1)

# 返回 x 的祖宗节点
def find(x):
    if p[x] != x:
        u = find(p[x])
        d[x] += d[p[x]]
        p[x] = u
    return p[x]

# 合并 a 和 b 所在的两个集合
def union(a, b, distance):
    pa = find(a)
    pb = find(b)
    p[pa] = pb
    d[pa] = distance


# 示例操作
for i in range(m):
    op = input().split()
    if op[0] == 'M':
        union(int(op[1]), int(op[2]), int(op[3]))
    else:
        if find(int(op[1])) == find(int(op[2])):
            print("Yes")
        else:
            print("No")

树状数组

#单点修改，区间查询（利用前缀和思想）
import sys
input=lambda:sys.stdin.readline().strip()
def lowbit(x):
    return x&(-x)
def query(x):
    ans=0
    #求区间从x到1
    while x:
        ans+=tree[x]
        x-=lowbit(x)
    return ans

def add(x,y):
    #单点修改，从小到大
    while x<=n:
        tree[x]+=y
        x+=lowbit(x)


n,q=map(int,input().split())
tree=[0]*(n+1)
a=[0]+list(map(int,input().split()))
for i in range(1,n+1):
    add(i,a[i])
for i in range(q):
    op=list(input().split())
    if op[0]=="1":
        add(int(op[1]),int(op[2]))
    else:
        print(query(int(op[2]))-query(int(op[1])-1))

#区间修改，单点查询（差分思想）
import sys
input = lambda: sys.stdin.readline().strip()


def lowbit(x):
    return x & (-x)


def query(x):
    ans = 0
    while x:
        ans += tree[x]
        x -= lowbit(x)
    return ans


def add(x, y):
    while x <= n:
        tree[x] += y
        x += lowbit(x)


n, q = map(int, input().split())
tree = [0] * (n + 1)
a = [0] + list(map(int, input().split()))
preNum = 0
for i in range(1, n + 1):
    num = a[i]
    add(i, num - preNum)
    preNum = num

for i in range(q):
    op = list(input().split())
    if op[0] == "1":
        x, y, k = int(op[1]), int(op[2]), int(op[3])
        add(x, k)
        add(y + 1, -k)
    else:
        x = int(op[1])
        print(query(x))

区间查询，区间修改
import sys
# 定义输入函数，使用 sys.stdin.readline().strip() 可以更高效地读取输入
input = lambda: sys.stdin.readline().strip()

# 计算 x 的最低位 1 所代表的数值，用于树状数组的操作
def lowbit(x):
    return x & (-x)

# 查询树状数组中前 x 个元素的和
def query(tree, x):
    ans = 0
    while x:
        ans += tree[x]
        # 减去最低位 1，向前查询
        x -= lowbit(x)
    return ans

# 向树状数组中第 x 个元素加上 y，同时更新相关节点
def add(tree, x, y):
    while x <= n:
        tree[x] += y
        # 加上最低位 1，向后更新
        x += lowbit(x)

# 读取输入的数列长度 n 和询问个数 q
n, q = map(int, input().split())
# 两个树状数组，tree1 用于维护差分的和，tree2 用于辅助计算区间和
tree1 = [0] * (n + 1)
tree2 = [0] * (n + 1)
# 读取初始数列，并在开头添加一个 0 元素，方便后续计算
a = [0] + list(map(int, input().split()))

# 初始化差分树状数组
for i in range(1, n + 1):
    # 计算相邻元素的差值
    diff = a[i] - a[i - 1]
    # 将差值添加到 tree1 中
    add(tree1, i, diff)
    # 将差值乘以当前索引添加到 tree2 中
    add(tree2, i, diff * i)

# 计算前缀和
def prefix_sum(x):
    return (x + 1) * query(tree1, x) - query(tree2, x)

# 计算区间 [l, r] 的和
def range_query(l, r):
    return prefix_sum(r) - prefix_sum(l - 1)

# 对区间 [l, r] 内的元素都加上 k
def range_modify(l, r, k):
    # 更新 tree1 中 l 位置的差分
    add(tree1, l, k)
    # 更新 tree1 中 r + 1 位置的差分，以保证只影响 [l, r] 区间
    add(tree1, r + 1, -k)
    # 更新 tree2 中 l 位置的辅助值
    add(tree2, l, k * l)
    # 更新 tree2 中 r + 1 位置的辅助值
    add(tree2, r + 1, -k * (r + 1))

# 处理 q 个询问
for _ in range(q):
    # 读取询问信息，并将其转换为整数列表
    op = list(map(int, input().split()))
    if op[0] == 1:
        # 若为区间修改操作，获取区间 [l, r] 和要添加的值 k
        l, r, k = op[1:]
        range_modify(l, r, k)
    else:
        # 若为区间查询操作，获取区间 [l, r]
        l, r = op[1:]
        # 计算并输出区间和
        print(range_query(l, r))

图论

SPFA检测负环

from collections import deque

# 读取输入
n, m = map(int, input().split())

# 构建图的邻接表
e = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    e[u].append([v, w])

# 定义无穷大
INF = int(1e18)

def spfa():
    # 记录每个节点入队的次数（用于检测负环）
    cnt = [0] * (n + 1)
    # 记录到每个节点的最短距离
    d = [INF] * (n + 1)
    # 标记节点是否在队列中
    vis = [False] * (n + 1)
    # 初始化队列
    q = deque()

    # 将所有节点加入队列（虚拟源点优化，检测全图负环）
    for i in range(1, n + 1):
        d[i] = 0
        vis[i] = True
        cnt[i] += 1
        q.append(i)

    while q:
        u = q.popleft()
        vis[u] = False

        # 遍历当前节点的所有邻接边
        for v, w in e[u]:
            # 松弛操作：如果通过u到达v的距离更短，则更新v的距离
            if d[u] + w < d[v]:
                d[v] = d[u] + w
                if not vis[v]:
                    vis[v] = True
                    q.append(v)
                    cnt[v] += 1


                    #Bellman-Ford：如果在第n轮松弛时仍能更新距离，则存在负环（n-1轮是正常的）
                    #SPFA：如果某个节点入队次数超过n次，则存在负环（入队n次是正常的）
                    # 负环检测：如果某个节点入队次数超过节点数，则存在负环
                    if cnt[v] > n:
                        return False
    return True

# 判断是否存在负权回路并输出结果
print("No" if spfa() else "Yes")

flody

n,m,t=map(int,input().split())
INF=int(1e9)
g=[[INF]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b,c=map(int,input().split())
    g[a][b]=min(c,g[a][b])
for i in range(1, n + 1):
    g[i][i] = 0
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
for i in range(t):
    a,b=map(int,input().split())
    print(g[a][b]if g[a][b]!=INF else "-1")

### Kruskal 最小生成树

n, m = map(int, input().split())

# 存储边的列表，每个边包含权重、起点和终点
edges = []
for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((w, u, v))  # 存储边

# 按边权从小到大排序
edges.sort()

# 初始化并查集的父节点数组，p[x] 表示节点 x 的父节点
p = list(range(n + 1))

# 查找节点 x 的根节点，并进行路径压缩
def find(x):
    if x != p[x]:
        p[x] = find(p[x])  # 路径压缩
    return p[x]

res = 0  # 最小生成树的总权值
cnt = 0  # 已选择的边数

# Kruskal 算法核心逻辑
for w, u, v in edges:
    root_a = find(u)
    root_b = find(v)
    # 如果两个节点不在同一个集合中，则选择这条边
    if root_a != root_b:
        p[root_a] = root_b  # 合并两个集合
        res += w
        cnt += 1
        # 当选择的边数达到 n-1 条时，最小生成树构建完成
        if cnt == n - 1:
            break

# 输出结果
if cnt == n - 1:
    print(res)
else:
    print("impossible")

### 拓扑序

from collections import deque
n,m=map(int,input().split())
e=[[] for i in range(n+1)]  # 邻接表存储图结构
ru=[0]*(n+1)  # 入度数组
for i in range(m):
    a,b=map(int,input().split())
    e[a].append(b)  # 添加边a->b
    ru[b]+=1  # 更新节点b的入度

res=[]  # 存储拓扑排序结果
q=deque()  # 队列用于BFS
for  i in range(1,n+1):  # 将所有入度为0的节点入队
    if ru[i]==0:
        q.append(i)

while q:  # BFS主循环
    u=q.popleft()  # 取出队首节点
    res.append(u)  # 加入拓扑序列
    for v in e[u]:  # 遍历当前节点的所有邻接节点
        ru[v]-=1  # 邻接节点入度减1
        if ru[v]==0:  # 若邻接节点入度变为0则入队
            q.append(v)

# 判断是否存在环并输出结果
if len(res)==n:
    print("loop not exist.")
    print(*res)  # 输出拓扑序列
else:
    print("loop exist.")  # 存在环

数学

进制转换

import sys
input =lambda:sys.stdin.readline().strip()
int_to_char="0123456789ABCDEF"
dis={}
for idx,val in enumerate(int_to_char):
    dis[val]=idx
##print(dis)
#注意翻转
def into_char():
    x,k=map(int,input().split())
    res=""
    while x:
        res+=int_to_char[x%k]
        x//=k
    print(res[::-1])

def into_int():
    s,k=list(input().split())
    k=int(k)
    res=0
    for r,x in enumerate (s):
        res=res*k+dis[x]
    print(res)
into_int()

线性筛

线性筛的核心思想是让每个合数只被其最小质因数筛去，这样就能保证每个数仅被筛选一次，从而让时间复杂度达到线性，也就是 (O(n))。

# 初始化一个空列表 primes 用于存储素数
primes = []
# 初始化一个布尔类型的列表 is_prime，长度为 n + 1，初始值都为 True
is_prime = [True] * (n + 1)
# 0 和 1 不是素数，将其标记为 False
is_prime[0] = is_prime[1] = False
# 从 2 开始遍历到 n
for i in range(2, n + 1):
    # 如果 i 是素数，则添加到 primes 列表中
    if is_prime[i]:
        primes.append(i)
    # 从小到大遍历列表中的素数
    for p in primes:
        # 如果 i * p 超过了 n，则跳出循环
        if i * p > n:
            break
        # 将 i * p 标记为非素数
        is_prime[i * p] = False
        #此时 p 一定是i的最小质因子，也是p*i的最小质因子
        if i % p == 0:
            break

GCD / LCM

import math
a,b=map(int,input().split())
print(math.gcd(a,b))
print(a*b//math.gcd(a,b))

快速幂/逆元(费马小定理)

int(pow(a,k,p))

int(pow(i,p-2,p))#p要求为质数

组合数

卢卡斯定理

def get(n, m, p, f, g):
    return f[n] * g[m] * g[n - m] % p

def lucas(n, m, p, f, g):
    if m == 0:
        return 1
    return lucas(n // p, m // p, p, f, g) * get(n % p, m % p, p, f, g) % p


n = int(input())
for i in range(n):
    n, m, p = map(int, input().split())
    f = [0] * (p + 1)
    g = [0] * (p + 1)
    f[0], g[0] = 1, 1
    for i in range(1, p + 1):
        f[i] = f[i - 1] * i % p
        g[i] = g[i - 1] * pow(i, p - 2, p) % p

    print(lucas(n, m, p, f, g))

无需模p
a, b = map(int, input().split())
up = 1
down = 1
for i in range(a - b + 1, a + 1):
    up *= i
for i in range(1, b + 1):
    down *= i
print(up // down)

递推式
N = 2010
mod = int(1e9 + 7)
c = [[0 for i in range(N)] for j in range(N)]


def gen():
    global c
    for i in range(N):
        for j in range(i + 1):
            if j == 0:
                c[i][j] = 1
            else:
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod

n = int(input())
gen()
for k in range(n):
    a, b = map(int, input().split())
    print(c[a][b])

预处理阶乘和逆元

N = 100010
mod = int(1e9 + 7)
fact = [0] * N
infact = [0] * N


fact[0], infact[0] = 1, 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i % mod
    infact[i] = infact[i - 1] * pow(i, mod - 2, mod) % mod

n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    print((fact[a] * infact[b] % mod * infact[a - b]) % mod)