luogu P1641 [SCOI2010]生成字符串

代码极短

$O(n^2)$dp是设$f_{i,j,k}$表示前$i$位,放了$j$个1,后面还可以接着放$k$个0的方案,转移的话,如果放0,$k$就要减1,反之放了1,后面可以多放一个0,所以$k$加1,即$$f_{i+1,j,k-1}+=f_{i,j,k}$$$$f_{i+1,j+1,k+1}+=f_{i,j,k}$$

这样子还是不好优化,,,

我们可以把问题抽象化,把这个放字符过程转化为从平面直角坐标系的$(0,0)$走到$(n,m)$,其中放1相当于横坐标+1,放0相当于纵坐标+1,因为要求任何一个前缀中1个数大于等于0个数,也就是走的过程中不能经过$(x,x+1)$,也就是不能碰到直线$y=x+1$.这是个经典问题,答案为$\binom{n+m}{m}-\binom{n+m}{m-1}$.至于为什么,这里有一道类似的题

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define db double

#define eps (1e-5)

using namespace std;

const int N=1000000+10,mod=20100403;

il LL rd()

{

    re LL x=0,w=1;re char ch;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

LL n,m,jc[N<<1];

il LL ksm(LL a,LL b)

{

  LL an=1;

  while(b)

    {

      if(b&1) an=(an*a)%mod;

      a=(a*a)%mod;

      b>>=1;

    }

  return an;

}

int main()

{

  n=rd(),m=rd();

  jc[0]=1;

  for(int i=1;i<=n+m;i++) jc[i]=(jc[i-1]*i)%mod;

  printf("%lld\n",((jc[n+m]*ksm(jc[n],mod-2)%mod*ksm(jc[m],mod-2)%mod-jc[n+m]*ksm(jc[n+1],mod-2)%mod*ksm(jc[m-1],mod-2)%mod)%mod+mod)%mod);

  return 0;

}

巴特西

luogu P1641 [SCOI2010]生成字符串

最新文章

热门文章