牛客多校训练第三场F sum of digits(数学+线段树区间合并)

https://www.nowcoder.com/acm/contest/141/F

题意：

现在有一个这样的函数：



我们可以发现这个递归函数是这样的

$$SOD(\sum_{i=1}^{k}(x_i*16^i))= SOD(\sum_{i=1}^{k}{x_i*16^i\%15})=SOD(\sum_{i=1}^{k}{x_i*1^i})$$

也就是说这个函数其实就是

$$SOD(x)=(x\%15==0?15:(x\%15))$$

在知道函数是这么简单情况下枚举子序列，可以用线段树区间合并没枚举区间内所有情况的0-15出现了多少次。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;
#define ls rt<<1
#define rs rt<<1|1
long long f[20];
char sss[maxn];
struct Tree
{
	long long num[16];
	void init()
	{
		memset(num,0,sizeof(num));
	}
	Tree operator+(const Tree&A)const
	{
		Tree ans;
		ans.init();
		for(int i=0;i<16;i++)
		{
			ans.num[i]=(ans.num[i]+num[i]+A.num[i])%mod;
		 	for(int j=0;j<16;j++)
		 	{
		 		int cnt=i+j;
		 		if(cnt>15) cnt-=15;
		 		ans.num[cnt]=(ans.num[cnt]+A.num[i]*num[j]%mod)%mod; 
			 }
		 } 
		return ans;
	}
}tree[maxn<<2];
int getNum(char x)
{
	if(x>='0'&&x<='9') return x-'0';
	return x-'A'+10;
}
void pushup(int rt)
{
	tree[rt]=tree[ls]+tree[rs];
}
void build(int l,int r,int L,int R,int rt)
{
	tree[rt].init();
	if(l==r)
	{
		int temp = getNum(sss[l]);
//		cout<<rt<<" "<<temp<<endl;
		tree[rt].num[temp]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,L,R,ls);
	build(mid+1,r,L,R,rs);
	pushup(rt);
}
void update(int l,int C,int L,int R,int rt)
{
//	cout<<L<<" "<<R<<endl;
	if(L==R)
	{
		tree[rt].init();
		tree[rt].num[C]=1;
		return;
	}
	int mid=(L+R)>>1;
	if(l<=mid) update(l,C,L,mid,ls);
	else update(l,C,mid+1,R,rs);
	pushup(rt);
}
Tree query(int l,int r,int L,int R,int rt)
{
//	cout<<L<<" "<<R<<endl;
	if(l<=L&&R<=r) 
	{
//		cout<<"--------------"<<rt<<endl;
		return tree[rt];
	}
	int mid=(L+R)>>1;
	Tree ans;
	ans.init();
	if(l<=mid) ans=ans+query(l,r,L,mid,ls);
	if(r>mid) ans=ans+query(l,r,mid+1,R,rs);
	return ans; 
}
int main()
{
	int T,n,m,op,i,j,k;
	f[0]=1;
	for(int i=1;i<16;i++) 
		f[i]=(f[i-1]*1021)%mod;
	scanf("%d%d",&n,&m);
	scanf("%s",sss+1);
	build(1,n,1,n,1);
	long long ans=0;
	while(m--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			int l,d;
			char x;
			scanf("%d %c",&l,&x);
			d=getNum(x);
//			cout<<d<<endl;
			update(l,d,1,n,1);
//			cout<<"----------------"<<endl;
		}
		else
		{
			ans=0;
			int l,r;
			scanf("%d%d",&l,&r);
			Tree a=query(l,r,1,n,1);
			for(i=0;i<16;i++)
			{
				ans = (ans+f[i]*a.num[i]%mod)%mod;
//				cout<<ans<<endl;
			}
			printf("%lld\n",ans);
		}
	}
}

Q.E.D.