文章目录

1989 竞赛表格

// 知识点1，rev函数进行反转
// 知识点2，分析反转之后的数字结构，
// 例如 

/* a + rev(a) = 2*a ab+ ba = 11*(a+b) abc + cba = 101*(a+c)+20*d abcd + dcba = 1001(a+d)+110*(b+c) // abcde + edcba = 10001(a+e)+1010*(b+d)+200*c; // abcdef + fedcba = 100001*(a+f)+10010*(b+e)+1100*(c+d); 可以通过dfs枚举 (a+f) ,(b+e),(c+d)的值 */
// 知识点3，预处理系数
// 知识点4，dfs处理满足条件的数
// 知识点5，公式转化
/* f[i]为i在表格中的出现次数 g[i]为j+rev(j)=i的j个数，那么 f[i]=1+∑j+rev(j) 所以 f[i]−1=∑(j+rev(j)=i)(f[j]−1)+g[i] 知识点6，离散化 */

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MX = 1e10;
typedef pair<LL,LL> P;
const int maxn = 1e7;
LL co[20];// 系数
P p[maxn]; int p1;
LL A[maxn],S[maxn];int p2;
// dfs 用来求所有符合要求的数，其中需要传递的参数是第几位，当前的值，种数,总共有多少位
void dfs(int x,LL v,LL count,int len){
	if(v > MX) return ;
	if(x > (len+1)/2){
		p[p1++] = P(v,count);
		return ;
	}
	int nn = 18;
	bool t = x == (len+1)/2 && (len & 1);
	if(t) nn = 9;
	for(int i = 0;i <= nn; ++i){
		int cnt = 1;
		if(!t)
			cnt = min(i,9)-max(i-9,(int)(x==1))+1;
		if(cnt <= 0) continue;
		dfs(x+1,v+i*co[x],cnt*count,len);
	}
}

LL rev(LL x){
	LL a = 0;
	while(x)
		a = a*10+x%10,x /= 10;
	return a;
}

int main(void){
	// freopen("input.txt","r",stdin);
	LL t = 1;
	int len = 10;
	for(int i = 1;i <= len; ++i){
		LL a = 1,b = t;
		for(int j = 1;j <= (i+1)/2; ++j){
			co[j] = a+b; 
			a *= 10;
			b /= 10;
		}
		// cout<<i<<" "<<p1<<endl;
		dfs(1,0,1,i);
		t *= 10;
	} 
	sort(p,p+p1);
	// cout<<p1<<endl;
	// for(int i = 0;i < 10; ++i)
	// cout<<p[i].first<<" "<<p[i].second<<endl;
	// cout<<endl;
	for(int i = 0,j;i < p1; ++i){
		LL t = i;
		for(j = i+1;j < p1; ++j){
			if(p[j].first == p[i].first) 
				p[i].second += p[j].second,t = j;
			else
				break;
		}
		// cout<<p[i].first<<endl;
		A[p2] = p[i].first;
		S[p2++] = p[i].second;
		i = t;
	}
	// cout<<p2<<endl;
	// for(int i = 0;i < 10; ++i) cout<<S[i]<<" ";
 // cout<<endl;
	for(int i = 0;i < p2; ++i){
		LL r = A[i]+rev(A[i]);
		if(r > MX) continue;
		// auto t = lower_bound(A,A+p2,r);
		// cout<<A[i]<<" "<<r<<" "<<*t<<endl;
		// cout<<" "<<*(--t)<<endl;
		S[lower_bound(A,A+p2,r)-A]  += S[i];
		// cout<<A[lower_bound(A,A+p2,r)-A]<<endl;
	}

  	for(int i = 1;i <  p2; ++i) S[i] += S[i-1];

  	int Q; cin>>Q;
  	LL L,R,P;
  	LL ans = 0;
  	while(Q--){
  		scanf("%lld%lld%lld",&L,&R,&P);
  		LL tmp = (S[upper_bound(A,A+p2,R)-A-1] - S[lower_bound(A,A+p2,L)-A-1]+R-L+1);
  		// cout<<tmp<<endl;
  		tmp %= P;
  		ans ^= tmp;
  	}
  	cout<<ans<<endl;

	return 0;
}