CF1993 VP 记录

2024年09月19日 CF补全计划约6k字预计需要29分钟

CF1993.Codeforces Round 963 (Div. 2) solved(3/7)

A. Question Marks

题意

蒂姆正在做一个由 $4n$ 个问题组成的测试；每个问题有 $4$ 个选项：A"、“B”、"C "和 “D”。每个选项都有 $n$ 个正确答案，也就是说，有 $n$ 道题的答案是 “A”， $n$ 道题的答案是 “B”， $n$ 道题的答案是 “C”， $n$ 道题的答案是 “D”。

对于每道题，蒂姆都会把答案写在答题纸上。如果想不出答案，他会在该题上留下问号"？

他的答题纸有 $4n$ 个字符。蒂姆最多能答对多少题？

思路

签到题

统计每一个选项，每一个选项与 $n$ 取 min 最后加和即可。

代码最后统一给出。

B. Parity and Sum

题意

给定一个由 $n$ 个正整数组成的数组 $a$ 。

在一次操作中，你可以选取任意一对索引 $(i, j)$ ，使得 $a_i$ 和 $a_j$ 具有不同的奇偶性，然后用它们的和替换较小的那个。更正式的说法是

如果 $a_i \leq a_j$ ，则用 $a_i + a_j$ 替换 $a_i$ ；
否则，用 $a_i + a_j$ 替换 $a_j$ 。

求使数组中所有元素具有相同奇偶性所需的最少操作数。

思路

我们可以发现，当奇偶性不同的时候，加出来的数一定是奇数，所以我们就是需要将所有的偶数变成奇数。我们还可以发现，当一个奇数大于一个偶数地时候，删掉偶数所需的操作次数为1，如果小于偶数的时候操作次数为2。所以为了减少不必要的操作，我们如下进行合并：

最大的奇数大于最小的偶数时，操作次数 $+1$ ，然后删掉这个偶数并累加到最大的奇数中。可以发现这样可以尽可能地减少当前奇数小于偶数的情况。
当最大的奇数小于最小的偶数时，选出最大的偶数，将它与这个奇数合并，可以发现这个操作最多只会被做一次，因为做完后会发现当前的数会大于所有的偶数。

代码写的很乱，有能力还是自己写。

C. Light Switches

题意

公寓由 $n$ 个房间组成，每个房间的灯最初都是关着的。

为了控制这些房间的灯光，公寓的主人决定在房间里安装芯片，这样每个房间正好有一个芯片，芯片安装在不同的时间。具体来说，这些时间由数组 $a_1, a_2, \ldots, a_n$ 表示，其中 $a_i$ 是在 $i$ /th房间安装芯片的时间(以分钟为单位)。

芯片安装后，每隔 $k$ 分钟就会改变房间的灯光状态–在 $k$ 分钟内开灯，然后在接下来的 $k$ 分钟内关灯，再在接下来的 $k$ 分钟内开灯，以此类推。换句话说， $i$ /th房间的灯光状态在 $a_i$ 、 $a_i + k$ 、 $a_i + 2k$ 、 $a_i + 3k$ 、 $\ldots$ 分钟时由芯片改变。

公寓里所有房间最早亮灯的时刻是什么时候？

思路

~~这题看似很难，实则一点也不简单（指细节）~~

不难发现，每一个灯泡都是以 $2\times k$ 为一个周期的，所以我们可以先将所有输入的时间对 $2\times k$ 取模后再进行计算（注意在此时需要将取模前元素的最大值找出，方便统计）。

对于两个灯，如果它们两个存在某个时刻都亮了，那么它们的时间 $[a_i,a_i+k]$ 与 $[a_j,a_j+k]$ 必定有交集。同理，对于 $n$ 个时间点，如果它们存在一个时间都亮了，那么它们必定都在某个长度为 $k$ 的区间中,然而 $k$ 是很小的,所以可以从先前记录的最大值向后,判断所有点是否都在 $k$ 的区间中.

(~~这道题我赛时写的代码很烂,依旧是有能力的自己写~~)

D. Med-imize

题意

给定两个正整数 $n$ 和 $k$ 以及另一个由 $n$ 个整数组成的数组 $a$ 。

