F、Sum Of Digit

C++14(g++5.4) 解法, 执行用时: 2140ms, 内存消耗: 15400K, 提交时间: 2018-07-27 15:54:52

#include <bits/stdc++.h>
using namespace std;
const int N=100010,D=16;
const int P=1e9+7;
int p[16],M,T[N<<2][D],x,y,res[D],tmp[D],n,q,op,Ans;
char s[N],t[D];
inline int add(int a,int b){
	a+=b;
	return a>=P?a-P:a;
}
inline int sub(int a,int b){
	a-=b;
	return a<0?a+P:a;
}
inline int mul(long long a, int b){
	a*=b;
	return a>=P?a%P:a;
}
int A(char c){
    if(c>='0'&&c<='9')return c-'0';
    else return c-'A'+10;
}
void merge(int A[16],int B[16],int *C){
	for(int i=0;i<D;i++)C[i]=0;
	for(int i=0;i<D;i++){
		for(int j=0;j<D;j++){
			int u=(i+j)%(D-1);
			if((i+j)&&!u)u=D-1;
			C[u]=add(C[u],mul(A[i],B[j]));
		}
	}
}
int main(){
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    for(M=1;M<(n+2);M<<=1); 
    p[0]=1; for(int i=1;i<D;i++)p[i]=1LL*p[i-1]*1021%P;
    for(int i=1;i<=n;i++){T[i+M][A(s[i])]++;T[i+M][0]++;}
    for(int x=M;x;x--)merge(T[x<<1],T[x<<1|1],T[x]);
	while(q--){
        scanf("%d",&op);
        if(op==1){
            scanf("%d%s",&x,t);
            T[x+M][A(s[x])]--;
            T[x+M][A(t[0])]++;
            s[x]=t[0];
            for(x=(x+M)/2;x;x/=2)merge(T[x<<1],T[x<<1|1],T[x]);
        }else{
            scanf("%d%d",&x,&y);
            for(int i=0;i<D;i++)res[i]=0; res[0]=1;
            x+=M-1; y+=M+1;
            while(x^y^1>0){
                if(~x&1){
                	merge(res,T[x+1],tmp);
                	for(int i=0;i<D;i++)res[i]=tmp[i];
				} 
                if(y&1){
					merge(res,T[y-1],tmp);
					for(int i=0;i<D;i++)res[i]=tmp[i];
				}
                x>>=1;y>>=1; 
            }
            res[0]=sub(res[0],1);
            Ans=0;
            for(int i=0;i<D;i++)Ans=add(Ans,mul(res[i],p[i]));
            printf("%d\n",Ans);
        }
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3252ms, 内存消耗: 34008K, 提交时间: 2018-07-26 23:02:03

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=100003;
struct node{
	ll cnt[16];
	void init(){
		memset(cnt,0,sizeof(cnt));
	}
};
char s[maxn];
node rec[maxn<<2];
node a;
ll pw[16];
int n,q;
int getnum(char c){
	if(c>='0'&&c<='9')return c-'0';
	return c-'A'+10;
}
void Union(node& x,node a,node b){
	for(int i=0;i<16;i++){
		x.cnt[i]=(a.cnt[i]+b.cnt[i])%mod;
	}
	for(int i=0;i<16;i++){
		for(int j=0;j<16;j++){
			int k=(i+j)%15;
			if(k==0&&(i!=0||j!=0))k=15;
			x.cnt[k]=(x.cnt[k]+a.cnt[i]*b.cnt[j])%mod;
		}
	}
}
void pushup(int u){
	Union(rec[u],rec[u+u],rec[u+u+1]);
}
void build(int u,int l,int r){
	if(l==r){
		rec[u].init();
		rec[u].cnt[getnum(s[l])]=1;
		return;
	}

	int mid=(l+r)>>1;
	build(u+u,l,mid);
	build(u+u+1,mid+1,r);
	pushup(u);
}
void update(int u,int l,int r,int p,int x){
	if(p<l||p>r)return;
	if(l==r){
		rec[u].init();
		rec[u].cnt[x]=1;
		return;
	}
	int mid=(l+r)>>1;
	update(u+u,l,mid,p,x);
	update(u+u+1,mid+1,r,p,x);
	pushup(u);
}
void query(int u,int l,int r,int ql,int qr,node& a){
	if(qr<l||ql>r)return;
	if(ql<=l&&r<=qr){
		node c;
		Union(c,a,rec[u]);
		a=c;
		return;
	}
	int mid=(l+r)>>1;
	query(u+u,l,mid,ql,qr,a);
	query(u+u+1,mid+1,r,ql,qr,a);
}
int main(){
	pw[0]=1;
	for(int i=1;i<16;i++)pw[i]=pw[i-1]*1021%mod;
	scanf("%d%d",&n,&q);
	scanf("%s",s+1);
	build(1,1,n);
	for(int i=1;i<=q;i++){
		int typ;
		scanf("%d",&typ);
		if(typ==1){
			int p;
			char c[3];
			scanf("%d%s",&p,c);
			int x=getnum(c[0]);
			update(1,1,n,p,x);
		}
		else {
			int l,r;
			scanf("%d%d",&l,&r);
			a.init();
			query(1,1,n,l,r,a);
			ll ans=0;
			for(int i=0;i<16;i++)ans=(ans+a.cnt[i]*pw[i])%mod;
			printf("%lld\n",ans);
		}
	}
}

详情