「LibreOJ β Round #7」匹配字符串

                           「LibreOJ β Round #7」匹配字符串

                                                 时间限制: 2 Sec  内存限制: 512 MB

题目描述

          对于一个 01 串（即由字符 0 和 1 组成的字符串）sss，我们称 sss 合法，当且仅当串 sss 的

          任意一个长度为 mmm 的子串 s′s's′，不为全 1 串。

          请求出所有长度为 nnn 的 01 串中，有多少合法的串，答案对 655376553765537 取模。

输入格式

输入共一行，包含两个正整数 n,mn,mn,m。

输出格式

输出共一行，表示所求的和对 655376553765537 取模的结果。

样例

样例输入 1

5 2

样例输出 1

13

样例解释 1

以下是所有合法的串：

00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101

样例输入 2

2018 7

样例输出 2

27940

数据范围与提示

对于所有的数据，满足 1≤n,m≤687215739041\le n,m\le 687215739041≤n,m≤68721573904。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

题目链接：http://118.24.30.237/problem.php?id=2991   

                   https://loj.ac/problem/547

AC 代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      typedef long long  ll;
     
    
   

    

     

    
    

     

      #define mod 65537
     
    
   

    

     

    
    

     

      ll m,n;
     
    
   

    

     

    
    

     

      ll f[6005],g[6005],tp[6005];
     
    
   

    

     

    
    

     

      void mul(ll *a,ll *b)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	for(int i=0;i<=2*m;i++) tp[i]=0;
     
    
   

    

     

    
    

     
	for(int i=0;i<m;i++)
     
    
   

    

     

    
    

     
    for(int j=0;j<m;j++)
     
    
   

    

     

    
    

     

      	 tp[i+j]=(tp[i+j]+a[i]*b[j])%mod;
     
    
   

    

     

    
    

     
	for(int i=2*m-2;i>=m;i--)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		for(int j=0;j<m;j++)
     
    
   

    

     

    
    

     

      			tp[i-m+j]=(tp[i-m+j]+tp[i])%mod;
     
    
   

    

     

    
    

     

      		tp[i]=0;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for(int i=0;i<m;i++) a[i]=tp[i];
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void ksm1()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	while(n)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if(n&1)mul(g,f);
     
    
   

    

     

    
    

     
		mul(f,f);
     
    
   

    

     

    
    

     

      		n>>=1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void f1()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	f[1]=1; g[0]=1;
     
    
   

    

     

    
    

     
	ksm1();
     
    
   

    

     

    
    

     

      	ll s=1,ans=0;
     
    
   

    

     

    
    

     
	for(int i=0;i<m;i++) ans=(ans+s*g[i])%mod,s=s*2%mod;
     
    
   

    

     

    
    

     
	printf("%lld\n",(ans%mod+mod)%mod);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      ll fac[65538],inv[65538];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      ll C(ll n,ll m)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if(m>n) return 0;
     
    
   

    

     

    
    

     
	if(n>=mod) return C(n/mod,m/mod)*C(n%mod,m%mod)%mod;
     
    
   

    

     

    
    

     
	else return fac[n]*inv[m]*inv[n-m]%mod;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      ll ksm2(ll x,ll k)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	ll s=1;
     
    
   

    

     

    
    

     
	while(k)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if(k&1) s=s*x%mod;
     
    
   

    

     

    
    

     

      		x=x*x%mod;
     
    
   

    

     

    
    

     

      		k>>=1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return s;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      ll calc(ll n1)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	ll ans=0,pw2=ksm2(2,n1),iv=ksm2(ksm2(2,m+1),mod-2);
     
    
   

    

     

    
    

     
	int lim=n1/(m+1);
     
    
   

    

     

    
    

     
	for(int i=0;i<=lim;++i)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if(i&1) ans-=pw2*C(n1-i*m,i);
     
    
   

    

     

    
    

     
		else ans+=pw2*C(n1-i*m,i);
     
    
   

    

     

    
    

     

      		pw2=pw2*iv%mod;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return (ans%mod+mod)%mod;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void f2()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	fac[0]=inv[0]=1;
     
    
   

    

     

    
    

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

    

     

    
    

     

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

    

     

    
    

     
	for(int i=mod-2;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
     
    
   

    

     

    
    

     
	printf("%lld\n",(calc(n+1)-calc(n)+mod)%mod);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	scanf("%lld%lld",&n,&m);
     
    
   

    

     

    
    

     
	if(m<=3000) f1();
     
    
   

    

     

    
    

     
	else f2();
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/83016489