在一次操作中，可以选择 $a$ 的任意一个大小为 $k$ 的子数组，然后将其从数组中删除，而不改变其他元素的顺序。更正式地说，假设 $(l, r)$ 是对子数组 $a_l, a_{l+1}, \ldots, a_r$ 的操作，使得 $r-l+1=k$ ，那么执行此操作意味着用 $[a_1, \ldots, a_{l-1}, a_{r+1}, \ldots, a_n]$ 替换 $a$ 。

例如，如果 $a=[1,2,3,4,5]$ ，我们对这个数组执行 $(3,5)$ 操作，它就会变成 $a=[1,2]$ 。此外，操作 $(2, 4)$ 的结果是 $a=[1,5]$ ，操作 $(1,3)$ 的结果是 $a=[4,5]$ 。

当 $a$ 的长度大于 $k$ （即 $|a| \gt k$ ）时，你必须重复操作。处理后，数组 $a$ 中所有剩余元素的最大中值 $^\dagger$ 是多少？

$^\dagger$ 长度为 $n$ 的数组的中位数是按非递减顺序排序后索引为 $\left \lfloor (n+1)/2 \right \rfloor$ 的元素。例如 $median([2,1,5,4,3]) = 3$ 、 $median([5]) = 5$ 和 $median([6,8,2,4]) = 4$ 。

思路

看见中位数,就首想二分答案,二分答案行不通再考虑上数据结构.这道题就是因为一看到中位数就想数据结构就寄了(😓).

所以这题是二分答案.我们选择二分剩余元素的最大中值 $mid$ 每一次二分中都将每一个大于 $mid$ 的值设成 $1$ ,小于 $mid$ 的值设成 $-1$ ,这样的话,我们只需要判断最后删下来的数最大值是否大于 $0$ 即可.

extand

还有两个使用相同寄巧的题目:

P2824 HEOI2016/TJOI2016 排序

[AGC006D] Median Pyramid Hard

那么接下来难就难在如何求删掉剩下的数的最大值了.

考虑DP,但是在做DP之前,需要先知道一个 trick :

trick

对于一个序列,如果我们删去连续的一段,长度为 $k$ 那么剩余的序列下标在 $\pmod {k}$ 意义下还是连续的.

证明很简单 $[a_1,a_2\ldots a_{i-1},a_i\ldots a_{i+k-1},a_{i+k}\ldots a_n]$ 删去从 $i$ 开始的一段后成为 $[a_1,a_2\ldots a_{i-1},a_{i+k}\ldots a_n]$ 而 $i-1+1\equiv i+k \pmod k$ 所以tirck成立.

有了这个trick,我们会发现,最后剩下的数字下标会在 $1\ldots k$ 最多出现一次,且一定按顺序排列.于是我们就可以推出DP转移方程:

dp_i= \begin{cases} \max(dp_{i-k},a_i) & i\equiv 1\pmod k \\ \max(dp_{i-1}+a_i,dp_{i-k}) & \text{otherwise} \end{cases}

解释一下,当 $i\equiv 1\pmod k$ 时,一定为数列的第一项,所以有选择不选\选.

其余情况就是选当前点或删去.

E. Xor-Grid Problem

题意

给定一个大小为 $n \times m (n,m\leq 15)$ 的矩阵 $a$ ，其中每个单元格都包含一个非负整数。位于矩阵第 $i$ 行与第 $j$ 列交点上的整数称为 $a _{i,j}$ 。

让我们把 $f(i)$ 和 $g(j)$ 分别定义为第 $i$ 行和第 $j$ 列中所有整数的 XOR。在一次操作中，您可以

选择任意行 $i$ ，然后为每个 $1 \le j \le m$ 指定 $a_{i,j} := g(j)$ ；或
选择任意一列 $j$ ，然后为每个 $1 \le i \le n$ 赋值 $a_{i,j} := f(i)$ 。

对矩阵的第 $2$ 列进行操作的示例。

在本例中，当我们对列 $2$ 执行操作时，这一列中的所有元素都会发生变化：

