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;
}