2023牛客国庆集训派对day1
F. Infinite String Comparision
解题思路:
\(n = a.size,m = b.size\)
短的字符串不断延长，直到覆盖两倍的长串。然后按两倍长串的长度一一比较即可。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
void solve()
{
string a,b;
while(cin>>a>>b)
{
string l,r;
l = a;
r = b;
int n = a.size();
int m = b.size();
if(n < m)
{
int cnt = (m + n - 1) / n + 1;
for(int i = 1;i<=cnt;i++)
{
a += l;
}
b += r;
}
else if(n > m)
{
int cnt = (n + m - 1) / m + 1;
for(int i = 1;i<=cnt;i++)
{
b += r;
}
a += l;
}
n = a.size();;
m = b.size();
n = min(n,m);
string ans;
for(int i = 0;i<n;i++)
{
if(a[i] != b[i])
{
if(a[i] < b[i])
{
ans += '<';
}
else
{
ans += '>';
}
break;
}
}
if(ans.empty())
{
puts("=");
}
else
{
cout<<ans<<endl;
}
}
}
int main()
{
int t = 1;
while(t--)
{
solve();
}
return 0;
}
J. Easy Integration
解题思路：
分部积分法:
\(u(x) = u,v(x) = v\)，二者都是关于\(x\)的函数，以下是对\(x\)求导。
\[\begin{align*} \tag{1} (uv)' = u'v + v'u\\ \end{align*} \]积分是求导的逆运算：
\[\begin{align*} \int(uv)' = uv\\ \end{align*} \]对公式\((1)\)两边同时积分:
\[\begin{align*} \int(uv)'dx = \int (u'v)dx + \int (v'u)dx \\ uv = \int (u'v)dx+ \int (v'u)dx \\ \int (v'u)dx = uv - \int(u'v)dx \end{align*} \]公式推导：
\[\begin{align*} \int_0^1(x - x^2)^ndx &= \int_0^1 x^n(1 - x)^ndx \\ &= \frac 1 {n + 1}\int_0^1 (1 - x)^nd(x^{n + 1})\\ &= \left. \frac 1 {n + 1}x^{n + 1}(1-x)^n \right|_0^1 - \frac{1}{n + 1}\int_0^1x^{n + 1}d(1-x)^n\\ &=0 + \frac{n}{n+1}\int_0^1x^{n +1}(1-x)^{n-1}dx \\ &=\frac{n}{n+1}\int_0^1x^{n +1}(1-x)^{n-1}dx \end{align*} \]即
\[\begin{align*} \int_0^1 x^n(1 - x)^ndx &= \frac{n}{n+1}\int_0^1x^{n +1}(1-x)^{n-1}dx \\ &=......\\ &=\frac{n!}{(n+1)...(2n + 1)}\int_0^1x^{2n + 1}(1-x)^0dx\\ &=\frac{n!}{(n+1)...(2n + 1)} \end{align*} \]\[ans = \frac{n!}{(n+1)...(2n + 1)} \mod 998244353 \]\(p和q\)都有了，接下来就是经典费马小定理求逆元了。
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi first
#define se second
const int N = 2e6 + 10;
const int mod = 998244353;
ll qmi(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()
{
vector<ll> f(N);
f[0] = 1;
for(int i = 1;i<=2e6;i++)
{
f[i] = (f[i-1] * i) % mod;
}
ll n;
while(~scanf("%lld",&n))
{
ll p = f[n];
ll q = (f[2 * n + 1] * qmi(f[n],mod-2)) % mod;
ll ans = (p * qmi(q,mod-2)) % mod;
printf("%lld\n",ans);
}
}
int main()
{
int t = 1;
while(t--)
{
solve();
}
return 0;
}