2020牛客暑期多校训练营（第一场）

D. Quadratic Form $\looparrowright$

题目描述

Bobo has a positive-definite $n \times n$ matrix $A$ and an $n$ -dimension vector $b$ . He would like to find $x_1, x_2, \dots, x_n$ where $x_1, x_2, \dots, x_n \in \mathbb{R}$ , $\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n a_{ij} x_i x_j \leqslant 1$ and $\sum\limits_{i = 1}^n b_i x_i$ is maximum.
It can be shown that $\left(\sum\limits_{i = 1}^n b_i x_i\right)^2 = \frac{P}{Q}$ , which is rational.
Find the value of $P \cdot Q^{-1} \bmod 998244353$ .

输入描述

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 $a_{i1}, a_{i2}, \cdots, a_{i n}$ .
The last line contains $n$ integers $b_1, b_2, \cdots, b_n$ .
$1 \leqslant n \leqslant 200$ , $0 \leqslant |a_{i j}|, |b_{i}| \leqslant 10^9$ , $a_{ij} =a_{ji}$ .
$\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n a_{i j} x_i x_j > 0$ , for any $x \in \mathbb{R}^n$ .
$ \mathrm{det}(A) \not\equiv 0 \pmod {998244353}$.
The sum of $n$ does not exceed $10^4$ .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

输出

1
2
3

0
2
623902721

分析

将题目转化为约束条件下的最值问题。此处只讨论极值，不讨论边界可能存在的最值。
考虑到约束条件 $\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n a_{ij} x_i x_j \leqslant 1$ 为不等式约束，可以添加 $\mathrm{KKT}$ 条件，利用拉格朗日乘数法求解。

首先需要讨论矩阵 $A$ 的一些性质。由于 $\mathrm{det}(A) \not\equiv 0 \pmod {998244353}$ ，故 $A$ 可逆。根据 $a_{ij}\in\mathbb Z$ 且 $a_{ij}=a_{ji}$ ，得 $A$ 为实对称矩阵，继而 $A^{-1}$ 也为实对称矩阵。又有 $\sum\limits_{i = 1}^n \sum\limits_{j = 1}^n a_{i j} x_i x_j > 0$ ，故 $A$ 为正定矩阵，继而 $A^{-1}$ 也为正定矩阵。上述性质都会在接下来的推导中涉及。
定义： $x=\begin{pmatrix}x_1\\x_2\\\vdots\\x_n\end{pmatrix}$ ， $b=\begin{pmatrix}b_1\\b_2\\\vdots\\b_n\end{pmatrix}$ 。则有约束条件 $x^TAx\leqslant1$ ，要求最大值的表达式为 $x^Tb$ 或 $b^Tx$ 。

令 $L(x_1,x_2,\cdots,x_n,\lambda)=\sum\limits_{i=1}^n b_ix_i+\lambda\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^{n}a_{ij}x_ix_j-1\right)$ ；有 $\mathrm{KKT}$ 方程组如下。

$\begin{cases}\frac{\partial L}{\partial x_i}=0\quad i=1,2\cdots,n\\x^TAx\leqslant 1\\\lambda\geqslant 0\\\lambda (x^TAx-1)=0\end{cases}$

将 $\mathrm{KKT}$ 方程组的第一式展开，得到如下方程组。

$\begin{cases} b_1+\lambda(2a_{11}x_1+2a_{12}x_2+\cdots+2a_{1n}x_n)=0\\ b_2+\lambda(2a_{21}x_1+2a_{22}x_2+\cdots+2a_{2n}x_n)=0\\\quad\quad\quad\quad\quad\quad\quad\quad\quad\vdots\\b_n+\lambda(2a_{n1}x_1+2a_{n2}x_2+\cdots+2a_{nn}x_n)=0\end{cases}$