$a_{1,2} := f(1) = a_{1,1} \oplus a_{1,2} \oplus a_{1,3} \oplus a_{1,4} = 1 \oplus 1 \oplus 1 \oplus 1 = 0$
$a_{2,2} := f(2) = a_{2,1} \oplus a_{2,2} \oplus a_{2,3} \oplus a_{2,4} = 2 \oplus 3 \oplus 5 \oplus 7 = 3$
$a_{3,2} := f(3) = a_{3,1} \oplus a_{3,2} \oplus a_{3,3} \oplus a_{3,4} = 2 \oplus 0 \oplus 3 \oplus 0 = 1$
$a_{4,2} := f(4) = a_{4,1} \oplus a_{4,2} \oplus a_{4,3} \oplus a_{4,4} = 10 \oplus 11 \oplus 12 \oplus 16 = 29$

这些运算可以多次进行。然后，我们将所有相邻单元格对的绝对差值相加，计算出最终矩阵的 $\textit{beauty}$ 值。

更正式地说，如果所有单元格 $(x, y)$ 和 $(r, c)$ 相邻，则 $\textit{beauty}(a) = \sum|a_{x,y} - a_{r,c}|$ for all cells $(x, y)$ 。如果两个单元格共用一条边，则视为相邻单元格。

求所有可得矩阵中最小的 $\textit{beauty}$ 。

思路

手玩样例可以发现,我们选择任意两行,做两次操作后就会发现他们两行互换了,并且整体的异或值不变,对于列同理.

于是我们就可以考虑将每行\列的异或值求出,并添加一个新的列\行来存储,这样就变成了一个 $(n+1)\times(m+1)$ 的矩阵，然后每一个操作就变为了交换矩阵中任意两行或列的元素.问题就变成了选择 $n$ 行 $m$ 列,求最小的 $\textit{beauty}$ .

extand

这种异或的寄巧还有一道题

[AGC016D] XOR Replace

注意到 $n,m\leq 15$ 考虑状压,不难发现,行和列是可以分开考虑的,行对值的贡献与列对值的贡献之和就是答案,因此我们可以分开考虑(常用寄巧).

extand

也有使用这种技巧的题目,大多与相邻的值有关,行和列不一定是同一种算法.

P2258 [NOIP2014 普及组] 子矩阵此题是将行 dfs 再将列 dp

CF1202C You Are Given a WASD-string… 此题是将行列分开考虑,然后分别DP\前缀和

我们设 $g_{i,j}$ 代表将第 $i$ 行接在第 $j$ 行后面的代价,显然这是可以 $O(n^3)$ 预处理的.

我们首先枚举我们不选的列 $nl$ 然后对行进行DP

设 $dp_{S,i}$ 代表已选择的状态 $S$ 和最后一次选择第 $i$ 行的答案,那么就不难推出转移:

dp_{S\cup\{j\},j}=\min \limits_{j\notin S}\{dp_{S,i}+g_{i,j}-\abs{a_{i,nl}-a_{j,nl}}\}

我们记 $ans_{i,nl}$ 为不选择第 $i$ 行不选第 $nl$ 列的答案,这个不难能得到.

对于列,枚举不选的行后同理即可.(只是注意 $ans$ 的下标即可)

F2. Dyn-scripted Robot (Hard Version)

题意

这是问题的困难版本。唯一不同的是，在这个版本中 $k \le 10^{12}$ 。只有两个版本的问题都解决了，你才能进行hack。

给定 $Oxy$ 平面上有一个 $w \times h$ 矩形，矩形的左下方有点 $(0, 0)$ ，右上方有点 $(w, h)$ 。

您还有一个最初位于点 $(0, 0)$ 的机器人和一个由 $n$ 个字符组成的脚本 $s$ 。每个字符都是 L、R、U 或 D，分别指示机器人向左、向右、向上或向下移动。

机器人只能在矩形内移动，否则将更改脚本 $s$ 如下：

如果试图向垂直边界外移动，它会将所有 L 字符改为 R 字符（反之亦然，将所有 R 字符改为 L 字符）。
如果尝试向水平边界外移动，则会将所有 U 字符更改为 D 字符（反之亦然，将所有 D 字符更改为 U 字符）。

然后，它会从无法执行的字符开始执行更改后的脚本。

