首页 > 代码库 > BZOJ3326: [Scoi2013]数数
BZOJ3326: [Scoi2013]数数
SCOI的数位统计问题都好鬼畜……另外这题数据有误,可能l>r……
这题的预处理很简单,连DP都不用,然而统计的时候恶心死了……我的思路是计算每一位对所有区间的贡献,对于同一个右端点的所有区间其贡献是相同的,然后几个前缀和暴搞一下……
#include<cstdio> typedef long long ll; const int p=20130427; const int N=1e5+5; int n1,n2; ll s1,z1[N],z2[N],c1[N],c2[N],c3[N],c4[N]; ll cal(ll s){return(s-1)*s/2%p;} ll cal(int i,int j){ return((j+1)*c3[i]-c4[i]+p)%p; } int sol(ll*f,int n){ ll s2=0,s3=(c2[n]*cal(f[n])%p*c1[n]+cal(n-1,n)*cal(s1)%p*(f[n]-1)%p*c1[n-1])%p; for(int i=n-1;i;--i) s2=(s2+(n-i)*c2[i+1]%p*f[i+1])%p,s3=(s3+s2*f[i]%p*c1[i]+(n-i+1)*c2[i]%p*cal(f[i])%p*c1[i]+cal(i-1,n)*cal(s1)%p*f[i]%p*c1[i-1]+c2[i]*cal(s1)%p*c1[i]+cal(i-1,i)*cal(s1)%p*(s1-1)%p*c1[i-1])%p; return s3; } int main(){ scanf("%lld%d",&s1,&n1); for(int i=n1;i;--i) scanf("%lld",z1+i); scanf("%d",&n2); for(int i=n2;i;--i) scanf("%lld",z2+i); int n3=n1<n2?n2:n1; c1[1]=1; for(int i=2;i<=n3;++i) c1[i]=s1*c1[i-1]%p; for(int i=1;i<=n3;++i) c2[i]=(c2[i-1]+c1[i])%p,c3[i]=(c3[i-1]+c2[i])%p,c4[i]=(c4[i-1]+c2[i]*i)%p; ++z2[1]; printf("%d\n",(sol(z2,n2)-sol(z1,n1)+p)%p); }
BZOJ3326: [Scoi2013]数数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。