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("=
");
else if(flag == 1) printf(">
");
else printf("<
");
}
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”.
代码如下：
#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
", fac[n] * fac[n] % mod * inv[2*n+1] % mod);
}
return 0;
}
I题正在补，图论苦手……补完再更