F Infinite String Comparision

题意

对于字符串x，定义 为字符串x重复无限次形成的字符串。
给定字符串a,b，比较 和 的字典序大小。

题解

重复无限次肯定是不行的，多举几个样例发现，将长一点的字符串重复一次，短的字符串去和它去比较，不够则重复，直到重复了一次的长的字符串比完，就能得出结果。这虽然能过，但不会证。
正确解法根据一个定理，只需要比较a,b字符串的前 len(a)+len(b)-gcd(len(a),len(b)) 就行。

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1e5 + 7;
typedef long long ll;
const double eps = 1e-6;
const double pi = acos(-1.0);

int main()
{
    string s1, s2;
    while (cin >> s1 >> s2) {
        int len1 = s1.size(), len2 = s2.size();
        if(len1 < len2) {
            string s3 = s2 + s2;
            bool f = true, f1 = false, f2 = false;
            for (int i = 0, j = 0; i < s3.size(); i++) {
                if(s1[j] != s3[i]) f = false;
                if(s1[j] > s3[i]) {
                    f1 = true;
                    break;
                }
                if(s1[j] < s3[i]) {
                    f2 = true;
                    break;
                }
                j++;
                if(j == len1) j = 0;
            }
            if(f) printf("=\n");
            else if(f1) printf(">\n");
            else printf("<\n");
        }
        else {
            string s3 = s1 + s1;
            bool f = true, f1 = false, f2 = false;
            for (int i = 0, j = 0; i < s3.size(); i++) {
                if(s2[j] != s3[i]) f = false;
                if(s2[j] > s3[i]) {
                    f1 = true;
                    break;
                }
                if(s2[j] < s3[i]) {
                    f2 = true;
                    break;
                }
                j++;
                if(j == len2) j = 0;
            }
            if(f) printf("=\n");
            else if(f1) printf("<\n");
            else printf(">\n");
        }
    }
}

J Easy Integration

题意

求 % 998244353 。

题解

数学推导题，用分步积分法求解。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 7, M = 998244353;
typedef long long ll;
ll fac[N] = {1, 1};
void init(){
    for(int i = 2; i < N ; i++){
        fac[i] = fac[i-1] * i % M;
    }
}
ll qmod(ll a, ll b){
    ll ans = 1;
    a = a%M;
    while (b){
        if(b&1 == 1)
            ans = ans*a%M;
        a = a*a%M;
        b >>= 1;
    }
    return ans;
}
ll inv(ll a){
    return qmod(a, M-2);
}
int main()
{
    ios::sync_with_stdio(false);
    ll n; init();
    while (cin >> n) {
        printf("%lld\n", fac[n]*fac[n]%M*inv(fac[2*n+1])%M);
    }
    return 0;
}