本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-29 21:35:17

按照二元组意义下的模等价类分类。

考虑如何定义二元组下的模。考虑到模实际是减去若干次某一个数字，那么二元组下两个元素减去数字的次数也肯定要相同。若二元组是 $(x,y)$ ，模数是 $(a,b)$ ，那么结果可以为 $(x\bmod a,y-\lfloor\frac{x}{a}\rfloor b)$ 。

分完类就一眼了。

实现时需要注意正负号。

无论是 $x,y,a,b$ 都可以为负。

实现的很唐。

code

const int N=2e5+5;

char s[N];

pir p[N];

map<pir,bool>apr;

map<int,set<int> >mp[N<<1];

int k[N];

int c,d;
bool same(pir aa,pir bb){
	return (aa.fi%c+c)%c==(bb.fi%c+c)%c&&aa.se-floor(aa.fi*1.0\/c)*d==bb.se-floor(bb.fi*1.0\/c)*d;
}
bool cmp(pir aa,pir bb){
	if((aa.fi%c+c)%c==(bb.fi%c+c)%c&&aa.se-floor(aa.fi*1.0\/c)*d==bb.se-floor(bb.fi*1.0\/c)*d){
		return aa.fi<bb.fi;
	}
	if((aa.fi%c+c)%c==(bb.fi%c+c)%c)
		return aa.se-floor(aa.fi*1.0\/c)*d<bb.se-floor(bb.fi*1.0\/c)*d;
	return (aa.fi%c+c)%c<(bb.fi%c+c)%c;
}

signed main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	int T=read();
	c=0,d=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='L')
			c--;
		if(s[i]=='R')
			c++;
		if(s[i]=='U')
			d++;
		if(s[i]=='D')
			d--;
	}
	
	{
		if(c<0){
			for(int i=1;i<=n;i++){
				if(s[i]=='L')
					s[i]='R';
				else if(s[i]=='R')
					s[i]='L';
			}
		}
		if(d<0){
			for(int i=1;i<=n;i++){
				if(s[i]=='U')
					s[i]='D';
				else if(s[i]=='D')
					s[i]='U';
			}
		}
	}
	
	c=0,d=0;
	apr[{0,0}]=1;
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='L')
			c--;
		if(s[i]=='R')
			c++;
		if(s[i]=='U')
			d++;
		if(s[i]=='D')
			d--;
		if(apr[{c,d}])
			continue;
		p[++cnt]={c,d};
		apr[{c,d}]=1;
	}
	n=cnt;
	if(c==0){
		for(int i=1;i<=n;i++)swap(p[i].fi,p[i].se);
		swap(c,d);
	}
	if(T==1||(c==0&&d==0)){
		print(n+1),pc('\n');
		return 0;
	}
	p[++n]={0,0};
	sort(p+1,p+1+n,cmp);
	int ans=T;
	for(int i=2;i<=n;i++){
		if(same(p[i-1],p[i]))
			ans+=min(T,(p[i].fi-p[i-1].fi)\/c);
		else
			ans+=T;
	}print(ans),pc('\n');
	return 0;
}