【解题报告】 洛谷P1641 生成字符串

题目链接

https://www.luogu.com.cn/problem/P1641

思路

我们可以想象一个平面直角坐标系，或者一个格子图

我们设左下角为 (0,0)(0,0) 然后我们向右走是选一个1，向左走选一个0，于是我们最终要走到 (n,m)(n,m) 这个位置

并且我们只能在 (0,0),(n,m)(0,0),(n,m) 的连线下方走

这样我们就可以用小学就学过的格点标记法来做了

然后我们发现，有一些不合法的方案，然后我们设答案为 f(n,m)f(n,m) ，则有
f(n,m)=n−m+1n+1Cm+nm f(n,m)=\dfrac {n-m+1} {n+1} C_{m+n}^m
然后这里的 n,mn,m 比较大，所以我们预处理一下，然后利用逆元来求组合数，这是一个小技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int long long
using namespace std;
const int mod=20100403;
int n,m,ans,divi;
void mul(int &base,int x)
{
	base=(base*x)%mod;
}
int ksm(int a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1)
		res=1ll*res%p*a%p;
		a=1ll*a%p*a%p;
		b>>=1;
	}
	return res;
}
signed main()
{
	cin>>n>>m;
	divi=n+1,ans=divi-m;
	for(int i=n+1;i<=n+m;i++)
	mul(ans,i);
	for(int i=1;i<=m;i++)
	mul(divi,i);
	ans=(ans*ksm(divi,mod-2,mod))%mod;
	cout<<ans<<'\n';
	return 0;
}