机器人移动过程的示例， $s = \texttt{"ULULURD"}$ 。

脚本 $s$ 将被连续执行 $k$ 次。即使重复执行，字符串 $s$ 的所有变化都将被保留。在此过程中，机器人总共会移动到 $(0, 0)$ 点多少次？注意，初始位置不计算在内。

思路

先给一个提示:本题为数论题,算法是 ExCRT.

好,我们首先要知道这个反转是怎么做的.我们从一位的情况开始考虑,碰到边缘反弹其实就是将走出去的部分镜像.

所以我们可以把它当成反转当成镜像空间内行走,这样的话题目就变成了会经过多少次横纵坐标都为 $2w$ 和 $2h$ 倍数的点.

我们设重复完一次指令后的坐标位于 $(dx,dy)$ 那么我们实际上要求的就是对于当前指令的第 $i$ 位所在的点 $(sx,sy)$ 求解有多少个解满足:

\begin{cases} dx\times x+sx\equiv 0 \pmod{2w}\\ dy\times y+sy\equiv 0 \pmod{2h} \end{cases}

其中 $x\leq k$ .

可以发现,我们只需要求解出一个最小整数解后剩下的统计就是 $\lfloor \frac{k-x_0-1}{m}\rfloor$ 其中 $m$ 为模数.

我们将它改造成exgcd的标准模式,使用exgcd合并两个方程即可求出最小正整数解.

改造过程

\begin{aligned} &ax+by=c\\ \implies &ax_0+by_0=\gcd(a,b)\\ \iff & ax_0\frac{c}{\gcd(a,b)}+by_0\frac{c}{\gcd(a,b)}=c\\ \implies &\begin{cases}x=x_0\frac{c}{\gcd(a,b)}+k\frac{b}{gcd(a,b)}\\y=y_0\frac{c}{\gcd(a,b)}-k\frac{a}{gcd(a,b)}\end{cases}\\ \implies & x=x_0\frac{c}{gcd(a,b)} \pmod{\frac{b}{\gcd(a,b)}} \end{aligned}

下面给出通解的证明

\begin{aligned} &\text{设}ax_0+by_0=c\text{是}ax+by=c\text{的一组特解}\\ &\text{设}(x_0+t_x,y_0+t_y)\text{是下一组通解}\\ \implies &a(x_0+t_x)+b(y_0+t_y)=c\\ \iff & at_x+bt_y=c\\ &\text{设}d=\gcd(a,b),a=da',b=db',\gcd(a',b')=1\\ &t_y=-\frac{at_x}{b}\\ \iff & t_y=-\frac{a't_x}{b'}\\ \because &\gcd(a',b')=1\\ \therefore &\begin{cases}t_x=b'\\t_y=a' \end{cases}\\ \iff &\begin{cases}t_x=\frac{b}{gcd(a,b)}\\t_y=\frac{a}{gcd(a,b)} \end{cases}\\ \end{aligned}

code

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e6+10;

int n,cnt[6],t,ans;
char s[maxn];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(cnt,0,sizeof cnt);ans=0;
		scanf("%d",&n);
		scanf("%s",s+1);
		_F(i,1,4*n)
			if(s[i]<='D'||s[i]>='A')
				cnt[s[i]-'A']++;
		_F(i,0,3)
			ans+=min(cnt[i],n);
		printf("%d\n",ans);
	}
	return 0;
}

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e6+10;

ll n,t,a[maxn],mx,cnt,mx2;
int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld",&n);mx=0,cnt=0,mx2=0;
		_F(i,1,n)
			scanf("%lld",&a[i]),mx=max(mx,(a[i]&1)*a[i]);
		if(!mx)
		{
			puts("0");
			continue;
		}
		sort(a+1,a+1+n);
		F_(i,n,1)
			if(!(a[i]&1))
			{
				mx2=i;
				break;
			}
		_F(i,1,n)
		{
			if((!(a[i]&1))&&(mx>a[i]))
				mx=a[i]+mx,cnt++;
			else if(!(a[i]&1))
			{
				mx+=2*a[mx2],cnt+=2,a[mx2]=1;
				if(i!=mx2)
				{
					mx=a[i]+mx,cnt++;
				}
			}
		}
		printf("%lld\n",cnt);
	}
	return 0;
}

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e6+10;

