牛客多校第一场

F

定理：
两个字符串s，t，其循环节各自为p,q，如果p+q-gcd(p,q)相等，则之后就一直相等

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;

char s[maxn],t[maxn];
int len;
int solve(){
    int lens = strlen(s),lent = strlen(t);
    for(int i = 0;i<len;i++){
        if(s[i%lens] < t[i%lent]) return cout<<"<\n",0;
        if(s[i%lens] > t[i%lent]) return cout<<">\n",0;
    }
    return cout<<"=\n",0;
}
int main(){
    // debug;
    ios;

    while(cin>>s && cin>>t){
        len = max(strlen(s),strlen(t))*2;
        solve();
    }
    return 0;
}

J

手动推算前三项，找规律，列出式子。

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

ll jc[maxn],inv[maxn];
ll ksm(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res * a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}
void init(){
    jc[0] = 1;
    for(int i = 1;i<maxn;i++){
        jc[i] = jc[i-1] * i %mod;
        inv[i] = ksm(jc[i],mod-2);
    }
}
int main(){
    // debug;
    ios;

    init();
    int N;
    while(cin>>N){
        ll ans = jc[N] * jc[N] %mod * inv[2*N+1]%mod;
        cout<<ans<<'\n';
    }

    return 0;
}