F题 Infinite String Comparision
本场的签到题
题意：给两个字符串 \(a\) 和 \(b\)。\(a\) 和 \(b\) 重复无穷遍构成字符串 \(a^\infty\) 和 \(b^\infty\)，判断 \(a^\infty\) 和 \(b^\infty\)的字母序大小。
思路：最开始想的是将 \(a\) 和 \(b\) 补充到它们长度的最小公倍数或者用模作为下标进行比较，由于数据范围 \(a\)、\(b\) 长度在 \(10^5\)，这种做法会tle。
之后的想法是将长的那个字符串延长一倍，然后短的字符串补到和长的一样长，再做比较。
赛后看到更简洁的做法，\(p=a+b\)，\(q=b+a\)，直接比较 \(p\) 和 \(q\) 大小。
题解：
Compare the string \(a^\infty\) and \(b^\infty\) directly
By the Periodicity Lemma, if there is no mismatches in the first \(a + b - gcd(a, b)\) characters, the two string are identical
Periodicity Lemma
假设一个字符串 \(S\) 有循环节 \(p\) 和 \(q\) 并且满足 \(p + q \leqslant |S| + gcd(p, q)\) ，那么 \(gcd(p, q)\) 也是一个循环节。
定理的证明：https://zhuanlan.zhihu.com/p/85169630
\(a\) 和 \(b\) 分别为 \(a^\infty\) 和 \(b^\infty\) 的循环节，如果 \(a^\infty\) 和 \(b^\infty\) 相等，设 \(S=a^\infty=b^\infty\)，则 \(a\)，\(b\) 为 \(S\) 的循环节。
\(|S|=\infty\)，所以 \(a + b \leqslant |S| + gcd(a, b)\) 成立，\(gcd(a, b)\) 也是一个循环节，\(a^\infty\) 和 \(b^\infty\) 中前 \(a + b - gcd(a, b)\) 个字母是相等的。（个人理解为减去了a，b中重复的一个循环节）
则只需要比较前 $$a + b - gcd(a, b)$$ 个字母，就可以判断两字符串是否相等。
代码如下(直接比较a+b和b+a的做法)：
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
int main(){
string a, b;
while(cin>>a>>b){
string p = a + b;
string q = b + a;
if(p > q) cout<<">"<<endl;
else if(p < q) cout<<"<"<<endl;
else cout<<"="<<endl;
}
return 0;
}
(比较前\(a + b - gcd(a, b)\)个字母的做法)
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
char a[N], b[N];
int gcd(int a, int b){
return b==0?a:gcd(b, a%b);
}
int main(){
while(scanf("%s %s", a, b) == 2){
int la = strlen(a);
int lb = strlen(b);
int l = la + lb - gcd(la, lb);
int flag = 0;
for(int i = 1; i <= l; i ++ ){
if(a[i%la] > b[i%lb]){
flag = 1;
break;
}
else if(a[i%la] < b[i%lb]){
flag = -1;
break;
}
}
if(flag == 0) printf("=\n");
else if(flag == 1) printf(">\n");
else printf("<\n");
}
return 0;
}
J题 Easy Integration
题意：计算\(\int_0^1(x-x^2)^ndx\)的值，这个值可以被表示为\(\frac{p}{q}\)，输出结果\((p·q^-1)mod998244353\)。
思路：用微积分计算出上面式子的值，或者直接找规律。
题解：
The value is (n!)^2 / (2n+1)!
Detailed proof can be found in “Wallis' integrals”.
\[\int_0^1(x-x^2)^ndx\\ =\int_0^1x^n(1-x)^ndx\\ =\frac{x^n+1}{n+1}(1-x)^n|_0^1-\int_0^1\frac{x^n+1}{n+1}(-n)(1-x)^n-1\quad dx\\ =\frac{n}{n+1}\int_0^1x^{n+1}(1-x)^{n-1}dx\\ =\frac{n}{n+1}\{[\frac{x^{n+2}}{n+2}(1-x)^{n-1}]_0^1-\int_0^1\frac{x^{n+2}}{n+2}(-n+1)(1-x)^{n-2}dx\}\\ =\frac{n(n-1)}{(n+1)(n+2)}\int_0^1x^{n+2}(1-x)^{n-2}dx\\ =\frac{n(n-1)···1}{(n+1)(n+2)···2n}\int_0^1x^{2n}dx\\ =\frac{n(n-1)···1}{(n+1)(n+2)···2n}\\ =\frac{(n!)^2}{(2n+1)!} \]
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 998244353;
const int N = 2e6 + 10;
const int M = 2e6;
LL fac[N], inv[N];
LL pow_mod(LL a, LL b, LL p){
LL ret = 1;
while(b){
if(b & 1) ret = (ret * a) % p;
a = (a * a) % p;
b >>= 1;
}
return ret;
}
void init(){
fac[0] = 1;
for(int i = 1; i <= M; i ++ )
fac[i] = fac[i-1] * i % mod;
inv[M] = pow_mod(fac[M], mod-2, mod);
for(int i = M-1; i > 0; i --)
inv[i] = inv[i+1] * (i+1) % mod;
}
int main(){
init();
int n;
while(scanf("%d", &n) != EOF){
printf("%lld\n", fac[n] * fac[n] % mod * inv[2*n+1] % mod);
}
return 0;
}
I题正在补，图论苦手……补完再更