int n,t,a[maxn],k,mx,mn,x;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);mx=0;
		_F(i,1,n)
			scanf("%d",&a[i]),mx=max(a[i],mx),a[i]%=2*k;
		sort(a+1,a+1+n);n=unique(a+1,a+1+n)-a-1;
		a[++n]=a[1];mn=11451419;
//		_F(i,1,n)
		_F(i,1,n-1)
			if(mn>(a[i]-a[i+1]+2*k)%(2*k))
			{
				mn=(a[i]-a[i+1]+2*k)%(2*k);
//				printf("%d ",(a[i]-a[i+1]+2*k)%2*k);
				x=i;
			}
		if(mn>=k)
			puts("-1");
		else
		{
			printf("%d\n",mx+(a[x]-(mx)%(2*k)+2*k)%k);
		}
	}
	return 0;
}

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e6+10;

int t,n,k,a[maxn],b[maxn],dp[maxn],l,r,ans;
int check(int x)
{
	_F(i,1,n)
		b[i]=(a[i]>x)?1:-1;
	dp[1]=b[1];
	_F(i,2,n)
	{
		if((i-1)%k==0) 
			dp[i]=max(dp[i-k],b[i]);
		else
			dp[i]=max(dp[i-1]+b[i],(i-k>0)?dp[i-k]:-114514191);
//		printf("%d ",dp[i]);
	}
//	puts("");
	return dp[n]>0;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);r=0;
		_F(i,1,n)
			scanf("%d",&a[i]),r=max(r,a[i]);
		l=1;ans=r;
		while(l<=r)
		{
			int mid=(l+r)>>1;
//			printf("***%d %d %.d\n",l,r,mid);
			if(check(mid))
				l=mid+1;
			else
				r=mid-1,ans=mid;
		}
		printf("%d\n",ans);
	}
	return 0;
}

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=1<<17;

ll n,m,t,a[20][20],dp[maxn][20],s[20][20],ans[20][20],inf=INT_MAX;
void work()
{
	_F(i,1,n)
	{
		_F(j,1,n)
		{
			if(i==j) continue;
			s[i][j]=0;
			_F(k,1,m)
				s[i][j]+=abs(a[i][k]-a[j][k]);
		}
	}
	_F(nl,1,m)
	{
		_F(i,0,(1<<n)-1)
		{
			_F(j,1,n)
			{
				dp[i][j]=inf;
			}
		}
		_F(i,1,n)
			dp[(1<<(i-1))][i]=0;
		_F(i,0,(1<<n)-1)
		{
			_F(j,1,n)
			{
				if(!(i&(1<<(j-1)))) continue;
				_F(k,1,n)
				{
					if(i&(1<<(k-1))) continue;
					dp[i|(1<<(k-1))][k]=min(dp[i|(1<<(k-1))][k],dp[i][j]-abs(a[j][nl]-a[k][nl])+s[j][k]);
				}
			}
		}
		_F(i,1,n)
		{
			ans[i][nl]=inf;
			_F(j,1,n)
			{
				if(i==j)continue;
				ans[i][nl]=min(ans[i][nl],dp[((1<<n)-1)^(1<<(i-1))][j]);
			}
		}
	}
	_F(i,1,m)
	{
		_F(j,1,m)
		{ 	
			if(i==j) continue;
			s[i][j]=0;
			_F(k,1,n)
				s[i][j]+=abs(a[k][i]-a[k][j]);
		}
	}
	_F(nr,1,n)
	{
		_F(i,0,(1<<m)-1)
		{
			_F(j,1,m)
			{
				dp[i][j]=inf;
			}
		}
		_F(i,1,m)
			dp[(1<<(i-1))][i]=0;
		_F(i,0,(1<<m)-1)
		{
			_F(j,1,m)
			{
				if(!(i&(1<<(j-1)))) continue;
				_F(k,1,m)
				{
					if(i&(1<<(k-1))) continue;
					dp[i|(1<<(k-1))][k]=min(dp[i|(1<<(k-1))][k],dp[i][j]-abs(a[nr][k]-a[nr][j])+s[j][k]);
//					printf("%x %d %d %lld\n",i,j,k,dp[i|(1<<(k-1))][k]);
				}
			}
		}
//		puts("");
		_F(i,1,m)
		{
			ll x=inf;
			_F(j,1,m)
			{
				if(i==j)continue;
				x=min(x,dp[((1<<m)-1)^(1<<(i-1))][j]);
			}
			ans[nr][i]+=x;
		}
	}
	ll res=inf;
	_F(i,1,n)
	{
		_F(j,1,m)
		{
			res=min(res,ans[i][j]);
		}
	}
	printf("%lld\n",res);
}
int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&m);
		memset(a,0,sizeof a);
		_F(i,1,n)
			_F(j,1,m)
				scanf("%lld",&a[i][j]),a[n+1][j]^=a[i][j],a[i][m+1]^=a[i][j],a[n+1][m+1]^=a[i][j];
		n++,m++;
		work();
	}
	return 0;
}
//1 3 2