将上述方程组写成矩阵形式，有 $b+2\lambda Ax=0$ 。即 $\lambda x=-\frac{1}{2}A^{-1}b\ (1)$ ，等式两边取转置，得 $\lambda x^T=-\frac{1}{2}b^TA^{-1}\ (2)$ ； $(2)\times A\times(1)$ ，得 $\lambda^2x^TAx=\frac{1}{4}b^TA^{-1}b$ 。代入约束条件，移项后有 $x^TAx\leqslant 1$ ， $\lambda^2\geqslant\frac{1}{4}b^TA^{-1}b$ ；由于 $A^{-1}$ 为正定矩阵，故 $\lambda\geqslant\frac{1}{2}\sqrt{b^TA^{-1}b}>0$ ；所以约束条件是有效的，即 $x^TAx=1\ (3)$ 。根据式 $(1),(2)$ ，可得到最优解为 $x=-\frac{1}{2\lambda}A^{-1}b,x^T=-\frac{1}{2\lambda}b^TA^{-1}$ ；将其带入式 $(3)$ ，有 $\frac{1}{4\lambda^2}b^TA^{-1}b=1\ (\ast)$ 。
由于 $\sum\limits_{i=1}^nb_ix_i=b^Tx$ ，代入最优解 $x=-\frac{1}{2\lambda}A^{-1}b$ ，得 $\sum\limits_{i=1}^nb_ix_i$ 的最大值为 $-\frac{1}{2\lambda}b^TA^{-1}b$ 。于是， $\left(\sum\limits_{i=1}^nb_ix_i\right)^2$ 最大值为 $\frac{1}{4\lambda^2}\left(b^TA^{-1}b\right)^2$ ；将式 $(\ast)$ 代入，有 $\frac{1}{4\lambda^2}\left(b^TA^{-1}b\right)^2=b^TA^{-1}b$ 。
综上所述，最终答案为 $b^TA^{-1}b\bmod 998244353$ 。套用矩阵求逆模板和矩阵乘法公式即可。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第一场） Problem D
Date: 7/22/2020 
Description: 
	Use lagrange multiplier method
	Compute the inverse matrix 
*******************************************************************/
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=202;
const ll mod=998244353;
ll a[N][N<<1],b[N],c[N];
int n;
void inverse();
ll qpow_mod(ll a,int b);
int main()
{
	while(~scanf("%d",&n))
	{
		int i,j,k;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				scanf("%lld",&a[i][j]);
				a[i][n+j]=0;//初始化
				a[i][j]%=mod;
			}
		}
		for(i=1;i<=n;i++)
		{
			scanf("%lld",b+i);
			b[i]%=mod;
		}
		inverse();
		//=========================================
		//a[1][1+n]*b[1]+a[2][1+n]*b[2]...
		//a[2][1+n]*b[1]+a[2][1+n]*b[2]...
		//...
		for(j=1;j<=n;j++)
		{
			ll res=0;
			for(i=1;i<=n;i++)
			{
				res+=a[i][j+n]*b[i];
				res%=mod;
			}
			c[j]=res%mod;
		}
		//c存b的转置由乘A的结果
		//==========================================
		//计算c右乘B
		ll ans=0;
		for(i=1;i<=n;i++) 
		{
			ans+=b[i]*c[i];
			ans%=mod;
		}
		//==========================================
		printf("%lld\n",ans);
	}
	return 0;
}
void inverse()//矩阵求逆模板
{
	int m=n+n;
	int i,j,k;
	for(i=1;i<=n;i++) a[i][i+n]=1;
	for(i=1;i<=n;i++)
	{
		for(j=i;j<=n;j++)
		{
			if(a[j][i])
			{
				for(k=1;k<=m;k++)
				{
					swap(a[i][k],a[j][k]);
				}
			}
		}
		ll r=qpow_mod(a[i][i],mod-2);
		for(j=i;j<=m;j++) a[i][j]=r*a[i][j]%mod;
		for(j=1;j<=n;j++)
		{
			if(i==j) continue;
			ll rate=a[j][i]*a[i][i]%mod;
			for(k=i;k<=m;k++) 
			{
				a[j][k]=a[j][k]-rate*a[i][k]%mod;
				a[j][k]=(a[j][k]%mod+mod)%mod;
			}
		}
	}
}
ll qpow_mod(ll a,int b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

F. Infinite String Comparision $\looparrowright$

题目描述

For a string $x$ , Bobo defines $x^\infty = x x x \cdots 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^\infty$ and $b^\infty$ 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 \leqslant |a|, |b| \leqslant 10^5$ . $a, b$ consists of lower case letters. The total length of input strings does not exceed $2 \times 10^6$ .
输出描述:
For each test case, print = (without quotes) if $a^\infty = b^\infty$ . Otherwise, print < if $a^\infty < b^\infty$ , or > if $a^\infty > b^\infty$ .

示例1

输入

aa  
b  
zzz  
zz  
aba  
abaa

输出

1
2
3

<  
=  
>

分析

有些串直接循环比较即可，如 abc 和 abca；而类似 abc 和 abca 这样的字符串，需要重复几次变为 abcabc 和 abcaabca 才能看出端倪。不妨将 $a,b$ 都重复四次，再直接进行循环比较，即可得到结果。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第一场） Problem F
Date: 8/10/2020 
Description: Just Use IQ
*******************************************************************/
#include<string>
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	string a,b;
	while(cin>>a>>b)
	{
		int i;
		//重复四次
		a=a+a+a+a;
		b=b+b+b+b;
		//-1 <
		//0 =
		//1 >
		short flag=0;
		//循环比较
		if(a.size()>b.size())
		{
			for(i=0;i<a.size();i++)
			{
				if(a[i]<b[i%b.size()]) 
				{
					flag=-1;
					break;
				}
				else if(a[i]>b[i%b.size()]) 
				{
					flag=1;
					break;
				}
			}
		}
		else 
		{
			for(i=0;i<b.size();i++)
			{
				if(a[i%a.size()]<b[i])
				{
					flag=-1;
					break;
				} 
				else if(a[i%a.size()]>b[i]) 
				{
					flag=1;
					break;
				}
			}
		}
		switch (flag)
		{
		case -1:
			putchar('<');
			break;
		case 0:
			putchar('=');
			break;
		case 1:
			putchar('>');
			break;
		default:
			break;
		}
		putchar('\n');
	}
	return 0;
}

