一、简答题
1、1.# 子序列
## 题目描述
给定两个整数序列，第一个序列长度为 n*n*，第二个序列长度为 m*m*。请问，这两个序列有多少种公共的子序列？输出数量模 998244353998244353 的余数。
所谓子序列，是指从原序列中选择部分或全部元素组成新序列，这些元素在原序列中不必连续，但要保持在原序列中的顺序。只要下标不同，哪怕数字相同，也要算成不同的子序列。
## 输入格式
· 第一行：两个整数表示 n*n* 与 m*m*；
· 第二行： n*n* 个数字 a1,a2,⋯ ,an*a*1,*a*2,⋯,*an*；
· 第三行：m*m* 个数字 b1,b2,⋯ ,bm*b*1,*b*2,⋯,*bm*；
## 输出格式
单个整数表示答案。
## 输入样例
4 3
3 4 6 2
3 3 2
## 输出样例
6
## 说明提示
· 1≤n,m≤20001≤*n*,*m*≤2000
· 1≤ai,bj≤100,0001≤*ai*,*bj*≤100,000
## 限制
时间限制：1000ms
内存限制：512MiB
2、2.# 逻辑表达式
## 题目描述
给定一个逻辑表达式，以运算符做前缀的形式给出。它包含三种运算符：&、|、^：
· & 表示逻辑与运算
· | 表示逻辑或运算
· ^ 表示逻辑异或运算
表达式还包含三种基本逻辑值：0、1、?。
每个 ? 必须赋值成为 0 或 1 中的一种，请问有多少种不同的赋值方式，可以让整个逻辑表达式的值为 0？
由于答案可能很大，请输出方案数模 1,000,000,0071,000,000,007 的余数。
前缀表达式的定义如下：
· 0、1、? 都是前缀表达式；
· 如果 x，y 都是前缀表达式，则 &xy、｜xy、^xy 都是前缀表达式；
· 不满足以上两条规则的表达式都不是前缀表达式。
## 输入格式
单个字符串表示输入的前缀表达式
## 输出格式
单个整数：表示答案模 1,000,000,0071,000,000,007 的余数。
## 输入样例#1
&??
## 输出样例#1
3
## 输入样例#2
||??|||?^?|0|1&???|??
## 输出样例#2
4
## 输入样例#3
|?^?|0|&??||?^?|1??
## 输出样例#3
64
## 说明提示
设 ∣s∣∣*s*∣ 表示输入字符串的长度
· 50%50%的数据，1≤∣s∣<1,0001≤∣*s*∣<1,000
· 100%100%的数据，1≤∣s∣<200,0001≤∣*s*∣<200,000
## 限制
时间限制：1000ms
内存限制：512MiB
3、3.# 联盟
## 题目描述
在国际会议上，共有 n*n* 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况，请计算存在多少种合法的联盟分配方案。
## 输入格式
· 第一行：单个整数 n*n* 表示国家数量
· 第二行到第 n*n* 行：在第 i+1*i*+1 行有 n−i*n*−*i* 个整数 ci,i+1,ci,i+2,…,ci,n*ci*,*i*+1,*ci*,*i*+2,…,*ci*,*n*，其中
· ci,j=0*ci*,*j*=0 表示 i*i* 号国家与 j*j* 号国家不接壤
· ci,j=1*ci*,*j*=1 表示 i*i* 号国家与 j*j* 号国家接壤
## 输出格式
单个整数：表示合法的联盟分配方案总数。
## 输入样例#1
3
1 1
1
## 输出样例#1
6
## 输入样例#2
4
1 1 1
1 1
1
## 输出样例#2
0
## 说明提示
数据范围
· 对于 50%50% 的数据，1≤n≤121≤*n*≤12
· 对于 100%100% 的数据，1≤n≤201≤*n*≤20
样例1说明
三国两两接壤，形成三角形。三个联盟的排列方案为 3!=63!=6 种。
## 限制
时间限制：1000ms
内存限制：512MiB
4、4.# 工作规划
## 题目描述
n*n* 台机器人正在完成任务。其中，第 i*i* 台机器人需要工作 ti*ti* 分钟才能完成任务。这些机器人之间有一些前后约束，其中约束关系共有m*m*条，每一条约束表示机器人 b*b* 要在机器人 a*a* 完成任务后才能开始工作。
请问，所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的，所有机器人一定在有限时间内完成工作。
## 输入格式
第一行：两个整数 n*n* 和 m*m*
• 第二行到第 n+1*n*+1 行：每个机器人需要的时间 ti*ti*
• 接下来 m*m* 行：每行有两个整数 a*a* 和 b*b*，表示第 b*b* 台机器人必须要等第 a*a* 台机器人任务完成之后才能开始工作。
## 输出格式
单个整数，表示所有机器人任务完成最少需要花多少时间。
## 输入样例
10 9
3
29
1
35
18
22
8
29
4
12
3 2
4 8
1 7
6 5
7 10
8 1
10 9
2 4
5 3
## 输出样例
161
## 说明提示
1≤n≤1041≤*n*≤104
1≤m≤50,0001≤*m*≤50,000
1≤ti≤1051≤*ti*≤105
1≤ai,bi≤n1≤*ai*,*bi*≤*n*
## 限制
时间限制：1000ms
内存限制：512MiB
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
