T4
求最长不下降子序列，因为最大值为150，并且数据产生方式有循环；
所以可以找规律，在后面的时候，每经过一个循环节答案最大值+1；
恶心的事循环节前面和后面的处理，很难调；

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const int N=1e5+7;
LL n,tt,ans;
int t0,A,B,C,D,ff=0;
int vis[N],a[N],last[N];
LL f[N];
int main(){
	freopen("lis.in","r",stdin);
	freopen("lis.out","w",stdout);
	scanf("%lld",&n);
	scanf("%d%d%d%d%d",&t0,&A,&B,&C,&D);
	a[1]=t0;
	vis[a[1]]=1;
	last[a[1]]=1;
//	cout<<a[1]<<" ";
	for(int i=2;i<=n;i++){
		a[i]=1LL*(1LL*a[i-1]*a[i-1]*A+B*a[i-1]+C)%D;
		tt=i;
//		cout<<a[i]<<" ";
		if(vis[a[i]]){
			ff=1;
			break;
		}
		vis[a[i]]=1;
		last[a[i]]=i;
//		if(a[i]==9) cout<<"------"<<i<<" ";
	}
//	cout<<"\n";
//	cout<<tt<<"\n";
//	cout<<a[tt]<<"\n";
	LL l=last[a[tt]];
//	cout<<l<<"\n";
	if(ff==1) tt--;
	LL uu=tt-l+1;
//	cout<<uu<<"\n";
//	cout<<l<<" "<<"\n";
	LL ss=l-1+100*uu;
	for(int i=1;i<=min(ss,n);i++){
		if(i>tt) a[i]=1LL*(1LL*a[i-1]*a[i-1]*A+B*a[i-1]+C)%D;
		LL maxn=0;
		for(int j=1;j<i;j++){
			if(a[j]<=a[i]){
				maxn=max(maxn,f[j]);
			}
		}
		f[i]=maxn+1;
//		cout<<f[i]<<" ";
	}
	if(ff==0||ss>=n){
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++){
			if(i>tt) a[i]=1LL*(1LL*a[i-1]*a[i-1]*A+B*a[i-1]+C)%D;
			LL maxn=0;
			for(int j=1;j<i;j++){
				if(a[j]<=a[i]){
					maxn=max(maxn,f[j]);
				}
			}
			f[i]=maxn+1;
//			ans=max(ans,f[i]);
		}
		for(int i=1;i<=n;i++){
			ans=max(ans,f[i]);
		}
		cout<<ans;
		return 0;
	}
//	cout<<ss<<"\n";
	LL kk=n-ss;
//	cout<<kk<<"\n";
	LL oo=kk/uu;
	LL pp=0;
//	cout<<"--"<<oo<<"\n";
	if(oo!=0){
		oo--;
		pp=uu;
	}
//	cout<<(uu*99+l)<<"\n";
	for(int i=(uu*99+l);i<=ss;i++){
//		LL zz=(i-(l-1))/uu;
//		if((i-(l-1))%uu==0) zz--;
		f[i]+=oo;
//		cout<<f[i]<<" ";
	}
//	cout<<"\n";
//	cout<<f[1]<<"\n";
	LL yy=kk%uu;
//	cout<<yy<<"\n";
	pp+=yy;
//	cout<<pp<<"\n";
	for(int i=ss+1;i<=ss+pp;i++){
		if(i>ss) a[i]=1LL*(1LL*a[i-1]*a[i-1]*A+B*a[i-1]+C)%D;
		LL maxn=0;
		for(int j=1;j<i;j++){
			if(a[j]<=a[i]){
				maxn=max(maxn,f[j]);
			}
		}
		f[i]=maxn+1;
	}
	for(int i=1;i<=ss+pp;i++){
		ans=max(ans,f[i]);
	}
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0; 
}
/*
309
126 139 23 135 26

707
77 56 129 57 131

10
1 1 3 5 37

1991
128 128 73 113 75

532889960237
143 88 122 1 147

1329
30 104 50 130 136
*/

T2
给定一个数组，可以选两个数a,b;
把a和b合并起来，就是a在前，b在后产生的一个新数；
问有多少种选的方案，使得拼起来的数不是k的倍数；

虑求有多少对(i; j)满足拼数结果为k的倍数。可以发现，对x; y拼数
的本质是x*10⌊log10y⌋+1+y（这个式子不严谨，明白意思就行）。只要加号
左边的与加号右边的对k取余的数能够加起来得到k或0即可。考虑
枚举j，设j的位数为dig=⌊log10aj⌋+ 1，那么只要查询有多少个数满足乘10dig的结果对k取余为k

#include<iostream>
#include<cstdio>
#include<map>
#define LL long long
using namespace std;
const int N=2e5+7;
int n,maxn;
LL k,ans;
LL a[N];
map<int,int> S[11];
int get(int x){
	int res=0;
	while(x!=0){
		res++;
		x/=10;
	}
	return res;
}
int main(){
	freopen("piece.in","r",stdin);
	freopen("piece.out","w",stdout);
	scanf("%d%lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		maxn=max(maxn,get(a[i]));
	}
	for(int i=1;i<=n;i++){
		int tt=a[i];
		for(int j=1;j<=maxn;j++){
			tt=1LL*tt*10%k;
			S[j][tt]++;
		}
	}
	for(int i=1;i<=n;i++){
		int tt=a[i];
		int nod=get(a[i]);
		for(int j=1;j<=nod;j++) tt=1LL*tt*10%k;
		S[nod][tt]--;
		if(a[i]%k){
			ans+=S[nod][k-a[i]%k];
		}else{
			ans+=S[nod][0];
		}
		S[nod][tt]++;
	}
	cout<<1LL*n*(n-1)-ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
4 11
45 1 10 12
*/