1856: [Scoi2010]字符串
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1118 Solved: 598
[Submit][Status][Discuss]
Description
lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？
Input
输入数据是一行，包括2个数字n和m
Output
输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数
Sample Input
2 2
Sample Output
2
HINT
【数据范围】
对于30%的数据，保证1<=m<=n<=1000
对于100%的数据，保证1<=m<=n<=1000000
这是道好题啊。
我们先转化一下模型，我们先建一个平面直角坐标系，原点为（0,0），若当前位置选1，就横坐标加一，纵坐标加一，否则横坐标加一，纵坐标减一。由题意，目标点为（n+m，n-m），且不能到y=0以下的部分。所以，我们只要总方案数减去经过y=-1的方案数，易知总方案数为C（n+m，n）。
现在我们来讨论经过y=-1的方案数。
我们将第一次与y=-1的点的左边部分关于y=-1对称，最后方案数就等价于从（0，-2）走到（n+m，n-m）的方案数，我们设向上走了x步，向下走了y步，方案数即为（x+y，x),又x+y=n+m,x-y=n-m+2，解得x=n+1，y=m-1。
是不是感觉这方法很精妙啊，我也这么觉得啊。
代码：
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,m,ans,mod=20100403;
ll ksm(ll x,ll y)
{
ll ans=1;
while (y)
{
if (y&1) ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
ll calc(ll x,ll y)
{
ll sum1=1,sum2=1,sum3=1;
for (ll i=1;i<=x;i++)
sum1=sum1*i%mod;
for (ll i=1;i<=y;i++)
sum2=sum2*i%mod;
for (ll i=1;i<=x-y;i++)
sum3=sum3*i%mod;
sum1=sum1*ksm(sum2,mod-2)%mod;
sum1=sum1*ksm(sum3,mod-2)%mod;
return sum1;
}
int main()
{
scanf("%lld%lld",&n,&m);
ans=(calc(n+m,n)-calc(n+m,n+1)+mod)%mod;
printf("%lld\n",ans);
}
评论 (0)
