工作规划

题目描述

n 台机器人正在完成任务。其中，第 i 台机器人需要工作 ti 分钟才能完成任务。这些机器人之间有一些前后约束，其中约束关系共有m条，每一条约束表示机器人 b 要在机器人 a 完成任务后才能开始工作。

请问，所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的，所有机器人一定在有限时间内完成工作。

输入格式

第一行：两个整数 n 和 m

第二行到第 n+1 行：每个机器人需要的时间 ti

接下来 m 行：每行有两个整数 a 和 b，表示第 b 台机器人必须要等第 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≤104

1≤m≤50,000

1≤ti≤105

1≤ai,bi≤n

限制

时间限制：1000ms

内存限制：512MiB

子序列

题目描述

给定两个整数序列，第一个序列长度为 n，第二个序列长度为 m。请问，这两个序列有多少种公共的子序列？输出数量模 998244353 的余数。

所谓子序列，是指从原序列中选择部分或全部元素组成新序列，这些元素在原序列中不必连续，但要保持在原序列中的顺序。只要下标不同，哪怕数字相同，也要算成不同的子序列。

输入格式

第一行：两个整数表示 n 与 m；

第二行： n 个数字 a1,a2,... ,an；

第三行：m 个数字 b1,b2,... ,bm；

输出格式

单个整数表示答案。

输入样例

4 3
3 4 6 2
3 3 2

输出样例

6

说明提示

1≤n,m≤2000

1≤ai,bj≤100,000

限制

时间限制：1000ms

内存限制：512MiB

联盟

题目描述

在国际会议上，共有 n 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况，请计算存在多少种合法的联盟分配方案。

输入格式

第一行：单个整数 n 表示国家数量

第二行到第 n 行：在第i+1 行有 n-i 个整数 ci,i+1,ci,i+2,…,ci,n，其中

ci,j=0-表示 i 号国家与 j 号国家不接壤

ci,j=1 表示 i 号国家与 j 号国家接壤

输出格式

单个整数：表示合法的联盟分配方案总数。

输入样例#1

3
1 1
1

输出样例#1

6

输入样例#2

4
1 1 1
1 1
1

输出样例#2

0

说明提示

数据范围

对于 50% 的数据，1≤n≤12

对于 100% 的数据，1≤n≤20

样例1说明

三国两两接壤，形成三角形。三个联盟的排列方案为 3!=6种。

限制

时间限制：1000ms

内存限制：512MiB

逻辑表达式

题目描述

给定一个逻辑表达式，以运算符做前缀的形式给出。它包含三种运算符：&、|、^：

& 表示逻辑与运算

| 表示逻辑或运算

^ 表示逻辑异或运算

表达式还包含三种基本逻辑值：0、1、?。

每个 ? 必须赋值成为 0 或 1 中的一种，请问有多少种不同的赋值方式，可以让整个逻辑表达式的值为 0？

由于答案可能很大，请输出方案数模1,000,000,007 的余数。

前缀表达式的定义如下：

0、1、? 都是前缀表达式；

如果 x，y 都是前缀表达式，则 &xy、｜xy、^xy 都是前缀表达式；

不满足以上两条规则的表达式都不是前缀表达式。

输入格式

单个字符串表示输入的前缀表达式

输出格式

单个整数：表示答案模 1,000,000,007 的余数。

输入样例#1

&??

输出样例#1

3

输入样例#2

||??|||?^?|0|1&???|??

输出样例#2

4

输入样例#3

|?^?|0|&??||?^?|1??

输出样例#3

64

说明提示

设 ∣s∣表示输入字符串的长度

50%的数据，1≤∣s∣<1,000

100%的数据，1≤∣s∣<200,000

限制

时间限制：1000ms

内存限制：512MiB