牛客多校Day_1

2020-07-14

这里是牛客多校Day1的补题

赛场回顾

一共就过了FJ两题……丢人.jpg

F

题意

题目大意是给出两个字符串$A$和$B$，都可以进行无限循环拓展成$AAA…$和$BBB…$，求他们字典序大小比较。

做法

一开始猜想是最坏情况到$lcm(a,b)$这一位才会出现不同（$a = |A|$,$b = |B|$），但是这个想法是错的，根据 Periodicity Lemma 也就是周期引理，若在第一个$a+b-gcd(a,b)$中所有字母都相同，那么这两个字符串相同。

这样就直接暴力了

代码

void solve(){
    string ss,tt;

    while(cin>>ss>>tt){

    string s,t;
    int len = ss.length()+tt.length()-__gcd(ss.length(),tt.length());
    while(s.length()<=len)  s+=ss;
    while(t.length()<=len)  t+=tt;
    s=s.substr(0,len);
    t=t.substr(0,len);
    if(s<t)         puts("<");
    else if(s>t)    puts(">");
    else            puts("=");

    }

    return ;
}

J

题意

对于给定的$n$,要求出 $ \int_{0}^{1} (x-x^2) \; dx \; \% \; 998244353$

做法

这题的做法嘛，说出来有点丢人。当时手推这个公式找规律发现是

$\begin{matrix} \sum_{i=0}^{n} \frac{(-1)^i \,C_{n}^{i}}{n+i+1} \end{matrix}$

这里要学一波反演

然后就没有然后了，默默算几项然后oeis找终极公式

$\frac{(n!)^2}{(2n+1)!}$

然后就是简单的阶乘打表，求逆元。

对于数学好的人可以分部积分得出以下过程(我推不动)

究极公式有了，就简单了

代码

ll frac[2*N+5]={0};

void  init(){
    frac[0]=1;
    for(ll i=1;i<=2*N;i++)
        frac[i]=(frac[i-1]*i)%mod;
    return ;
}

ll inv(ll x){//求x在%mod意义下的逆元
    ll times=mod-2,ans=1;
    while(times){
        if(times&1)ans=ans*x%mod;
        x=x*x%mod; times>>=1;
    }
    return ans;
}

ll qpow(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 solve(){
    init();
    ll n;
    while(cin>>n){
        cout<<qpow(frac[n],2)*inv(frac[2*n+1])%mod<<endl;
    }
    return ;
}

从现在开始这里叫做辰寿补题广场

不行叉姐的题目太难了补不动补不动溜了