H. Minimum-cost Flow $\looparrowright$

题目描述

Bobo has a network of $n$ nodes and $m$ arcs. The $i$ -th arc goes from the $a_i$ -th node to the $b_i$ -th node, with cost $c_i$ .
Bobo also asks $q$ questions. The $i$ -th question is specified by two integers $u_i$ and $v_i$ , 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 $\frac{u_i}{v_i}$ (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 $a_i, b_i$ and $c_i$ . The next line contains an integer $q$ . The $i$ -th of the last $q$ lines contains two integers $u_i$ and $v_i$ .
$2 \leqslant n \leqslant 50$ , $1 \leqslant m \leqslant 100$ , $1 \leqslant a_i, b_i \leqslant n$ , $1 \leqslant c_i \leqslant 10^5$ .
$1 \leqslant q \leqslant 10^5$ , $0 \leqslant u_i \leqslant v_i \leqslant 10^9$ , $v_i > 0$ .
The sum of $m$ does not exceed $10^4$ . The sum of $q$ does not exceed $10^6$ .

输出描述

For each test case, print $q$ fractions (or NaN, if it is impossible to send one unit of flow) which denote the answer.

示例1

输入

输出

2/1
3/2
4/3
NaN

分析

运行 $q$ 次最小费用流算法显然是不现实的，应当考虑的是：运行一次最小费用流，进行一些预处理，使得每次询问时能够在较短时间内给出答案。
题中有一重要信息：每条边的容量都相同。设这个容量为 $cap$ 。利用 $\text{MCMF}$ 算法求最小费用最大流，会不断用 $\text{SPFA}$ 算法寻找单位费用和最小的增广路；由于每条边的容量都为 $cap$ ，故每条边只会存在满流或零流的情况，每次增广获得的最大流改进量恒为 $cap$ 。若源点流量为 $flow$ 且 $flow$ 不超过最大流，就是最小费用流模型。对于这样特殊的（每条边容量都为 $cap$ ）最小费用流模型，仍然可以利用 $\text{MCMF}$ 算法，每次增广后相当于将流量 $flow$ 减少 $cap$ ，产生的费用是增广路单位费用和与 $cap$ 的乘积；而最后一次增广时费用的改进量为剩余流量 $flow\bmod cap$ 与增广路单位费用和的乘积。进行多轮增广，直至剩余流量为零，就能得到最小费用流。
由于每条边的费用 $c_i$ 是不变的，因此不论 $cap$ 如何变化，只要源点流量不超过当前网络的最大流，对 $q$ 次询问中的每一张网络进行 $\text{MCMF}$ 算法，找到的增广路都是相同的，且每条增广路的顺序也保持不变。因此，只需要进行一次最小费用流的计算，记录下每一条增广路的单位费用即可，根据 $\text{MCMF}$ 算法原理，这些增广路是按照单位费用和由小到大获得的，排序操作是多余的。
不妨令每条边的容量为 $1$ ，求一次最小费用最大流，记录下每一条增广路的单位费用。对于每一次询问，源点流量为 $1$ ，每条边容量为 $\frac{u}{v}$ 。为了减少计算的误差，可以将所有数量扩大 $v$ 倍，即网络中源点流量为 $v$ ，每条边容量为 $u$ 。若源点流量 $v$ 不超过网络最大流，那么求固定流量 $v$ 的最小费用流得过程中，增广路为最小费用最大流得增广路子集，且每一轮 $\text{SPFA}$ 获得的增广路一定是当前所有存在的增广路中费用最小的。每一轮增广，源点流量就减少 $u$ ，相应的费用为该增广路的单位费用与 $u$ 的乘积；最后一次增广，源点流量减少 $u\bmod v$ ，对应费用也要相应改变；最终，源点流量为 $0$ ，求得最小费用流 $\mathrm{ans}$ 。 $\frac{\mathrm{ans}}{v}$ 即为一次询问的答案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第一场） Problem H
Date: 7/24/2020 
Description: Minimum-cost Flow
*******************************************************************/
#include<cstring>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const int N=104;
const int M=203;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m;//n个点，m条边
int tot;
int head[N];
struct E
{
	int to;
	int Next;
	ll cap;//容量
	ll cost;//费用
}edge[M<<2];
vector<ll>span;//增广路单位费用
int pre[N];//记录增广路前驱
ll incf[N];//增广路上剩余最小容量
ll dis[N];//将费用看作边权求最短路
bool vis[N];//记录访问
int s,t;//源点 汇点
ll maxflow,mincost;//最小费用最大流
inline void init();//初始化
inline void add_edge(int,int,int,int);
bool SPFA();//找增广路
void update();//更新最长增广路容量
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		init();
		while(m--)
		{
			int u,v,c;
			scanf("%d%d%d",&u,&v,&c);
			add_edge(u,v,1,c);
			add_edge(v,u,0,-c);
		}
		while(SPFA())
		{
			update();
			//记录每一条增广路的单位费用
			span.push_back(dis[t]);
		}
		int q;
		scanf("%d",&q);
		while(q--)
		{
			ll u,v;
			scanf("%lld%lld",&u,&v);
			//流量v 容量u
			if(maxflow*u<v) puts("NaN");//流量大于最大流
			else
			{
				ll flow=v,cap=u;
				ll ans=0;
				//按照费用由小到大的顺序访问所有增广路
				for(auto cost:span)
				{
					if(flow>=u)
					{
						flow-=u;
						ans+=u*cost;
					}
					else 
					{
						ans+=flow*cost;
						break;
					}
				}
				//输出最简分式
				ll g=__gcd(ans,v);
				printf("%lld/%lld\n",ans/g,v/g);
			}
		}
	}
	return 0;
}
inline void init()
{
	s=1;
	t=n;
	memset(head,-1,sizeof(head));
	tot=1;
	span.clear();
	memset(pre,0,sizeof(pre));
	maxflow=mincost=0;
}
inline void add_edge(int u,int v,int cap,int cost)
{
	tot++;
	edge[tot].to=v;
	edge[tot].cap=cap;
	edge[tot].cost=cost;
	edge[tot].Next=head[u];
	head[u]=tot;
}
bool SPFA()
{
	queue<int>q;
	memset(dis,inf,sizeof(dis));
	memset(vis,0,sizeof(vis));
	q.push(s);
	dis[s]=0;
	vis[s]=1;
	incf[s]=inf;
	while(!q.empty())
	{
		int x=q.front();
		vis[x]=0;
		q.pop();
		for(register int i=head[x];~i;i=edge[i].Next)
		{
			if(!edge[i].cap) continue;//剩余容量为0，不在残量网络中
			int y=edge[i].to;
			if(dis[y]>dis[x]+edge[i].cost)
			{
				dis[y]=dis[x]+edge[i].cost;//松弛操作
				incf[y]=min(incf[x],edge[i].cap);//最小剩余容量
				pre[y]=i;//记录前驱
				if(!vis[y])
				{
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
	if(dis[t]==inf) return 0;//汇点不可达，已经求出最大流
	else return 1;
}
void update()
{
	int x=t;
	//沿着前驱倒着走增广路
	while(x!=s)
	{
		int y=pre[x];
		edge[y].cap-=incf[t];
		edge[y^1].cap+=incf[t];
		x=edge[y^1].to;
	}
	maxflow+=incf[t];
	mincost+=dis[t]*incf[t];
}

I. 1 or 2 $\looparrowright$

题目描述

Bobo has a graph with $n$ vertices and m edges where the $i$ -th edge is between the vertices $a_i$ and $b_i$ . Find out whether is possible for him to choose some of the edges such that the $i$ -th vertex is incident with exactly $d_i$ 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 $d_1, d_2, \cdots, d_n$ .
The $i$ -th of the following $m$ lines contains two integers $a_i$ and $b_i$ .
$1 \leqslant n \leqslant 50$ , $1 \leqslant m \leqslant 100$ , $1 \leqslant d_i \leqslant 2$ , $1 \leqslant a_i, b_i \leqslant n$ . $a_i \neq b_i$ , $\{a_i, b_i\} \neq \{a_j, b_j\}$ for $i\neq 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

Yes
No
Yes

分析

首先考虑最简单的情况。如果 $\forall\ i\in\mathbb N^\ast$ 且 $1\leqslant i\leqslant n$ ，有 $d_i=1$ ，那么此题可以转化为一般图最大匹配问题，若最大匹配为完备匹配，则存在满足条件的方案。
进一步考虑当 $d_i=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'$ 就连了不止一条匹配边，这种情况在最大匹配中是不会出现的，因此将边化点的操作是成功的。
建图完成后，若一般图最大匹配为完备匹配，则存在满足条件的方案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第一场） Problem I
Date: 8/11/2020 
Description: Perfect Matching In General Graph
*******************************************************************/
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=1003;
struct E
{
	int to;
	int Next=-1;
}edge[N*100];
int n,m;
int father[N];
int head[N],tot;
int color[N],pre[N],match[N],dfn[N];
int timer;
queue<int>q;
int d[N];
int cnt;
inline void init();
inline void add_edge(int,int);
int father_of(int);
int lca_of(int,int);
void blossom(int,int,int);
bool bfs(int);
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		init();
		int i;
		cnt=n+2*m;
		for(i=1;i<=n;i++) 
		{
			scanf("%d",&d[i]);
			cnt+=d[i]==2;//度为2要拆点
		}
		for(i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			if(d[a]==2)
			{
				add_edge(a,n*2+i);//a e
				add_edge(a+n,n*2+i);//a' e
				add_edge(2*n+i,a);//e a
				add_edge(2*n+i,a+n);//e a'
			}
			else 
			{
				add_edge(a,2*n+i);
				add_edge(2*n+i,a);
			}
			if(d[b]==2)
			{
				add_edge(b,n*2+m+i);//b e'
				add_edge(b+n,n*2+m+i);//b' e'
				add_edge(2*n+m+i,b);//e' b
				add_edge(2*n+m+i,b+n);//e' b'
			}
			else 
			{
				add_edge(b,2*n+m+i);
				add_edge(2*n+m+i,b);
			}
			//e e'
			add_edge(2*n+i,2*n+m+i);
			add_edge(2*n+m+i,2*n+i);
		}
		int ans=0;
		for(i=1;i<=2*(n+m);i++)
		{
			if(!match[i])
			{
				ans+=bfs(i);
			}
		}
		//完备匹配为总点数的二分之一
		puts(ans==cnt>>1?"Yes":"No");
	}
	return 0;
}
inline void init()
{
	tot=0;
	timer=0;
	memset(head,-1,sizeof(head));
	memset(match,0,sizeof(match));
	memset(dfn,0,sizeof(dfn));
}
inline void add_edge(int u,int v)
{
	tot++;
	edge[tot].to=v;
	edge[tot].Next=head[u];
	head[u]=tot;
}
//=============================================
//一般图匹配模板
int father_of(int x)
{
	if(father[x]==x) return x;
	else return father[x]=father_of(father[x]);
}
int lca_of(int x,int y)
{
	timer++;
	x=father_of(x);
	y=father_of(y);
	for(;;x^=y^=x^=y)
	{
		if(x)
		{
			if(dfn[x]==timer) return x;
			dfn[x]=timer;
			x=father_of(pre[match[x]]);
		}
	}
}
void blossom(int x,int y,int lca)
{
	while(father_of(x)!=lca)
	{
		pre[x]=y;
		if(color[match[x]]==1)
		{
			color[match[x]]=0;
			q.push(match[x]);
		}
		if(father[x]==x) father[x]=lca;
		if(father[match[x]]==match[x]) father[match[x]]=lca;
		y=match[x];
		x=pre[y];
	}
}
bool bfs(int x)
{
	int i;
	for(i=1;i<=2*(n+m);i++) father[i]=i;
	memset(color,-1,sizeof(color));
	memset(pre,0,sizeof(pre));
	while(!q.empty()) q.pop();
	color[x]=0;
	q.push(x);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(i=head[u];~i;i=edge[i].Next)
		{
			int v=edge[i].to;
			if(color[v]==-1)
			{
				pre[v]=u;
				color[v]=1;
				if(!match[v])
				{
					for(register int go=1;go;v=go,u=pre[go])
					{
						go=match[u];
						match[u]=v; 
						match[v]=u;
					}
					return 1;
				}
				color[match[v]]=0;
				q.push(match[v]);
			}
			else if(!color[v]&&father_of(u)!=father_of(v))
			{
				int lca=lca_of(u,v);
				blossom(u,v,lca);
				blossom(v,u,lca);
			}
		}
	}
	return 0;
}

后记

多组输入，注意初始化。

J. Easy Integration $\looparrowright$

题目描述

Given $n$ , find the value of $\int_0^1 (x - x^2)^n \mathrm d x$ .
It can be proved that the value is a rational number $\frac{p}{q}$ .
Print the result as $p \cdot q^{-1} \bmod 998244353$ .

输入描述

The input consists of several test cases and is terminated by end-of-file.
Each test case contains an integer $n$ .
$1 \leqslant n \leqslant 10^6$ . The number of test cases does not exceed $10^5$ .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

1
2
3

1
2
3

输出

1
2
3

166374059
432572553
591816295

备注

For $n = 1$ , $\int_{0}^1 (x - x^2) \mathrm{d} x = \frac{x^2}{2} - \frac{x^3}{3} |_0^1 = \frac{1}{6}$ .

分析

令 $I=\int_0^1 (x - x^2)^n \mathrm d x=\int_0^1x^n(1-x)^n\mathrm dx$ ，利用分部积分法求解。

$ \begin{aligned}I&=\int_0^1x^n(1-x)^x\mathrm dx\\&=\frac{n}{n+1}\int_0^1x^{n+1}(1-x)^{n-1}\mathrm dx\\&=\frac{n(n-1)}{(n+2)(n+1)}\int_0^1x^{n+2}(1-x)^{n-2}\mathrm dx\\&\quad\quad\quad\quad\quad\quad\quad\quad\quad\vdots\\&=\frac{n(n-1)(n-2)\cdots}{(2n+1)(2n)\cdots(n+1)}\\&=\frac{(n!)^2}{(2n+1)!} \end{aligned} $

预处理阶乘后，只需要计算逆元即可得到答案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第一场） Problem J
Date: 8/10/2020 
Description: Integration
*******************************************************************/
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1000004;
const ll mod=998244353;
ll fac[N<<1];
int n;
void init();
ll qpow_mod(ll,ll);
int main()
{
	init();
	while(~scanf("%d",&n)) 
	{
		ll up=fac[n]*fac[n]%mod;//分子
		ll down=qpow_mod(fac[2*n+1],mod-2);//分母
		printf("%lld\n",up*down%mod);
	}
	return 0;
}
void init()//预处理
{
	fac[0]=1;
	const int SIZE=1000000*2+1;
	for(register int i=1;i<=SIZE;i++) 
	{
		fac[i]=fac[i-1]*(ll)i;
		fac[i]%=mod;
	}
}
ll qpow_mod(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1; 
	}
	return res;
}

D. Quadratic Form ↬\looparrowright↬

题目描述

输入描述

输出描述

示例1

输入

输出

分析

代码

F. Infinite String Comparision ↬\looparrowright↬

题目描述

输入描述

示例1

输入

输出

分析

代码

H. Minimum-cost Flow ↬\looparrowright↬

题目描述

输入描述

输出描述

示例1

输入

输出

分析

代码

I. 1 or 2 ↬\looparrowright↬

题目描述

输入描述

输出描述

示例1

输入

输出

分析

代码

后记

J. Easy Integration ↬\looparrowright↬

题目描述

输入描述

输出描述

示例1

输入

输出

备注

分析

代码

D. Quadratic Form $\looparrowright$

F. Infinite String Comparision $\looparrowright$

H. Minimum-cost Flow $\looparrowright$

I. 1 or 2 $\looparrowright$

J. Easy Integration $\looparrowright$