51nod1989 竞赛表格

1989 竞赛表格

定义rev(i)为i十进制下各位翻转所得的数,例如rev(2345)=5432,rev(3210)=123。
l0nl1f3比较无聊,他打算用rev函数进行一个游戏。
他找了一个无穷大的表格,设第i行第j列的格子上的数为f(i,j),那么ff满足

f(x,y)=\left\{\begin{matrix} x& & y=1 \\ f(x,y-1)+rev(f(x,y-1))& &y>1 \end{matrix}\right.

l0nl1f3想要知道这个表格中[L,R]之间的数出现了多少次,mod P输出。
由于他有时候会改变主意,所以他可能会询问q次,每次的L、R、P可能不同。

1\leq q\leq10^{5},1\leq L\leq R\leq 10^{10},1\leq P\leq10^{9}
由于输入较慢,建议使用输入优化,这里提供一份C++的输入优化(标程就使用这个输入优化): 

char ch,B[1<<20],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
ll aa;ll F(){ //positive only.
    while(ch=getc(),!isd(ch));aa=ch-'0';
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';
	return aa;
}

由于输出较慢,你只需要将每个询问的答案异或后输出。

样例解释:

第一个询问,数字表格前13行、前4列如下:

   1    2    4      8
   2    4    8    16
   3    6   12   33
   4    8   16   77
   5  10   11   22
   6  12   33   66
   7  14   55  110
   8  16   77  154
   9  18   99  198
 10  11   22    44
 11  22   44    88
 12  33   66  132
 13  44   88  176

可以发现其中有9个10~13的数,9 mod 7=2,所以该询问答案为2。

四个询问的答案分别为:2 159 147 1825,2 xor 159 xor 147 xor 1825=1839,所以输出1839。

输入

第一行一个整数q,表示询问次数。( 1≤q≤10^5)
第二行开始q行每行三个整数L、R、P。(1≤L≤R≤10^10,1≤P≤10^9)

输出

一行一个整数,为每个询问的答案的异或和。

输入样例

4
10 13 7
2333 233333 233
6666 666666 666
1234 567890 2333

输出样例

1839

解析:

例如一个数x=abcde,rev(x)为edcba,那么x+rev(x)=10001(a+e)+1010(b+d)+200c。
那么可以发现a+e、b+d都是[0,18]的一个整数,c是[0,9]的整数。
那么我们可以考虑枚举x的位数和a+e、b+d、c这样的数,dfs一波,进而求出x+rev(x)可能取到的每个数,同时计算取到每个x+rev(x)的x的个数,全部记下来sort就好。
这样的复杂度大约是19^(len/2)*len的,可以求出250w左右个可能的数,记这个集合为S。
记f[i]为i在表格中的出现次数,g[i]为j+rev(j)=i的j个数,那么  f_{i}=1+\sum_{j+rev(j)=i}f_{j},所以 f_{i}-1=\sum_{j+rev(j)=i}(f_{j}-1)+g_{i}
显然只有g[i]>0的数f[i]才大于1,那么我们只要从小到大枚举S中的每个数p,每次让 f_{p}=f_{p}+g_{p}+1f_{rev(p)+p}=f_{rev(p)+p}+fp-1 即可。
求出S集合中所有f值之后只要前缀和一下,每次询问求和一下,再加上不在集合S中的数的个数即可。

放代码:

#include
#define ll long long
using namespace std;
char ch,B[1<<20],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
ll aa;ll F(){ 
    while(ch=getc(),!isd(ch));aa=ch-'0';
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';
	return aa;
}
ll psb[3200000],sb[3200000],pw[20],psum[3200000],sum[3200000];
int c[3200000];
void dfs(int now,int lim,ll had,ll ways){
	if(had > pw[10]) return;
	if(now == (lim+1)/2){
		psb[++psb[0]] = had , c[psb[0]] = psb[0] , psum[psb[0]] = ways;
		return;
	}
	if(!now){
		if(pw[now] == pw[lim-now-1]){
			for(int i=1;i<=9;i++)
				dfs(now+1,lim,had+2*i*pw[now],ways);
		}
		else{
			for(int i=1;i<=18;i++)
				dfs(now+1,lim,had+i*(pw[now]+pw[lim-1-now]),ways*(i<=9?i:9-(i-10)));
		}
	}
	else{
		if(pw[now] == pw[lim-now-1]){
			for(int i=0;i<=9;i++)
				dfs(now+1,lim,had+2*i*pw[now],ways);
		}
		else{
			for(int i=0;i<=18;i++)
				dfs(now+1,lim,had+i*(pw[now]+pw[lim-1-now]),ways*(i<=9?i+1:9-(i-10)));
		}
	}
}
ll rev(ll x){
	ll ret=0;
	for(;x;) ret=ret*10+x%10,x/=10;
	return ret;
}
bool cmp(const int &u,const int &v){ return psb[u] < psb[v]; }
int main(){
	pw[0] = 1;
	for(int i=1;i<=10;i++) pw[i] = pw[i-1] * 10;
	for(int i=1;i<=10;i++) dfs(0,i,0,1);
	sort(c+1,c+1+psb[0],cmp);
	for(int i=1;i<=psb[0]+1;i++)
		if(psb[c[i]] == psb[c[i-1]])
			psum[c[i]] += psum[c[i-1]];
		else if(i>1)
			sb[++sb[0]] = psb[c[i-1]] , sum[sb[0]] = psum[c[i-1]];
	for(int i=1;i<=sb[0];i++){
		sum[lower_bound(sb+1,sb+1+sb[0],sb[i]+rev(sb[i]))-sb] += sum[i];
		sum[i] += sum[i-1];
	}
	int q=F(),ans=0;
	ll l,r,p;
	for(;q--;){
		l=F(),r=F(),p=F();
		int ret = (sum[upper_bound(sb+1,sb+1+sb[0],r)-sb-1] - sum[upper_bound(sb+1,sb+1+sb[0],l-1)-sb-1] + r - l + 1) % p;
		ans ^= ret;
	}
	printf("%d\n",ans);
    return 0;
}

你可能感兴趣的