编程题 共4道
给定两个整数序列，第一个序列长度为 nn，第二个序列长度为 mm。请问，这两个序列有多少种公共的子序列？输出数量模 998244353998244353 的余数。
所谓子序列，是指从原序列中选择部分或全部元素组成新序列，这些元素在原序列中不必连续，但要保持在原序列中的顺序。只要下标不同，哪怕数字相同，也要算成不同的子序列。
· 第一行：两个整数表示 nn 与 mm；
· 第二行： nn 个数字 a1,a2,⋯ ,ana1,a2,⋯,an；
· 第三行：mm 个数字 b1,b2,⋯ ,bmb1,b2,⋯,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
给定一个逻辑表达式，以运算符做前缀的形式给出。它包含三种运算符：&、|、^：
· & 表示逻辑与运算
· | 表示逻辑或运算
· ^ 表示逻辑异或运算
表达式还包含三种基本逻辑值：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 的余数。
&??
3
||??|||?^?|0|1&???|??
4
|?^?|0|&??||?^?|1??
64
设 ∣s∣∣s∣ 表示输入字符串的长度
· 50%50%的数据，1≤∣s∣<1,0001≤∣s∣<1,000
· 100%100%的数据，1≤∣s∣<200,0001≤∣s∣<200,000
在国际会议上，共有 nn 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况，请计算存在多少种合法的联盟分配方案。
· 第一行：单个整数 nn 表示国家数量
· 第二行到第 nn 行：在第 i+1i+1 行有 n−in−i 个整数 ci,i+1,ci,i+2,…,ci,nci,i+1,ci,i+2,…,ci,n，其中
· ci,j=0ci,j=0 表示 ii 号国家与 jj 号国家不接壤
· ci,j=1ci,j=1 表示 ii 号国家与 jj 号国家接壤
单个整数：表示合法的联盟分配方案总数。
1 1
1
1 1 1
0
数据范围
· 对于 50%50% 的数据，1≤n≤121≤n≤12
· 对于 100%100% 的数据，1≤n≤201≤n≤20
样例1说明
三国两两接壤，形成三角形。三个联盟的排列方案为 3!=63!=6 种。
nn 台机器人正在完成任务。其中，第 ii 台机器人需要工作 titi 分钟才能完成任务。这些机器人之间有一些前后约束，其中约束关系共有mm条，每一条约束表示机器人 bb 要在机器人 aa 完成任务后才能开始工作。
请问，所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的，所有机器人一定在有限时间内完成工作。
第一行：两个整数 nn 和 mm • 第二行到第 n+1n+1 行：每个机器人需要的时间 titi • 接下来 mm 行：每行有两个整数 aa 和 bb，表示第 bb 台机器人必须要等第 aa 台机器人任务完成之后才能开始工作。
单个整数，表示所有机器人任务完成最少需要花多少时间。
10 9
29
35
18
22
8
12
3 2
4 8
1 7
6 5
7 10
8 1
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