4
12
2016
0

[BZOJ4421] [Cerc2015] Digit Division

首先,如果一个串可以被分割成两个串且这两个串均满足条件,那么这个串一定满足条件。

证明:$a=0(mod$ $m)$,$b=0(mod$ $m)$则$a*x+b*y=0(mod$ $m)$(显然)

那么我们只要统计有多少种满足情况的子串就可以了,设数目为$k$,然后方案数就是$2^k$

注意如果最后原串不满足条件就要输出0(显然原串不满足那么拆成的子串中至少有一个不满足该性质)

说了这么多,其实特别好写。。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,ans=0,len;
const int Mod=1e9+7;

int main(){
freopen("4421.in","r",stdin);
freopen("4421.out","w",stdout);
scanf("%d %d",&n,&m);
char ch;
while((ch=getchar())<'0' || ch>'9');
if((ch-'0')%m==0)ans=1;
len=ch-'0';
while((ch=getchar())>='0' && ch<='9'){
	len=(len*10+ch-'0')%m;
	if(len==0){
		if(ans==0)ans=1;
		else ans=ans*2%Mod;
	}
}
printf("%d\n",len==0?ans:0);
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 403

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com