CF1993F Dyn-scripted Robot (Easy Version&Hard Version) [扩展中国剩余定
传送门:CF[前题提要]:一道扩展中国剩余定理的标题,自从模板题之后就很少遇到这种题,而且是AC的第二道*2800的标题,故写篇题解记载一下
起首考虑 E a s y Easy Easy和 H a r d Hard Hard的区别,不难发现区别是循环的次数.以是猜想一下,显然 E a s y Easy Easy的做法应该是和枚举是第几次循环有关.然后我们会发现显然横坐标和纵坐标是可以分开来考虑.那么为了简朴起见,我们先只考虑横坐标变为0是什么情况.
直接模拟标题,会发现遇到边界翻转操纵序列是一件很难的事变,以是会想到是不是会存在某个规律,考虑手模一下样例或者是本身手造几个样例,诶,会发现每次达到0点的时候事实上是前缀操纵序列和为(2*W)的倍数的时候(此时我们将向右走记为1,向左走记为-1).这个结论非常的重要!!! 固然会有人会怎么注意到这个结论的,只能说运气,或者说一种直觉??
此时我们考虑枚举第几次操纵序列,然后假设当前我们所在的位置是 x x x,那么我们这一次操纵序列经过之后的贡献就是( s u m i sum_i sumi+ x x x)是 2 ∗ W 2*W 2∗W的倍数的个数(我们将前缀和记为 s u m i sum_i sumi),我们将其数学化,也就是问有多少个 ( s u m i + x ) % ( 2 ∗ W ) = 0 (sum_i+x)\%(2*W)=0 (sumi+x)%(2∗W)=0显然的我们可以直接通过预处理出模 2 ∗ W 2*W 2∗W意义下的数的个数,不妨记为 m p [ ] mp[\;] mp[],那么对于每一个 x x x,显然我们的贡献就是 m p [ 2 ∗ W − x ] mp mp.注意:考虑到 x < 2 ∗ W , s u m i < 2 ∗ W x<2*W,sum_i<2*W x<2∗W,sumi<2∗W,以是贡献只能是 2 ∗ W 2*W 2∗W
固然上述只是考虑了横坐标的情况,如果我们加入纵坐标的情况,只要开一个二维的累加一下即可.
以是此时我们的 E a s y Easy Easy就解决了,直接模拟即可.
现在考虑 H a r d Hard Hard.显然的,我们得顺着 E a s y Easy Easy得出来的结论去思考.现在我们不能枚举当前是第几次操纵了.其实,这个时候做 C F CF CF题做多了不能枚举的标题,不难会想到是不是可以直接反过来贡献一下.诶,事实上是可以的.对于本题来说,我们反过来想一下,对于 s u m i sum_i sumi,有多少个 x x x能有贡献,那么它们累加起来不就可行了.做 E a s y Easy Easy的时候不难发现经过一次的操纵序列,我们的 x + = s u m x n , y + = s u m y n x+=sumx_n,y+=sumy_n x+=sumxn,y+=sumyn,为了方便起见,我们将 s u m x n sumx_n sumxn记为 d x dx dx, s u m y n sumy_n sumyn记为 d y dy dy.那么我们的 x x x序列是 0 , 0 + d x , 0 + 2 ∗ d x , . . . , 0 + ( k − 1 ) ∗ d x 0,0+dx,0+2*dx,...,0+(k-1)*dx 0,0+dx,0+2∗dx,...,0+(k−1)∗dx,同理, y y y序列是 0 , 0 + d y , 0 + 2 ∗ d y , . . . , 0 + ( k − 1 ) ∗ d y 0,0+dy,0+2*dy,...,0+(k-1)*dy 0,0+dy,0+2∗dy,...,0+(k−1)∗dy.那么此时题目就酿成了,同时满意下面等式的 k k k的个数 ( k ∗ d x + s u m x i ) % ( 2 ∗ W ) = 0 ( k ∗ d y + s u m y i ) % ( 2 ∗ H ) = 0 (k*dx+sumx_i)\%(2*W)=0 \\ (k*dy+sumy_i)\%(2*H)=0 (k∗dx+sumxi)%(2∗W)=0(k∗dy+sumyi)%(2∗H)=0考虑到 s u m x i < 2 ∗ W , s u m y i < 2 ∗ H sumx_i<2*W,sumy_i<2*H sumxi<2∗W,sumyi<2∗H,以是我们可以化简上式:
k ∗ d x ≡ ( 2 ∗ W − s u m x i ) m o d ( 2 ∗ W ) k ∗ d y ≡ ( 2 ∗ H − s u m y i ) m o d ( 2 ∗ H ) k*dx\equiv(2*W-sumx_i) \;mod(2*W) \\ k*dy\equiv(2*H-sumy_i)\;mod(2*H) k∗dx≡(2∗W−sumxi)mod(2∗W)k∗dy≡(2∗H−sumyi)mod(2∗H)发现是一个同余式,同时模数并不是质数,以是考虑利用扩展中国剩余定理去解.回想一下扩展中国剩余定理的题目式子,是 x ≡ b i m o d a i x\equiv b_i mod\;a_i x≡bimodai诶有点不一样,我们此时的x前面有一个系数,此时会有人说了,我们直接将dx拿逆元除掉行不行,固然不行,因为我们此时的dx不一定和模数互质,以是费马小定理用不了,但是对于一个同余式,我们是可以利用扩展欧几里得解出一个关于x0的通式的(举个栗子,显然第一个同余式等同于 k ∗ d x + g ∗ ( 2 ∗ W ) = 2 ∗ W − s u m x i k*dx+g*(2*W)=2*W-sumx_i k∗dx+g∗(2∗W)=2∗W−sumxi) 而对于那个通式,我们会发现k的系数为1,符合扩展中国剩余定理的题目式,以是我们对上述两个式子先拿扩欧解出通式,然后再把通式转成同余式,然后用扩展中国剩余定理求那两个同余式.但是必要注意的是,扩展中国剩余定理只能求出 l c m ( 模数 ) lcm(模数) lcm(模数)范围内的唯一解,但是我们的 k k k是有大概大于这个 l c m lcm lcm,以是实际上这个解的个数得拿 k k k除一下模数求出真正的贡献(事实上此时的合法k序列是一个等差数列)
接下来是具体的代码部分:
E a s y Easy Easy版本:
//光这道题感觉很难有*2400吧
//需要注意到(手模)发现翻转序列后回到(0,0)的贡献事实上等价于不翻转序列到模(2W,2H)为0的贡献
//那么这道easy version就简单了,因为我们可以枚举k,然后对于每次的k,我们会发现其增量是可以预处理的
//所以只需要拿map存一下增量即可
//还需要注意的一点是,对于两个小于2W的数,他们之和必然是小于4*W的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pd __gnu_pbds
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
inline void print(__int128 x){
if(x<0) {putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
#define maxn 1000010
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
map<pair<int,int>,int>mp;
int main() {
cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--) {
int n,k,w,h;
cin>>n>>k>>w>>h;
string s;cin>>s;
s=" "+s;
int x=0;int y=0;
int W=2*w;int H=2*h;
for(int i=1;i<=n;i++) {
if(s=='L') x--;
else if(s=='R') x++;
else if(s=='U') y++;
else y--;
x=(x%W+W)%W;y=(y%H+H)%H;
mp[{x,y}]++;
}
int dx=x;int dy=y;
x=0;y=0;ll ans=0;
for(int i=1;i<=k;i++) {
int tempx=(W-x+W)%W;
int tempy=(H-y+H)%H;
ans+=mp[{tempx,tempy}];
x+=dx;x%=W;
y+=dy;y%=H;
}
cout<<ans<<'\n';
//clear
mp.clear();
}
return 0;
}
H a r d Hard Hard版本:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define pd __gnu_pbds
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
inline void print(__int128 x){
if(x<0) {putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
#define maxn 1000010
#define int long long
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int EXGCD(int a,int b,int &x,int &y) {
//ax+by=c,gcd(a,b)=d;
//x=c/d*x0+k*b/dy=c/d*y0-k*a/d
if(a%b==0) {
x=0;y=1;return b;
}
int GCD=EXGCD(b,a%b,x,y);
int temp=x;x=y;y=temp-a/b*x;
return GCD;
}
int a,b;int N;
int EXCRT() {//最后返回结果在A(模数的lcm)范围内是唯一解
int A=a,B=b;
for(int i=2;i<=N;i++) {
int x0,y0;int c=b-B;
int GCD=EXGCD(A,a,x0,y0);
if(c%GCD!=0) return -1;
x0*=c/GCD;y0*=c/GCD;
int x=x0*A+B;A=lcm(A,a);
x=(x%A+A)%A;
B=x;
}
return (B%A+A)%A;
}
map<pair<int,int>,int>mp;
signed main() {
cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--) {
int n,k,w,h;
cin>>n>>k>>w>>h;
string s;cin>>s;
s=" "+s;
int x=0;int y=0;
int W=2*w;int H=2*h;
for(int i=1;i<=n;i++) {
if(s=='L') x--;
else if(s=='R') x++;
else if(s=='U') y++;
else y--;
x=(x%W+W)%W;y=(y%H+H)%H;
mp[{x,y}]++;
}
int dx=x;int dy=y;
N=2;
int ans=0;
for(auto :mp) {
int x0,y0;
int GCD=EXGCD(dx,W,x0,y0);
if((W-k1.first)%GCD!=0) continue;
x0*=(W-k1.first)/GCD;
a=W/GCD;
b=(x0%a+a)%a;
GCD=EXGCD(dy,H,x0,y0);
if((H-k1.second)%GCD!=0) continue;
x0*=(H-k1.second)/GCD;
a=H/GCD;
b=(x0%a+a)%a;
int num=EXCRT();
if(num==-1||num>=k) {
continue;
}
else {
ans+=((k-1-num)/lcm(a,a)+1)*k2;
}
}
cout<<ans<<'\n';
//clear
mp.clear();
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]