F1/2.

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e6+10;

ll n,t,w,h,k,sx,sy,dx,dy,ans;
char s[maxn];
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	ll d=exgcd(b,a%b,x,y),tmp=x;
	x=y;
	y=tmp-a/b*y;
	return d;
}
ll ksc(ll a,ll b,ll p)
{
	ll tmp=(a*b)-(ll)((long double)a*b/p+0.5)*p;
//	printf("%lld\n",tmp);
	if(tmp<0)
		tmp+=p;
	return tmp;
}
ll get(ll a1,ll b1,ll m1,ll a2,ll b2,ll m2)
{
	a1=(a1%m1+m1)%m1,b1=(b1%m1+m1)%m1;
	a2=(a2%m2+m2)%m2,b2=(b2%m2+m2)%m2;
//	printf("%lld %lld %lld %lld\n",a1,b1,a2,b2);
	ll x,y;
	ll d=exgcd(a1,m1,x,y);
	if(b1%d)
		return 0;
	a1=ksc(x,b1/d,m1/d),m1=m1/d;//a1->r,b1->m
	d=exgcd(a2,m2,x,y);
//	printf("%lld\n",b2);
	if(b2%d)
		return 0;
	a2=ksc(x,b2/d,m2/d),m2=m2/d;
//	printf("%lld %lld %lld %lld\n",a2,m2,d,x);
	//excrt
	a2=a2-a1;//a2=(d[i]-b),m1=a,m2=c[i],x=k,g=d;
	d=exgcd(m1,m2,x,y);
	if(a2%d)
		return 0;
	x=ksc(x,a2/d,m2/d);
	m2=m1/d*m2;
	a1=(ksc(m1,x,m2)+a1)%m2;
	a1=(a1%m2+m2)%m2;
	if(a1>=k)
		return 0;
	return (k-1-a1)/m2+1;
}
void solve()
{
	dx=dy=0,ans=0;
	_F(i,1,n)
	{
		if(s[i]=='U')
			dy++;
		if(s[i]=='D')
			dy--;
		if(s[i]=='L')
			dx--;
		if(s[i]=='R')
			dx++;
	}
	sy=sx=0;
	_F(i,1,n)
	{
		if(s[i]=='U')
			sy++;
		if(s[i]=='D')
			sy--;
		if(s[i]=='L')
			sx--;
		if(s[i]=='R')
			sx++;
		ans+=get(dx,-sx,2*w,dy,-sy,2*h);
	}
	printf("%lld\n",ans);
}
int main()
{
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld%lld%lld",&n,&k,&w,&h);
		scanf("%s",s+1);
		solve();
	}
	return 0;
}
/*6
2 4 2 2
UR
1 0 1 3
0
0 4 1 -4
1 3 1 3
3
0 4 1 -4
2

G(64)
*/

文章分类

一言

文章归档

最新文章

CF1993 VP 记录

A. Question Marks

题意

思路

B. Parity and Sum

题意

思路

C. Light Switches

题意

思路

D. Med-imize

题意

思路

extand

trick

E. Xor-Grid Problem

题意

思路

extand

extand

F2. Dyn-scripted Robot (Hard Version)

题意

思路

code