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

比赛链接

收获

• $n=50$ 的数据量考虑一下网络流

F Infinite String Comparision

有一个 $\textbf{Periodicity Lemma}$：如果一个字符串 $S$ 有长度为 $p$ 的循环节和长度为 $q$ 的循环节，并且 $p+q\leq\left|S\right|+\gcd(p,q)$，那么 $\gcd(p,q)$ 也是 $S$ 的一个循环节。

因此，我们只需要判断 $i<\left|a\right|+\left|b\right|-\gcd(\left|a\right|,\left|b\right|)$ 时是否有 $a_i=b_i$。

关于 $\textbf{Periodicity Lemma}$ 的一些资料：link1 link2 link3

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); }

char a[N], b[N];

int main(){
	while(scanf("%s%s", a, b) != EOF){
		int lena = strlen(a), lenb = strlen(b);
		int mark = -1;
		for(int i = 0; i < lena + lenb - gcd(lena, lenb); i++){
			if(a[i % lena] != b[i % lenb]){
				mark = i; break;
			}
		}
		if(mark == -1)	puts("=");
		else if(a[mark % lena] < b[mark % lenb])	puts("<");
		else	puts(">");
	}
	return 0;
}

接下来是一个及其优美的做法：

不妨设 $\left|a\right|\leq\left|b\right|$，那么 $a[1…lena]$ 和 $b[1…lena]$ 不等答案显然；现在 $a[1…lena]=b[1…lena]$，接下来需要比较 $b[lena+1]$ 和 $a[1]$，但由于 $a[1…lena]=b[1…lena]$，相当于比较 $b[lena+1]$ 和 $b[1]$，同理往后推，可以得到一个非常简洁的结论：直接比较 $a+b$ 和 $b+a$ 即可。

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int main(){
	string a, b;
	while(cin >> a >> b){
		string A = a + b, B = b + a;
		if(A < B)	puts("<");
		else if(A == B)	puts("=");
		else	puts(">");
	}
	return 0;
}

---

J Easy Integration

直接分部积分一波：

$$\begin{align}\int_0^1\left(x-x^2\right)^n\mathrm dx&=\int_0^1x^n(1-x)^n\mathrm dx=\int_0^1(1-x)^n\mathrm d\frac{x^{n+1}}{n+1}\\&=\frac{1}{n+1}\left[(1-x)^nx^{n+1}\bigg|_0^1+n\int_0^1x^{n+1}(1-x)^{n-1}\mathrm dx\right]&&分部积分\\&=\frac{n}{n+1}\int_0^1x^{n+1}(1-x)^{n-1}\mathrm dx\\&=\cdots&&不断实施分部积分\\&=\frac{(n!)^2}{(2n+1)!}\end{align}$$

另外，上式其实是 $\mathbf{Beta}$ 函数的特例：

$$\text{B}(p,q)=\int_0^1x^{p-1}(1-x)^{q-1}\mathrm dx$$

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const LL MOD = 998244353;

inline LL fpow(LL bs, LL idx){
	LL res = 1;
	bs %= MOD;
	while(idx){
		if(idx & 1)	(res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}

int n;
LL fact[2000005], invfact[2000005];

int main(){
	fact[0] = 1;
	for(int i = 1; i <= 2000000; i++){
		fact[i] = fact[i-1] * i % MOD;
		invfact[i] = fpow(fact[i], MOD - 2);
	}
	while(scanf("%d", &n) != EOF)
		printf("%lld\n", fact[n] * fact[n] % MOD * invfact[2*n+1] % MOD);
	return 0;
}