CF 1045 H. Self-exploration 解题报告

CF 1045 H. Self-exploration

考虑到串的结构一定是

1...0....1....0.....1...

这样的，而\(01\)与\(10\)在转折点交替出现

首先串长一定是\(a+b+c+d+1\)（分别代表\(00,01,10,11\)的数量），且首位一定是\(1\)，还需要满足\(b=c\lor b=c-1\)，先不考虑限制计数一波

我们发现，实际上我们需要把所有\(0\)中选择若干个作为转折点，然后\(1\)也这样，剩下的直接按照转折填进去就可以了

注意到\(0\)和\(1\)的个数分别是\(a+c\)和\(b+d+1\)

然后转折点已经必须在第一位出现一次了，所以方案数是\(\binom{a+c-1}{c}\)与\(\binom{b+d}{b}\)，乘法原理就可以了

然后考虑限制，我们从最高位开始填充

如果当前位是\(0\)，就只能填\(0\)，继续向后填

如果当前为是\(1\)，填\(0\)以后后面可以随便填了，可以按没有限制的差不多的算，只是最高位钦定是\(0\)；填\(1\)就也是继续往后填

注意填的过程稍微注意一下边界判断，否则可能数组越界什么的

Code:

#include <cstdio>

#include <cctype>

#include <cstring>

#include <vector>

#include <algorithm>

const int SIZE=1<<21;

char ibuf[SIZE],*iS,*iT;

//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)

#define gc() getchar()

template <class T>

void read(T &x)

{

	int f=0;x=0;char c=gc();

	while(!isdigit(c)) f|=c=='-',c=gc();

	while(isdigit(c)) x=x*10+c-'0',c=gc();

	if(f) x=-x;

}

const int N=2e5+1;

const int mod=1e9+7;

char s[N],t[N];

int fac[N],inv[N];

inline void add(int &x,int y){x+=y;if(x>=mod) x-=mod;}

#define mul(a,b) (1ll*(a)*(b)%mod)

inline int qp(int d,int k)

{

	int f=1;

	while(k)

	{

		if(k&1) f=mul(f,d);

		d=mul(d,d);

		k>>=1;

	}

	return f;

}

int C(int m,int n)

{

    if(m==n) return 1;

    return mul(fac[m],mul(inv[m-n],inv[n]));

}

int cal(int c00,int c01,int c10,int c11,char *s)

{

	int n=strlen(s+1),l=c00+c01+c10+c11;

	if(c10!=c01&&c10!=c01+1) return 0;

	if(n>l+1) return mul(C(c00+c10-1,c10-1),C(c11+c01,c01));

	if(n<l+1) return 0;

	int pre=1,ret=0;

	for(int i=2;i<=n;i++)

	{

		if(s[i]=='0')

		{

			if(pre) --c10;

			else --c00;

			pre=0;

		}

		else

		{

			if(pre) --c10;

			else --c00;

			if(c01!=c10||c01!=c10+1) add(ret,mul(C(c00+c10,c10),C(c11+c01-1,c01-1)));

			if(pre) ++c10;

			else ++c00;

			if(pre) --c11;

			else --c01;

			pre=1;

		}

		if(c00<0||c01<0||c10<0||c11<0) break;

	}

	return ret;

}

int ck(int c00,int c01,int c10,int c11,char *s)

{

    int n=strlen(s+1),l=c00+c01+c10+c11;

    if(n!=l+1) return 0;

    int pre=s[1]-'0';

    for(int i=2;i<=n;i++)

    {

        if(pre)

        {

            if(s[i]=='1') --c11;

            else --c10;

        }

        else

        {

            if(s[i]=='1') --c01;

            else --c00;

        }

        pre=s[i]-'0';

    }

    return !c00&&!c01&&!c10&&!c11;

}

int main()

{

    //freopen("data.in","r",stdin);

    //freopen("data.out","w",stdout);

	scanf("%s%s",s+1,t+1);

	fac[0]=1;

	for(int i=1;i<N;i++) fac[i]=mul(fac[i-1],i);

	inv[N-1]=qp(fac[N-1],mod-2);

	for(int i=N-2;~i;i--) inv[i]=mul(inv[i+1],i+1);

	int c00,c01,c10,c11;

	read(c00),read(c01),read(c10),read(c11);

	int ans=((cal(c00,c01,c10,c11,t)-cal(c00,c01,c10,c11,s)+ck(c00,c01,c10,c11,t))%mod+mod)%mod;

	printf("%d\n",ans);

	return 0;

}

2019.6.2

巴特西

CF 1045 H. Self-exploration 解题报告

CF 1045 H. Self-exploration

最新文章

热门文章