Bobo has a positive-definite n×n matrix A and an n-dimension vector b. He would like to find x1,x2,…,xn where x1,x2,…,xn∈R, i=1∑nj=1∑naijxixj⩽1 and i=1∑nbixi is maximum.
It can be shown that (i=1∑nbixi)2=QP, which is rational.
Find the value of P⋅Q−1mod998244353.
输入描述
The input consists of several test cases terminated by end-of-file.
The first line of each test case contains an integer n.
The i-th of the following n lines contains n integers ai1,ai2,⋯,ain.
The last line contains n integers b1,b2,⋯,bn. 1⩽n⩽200, 0⩽∣aij∣,∣bi∣⩽109,aij=aji. i=1∑nj=1∑naijxixj>0, for any x∈Rn.
$ \mathrm{det}(A) \not\equiv 0 \pmod {998244353}$.
The sum of n does not exceed 104.
输出描述
For each test case, print an integer which denotes the result.
For a string x, Bobo defines x∞=xxx⋯x, which is x repeats for infinite times, resulting in a string of infinite length.
Bobo has two strings a and b. Find out the result comparing a∞ and b∞ in lexicographical order.
You can refer the wiki page for further information of Lexicographical Order.
输入描述
The input consists of several test cases terminated by end-of-file.
The first line of each test case contains a string a, and the second line contains a string b. 1⩽∣a∣,∣b∣⩽105. a,b consists of lower case letters. The total length of input strings does not exceed 2×106.
输出描述:
For each test case, print = (without quotes) if a∞=b∞. Otherwise, print < if a∞<b∞, or > if a∞>b∞.
Bobo has a network of n nodes and m arcs. The i-th arc goes from the ai-th node to the bi-th node, with cost ci.
Bobo also asks q questions. The i-th question is specified by two integers ui and vi, which is to ask the minimum cost to send one unit of flow from the 1-st node to the n-th node, when all the edges have capacity viui (a fraction).
You can refer the wiki page for further information of Minimum-cost Flow.
输入描述
The input consists of several test cases terminated by end-of-file.
The first line of each test case contains two integers n and m. The i-th of the following m lines contains three integers ai,bi and ci. The next line contains an integer q. The i-th of the last q lines contains two integers ui and vi. 2⩽n⩽50, 1⩽m⩽100, 1⩽ai,bi⩽n, 1⩽ci⩽105. 1⩽q⩽105, 0⩽ui⩽vi⩽109, vi>0 .
The sum of m does not exceed 104. The sum of q does not exceed 106.
输出描述
For each test case, print q fractions (or NaN, if it is impossible to send one unit of flow) which denote the answer.
示例1
输入
1 2 3 4 5 6 7 8 9 10 11
2 1 1 2 2 1 1 1 2 2 1 2 1 1 2 2 3 1 2 2 3 1 4
输出
1 2 3 4
2/1 3/2 4/3 NaN
分析
运行 q 次最小费用流算法显然是不现实的,应当考虑的是:运行一次最小费用流,进行一些预处理,使得每次询问时能够在较短时间内给出答案。
题中有一重要信息:每条边的容量都相同。设这个容量为 cap 。利用 MCMF 算法求最小费用最大流,会不断用 SPFA 算法寻找单位费用和最小的增广路;由于每条边的容量都为 cap,故每条边只会存在满流或零流的情况,每次增广获得的最大流改进量恒为 cap 。若源点流量为 flow 且 flow 不超过最大流,就是最小费用流模型。对于这样特殊的(每条边容量都为 cap)最小费用流模型,仍然可以利用 MCMF 算法,每次增广后相当于将流量 flow 减少 cap,产生的费用是增广路单位费用和与 cap 的乘积;而最后一次增广时费用的改进量为剩余流量 flowmodcap 与增广路单位费用和的乘积。进行多轮增广,直至剩余流量为零,就能得到最小费用流。
由于每条边的费用 ci 是不变的,因此不论 cap 如何变化,只要源点流量不超过当前网络的最大流,对 q 次询问中的每一张网络进行 MCMF 算法,找到的增广路都是相同的,且每条增广路的顺序也保持不变。因此,只需要进行一次最小费用流的计算,记录下每一条增广路的单位费用即可,根据 MCMF 算法原理,这些增广路是按照单位费用和由小到大获得的,排序操作是多余的。
不妨令每条边的容量为 1,求一次最小费用最大流,记录下每一条增广路的单位费用。对于每一次询问,源点流量为 1,每条边容量为 vu。为了减少计算的误差,可以将所有数量扩大 v 倍,即网络中源点流量为 v,每条边容量为 u。若源点流量 v 不超过网络最大流,那么求固定流量 v 的最小费用流得过程中,增广路为最小费用最大流得增广路子集,且每一轮 SPFA 获得的增广路一定是当前所有存在的增广路中费用最小的。每一轮增广,源点流量就减少 u,相应的费用为该增广路的单位费用与 u 的乘积;最后一次增广,源点流量减少 umodv,对应费用也要相应改变;最终,源点流量为 0,求得最小费用流 ans。vans 即为一次询问的答案。
Bobo has a graph with n vertices and m edges where the i-th edge is between the vertices ai and bi. Find out whether is possible for him to choose some of the edges such that the i-th vertex is incident with exactly di edges.
输入描述
The input consists of several test cases terminated by end-of-file.
The first line of each test case contains two integers n and m.
The second line contains n integers d1,d2,⋯,dn.
The i-th of the following m lines contains two integers ai and bi. 1⩽n⩽50, 1⩽m⩽100, 1⩽di⩽2, 1⩽ai,bi⩽n. ai=bi, {ai,bi}={aj,bj} for i=j. The number of tests does not exceed 100.
输出描述
For each test case, print Yes without quotes if it is possible. Otherwise, print No without quotes.
示例1
输入
1 2 3 4 5 6 7 8 9 10
2 1 1 1 1 2 2 1 2 2 1 2 3 2 1 1 2 1 3 2 3
输出
1 2 3
Yes No Yes
分析
首先考虑最简单的情况。如果 ∀i∈N∗ 且 1⩽i⩽n,有 di=1,那么此题可以转化为一般图最大匹配问题,若最大匹配为完备匹配,则存在满足条件的方案。
进一步考虑当 di=2 时的操作。不妨进行拆点,将点 a 拆成点 a 和 a′,让两者各自找一个点匹配,仍然转化为一般图最大匹配问题。但是拆点后,由点 a 拆开的两个点可能正好和由点 b 拆开的两点相匹配,为了防止此类情况发生,应当再增加一些限制。
我们可以将一条边 e(e 的两端分别为点 a,b)化为两点 e 和 e′,e 和 a,a′ 连边,e′ 和 b,b′ 连边,e 和 e′ 之间连边。若 e 与 e′ 之间匹配,那么 a,a′,b,b′ 四点都不会与之匹配,在原图中的意义为 a,b 之间的边不是一条匹配边;反之,若 a(a′) 与 e 匹配,b(b′) 与 e′ 匹配,在原图上代表 a,b 之间的边是一条匹配边。假如 a 要与 b 匹配,a′ 要与 b′ 匹配,那么 e 和 e′ 就连了不止一条匹配边,这种情况在最大匹配中是不会出现的,因此将边化点的操作是成功的。
建图完成后,若一般图最大匹配为完备匹配,则存在满足条件的方案。
Given n, find the value of ∫01(x−x2)ndx.
It can be proved that the value is a rational number qp.
Print the result as p⋅q−1mod998244353.
输入描述
The input consists of several test cases and is terminated by end-of-file.
Each test case contains an integer n. 1⩽n⩽106. The number of test cases does not exceed 105.
输出描述
For each test case, print an integer which denotes the result.