传送门: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[2*W-x] mp[2∗W−x].注意:考虑到 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[i]=='L') x--;
- else if(s[i]=='R') x++;
- else if(s[i]=='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;
- }
- #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/d y=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[maxn],b[maxn];int N;
- int EXCRT() {//最后返回结果在A(模数的lcm)范围内是唯一解
- int A=a[1],B=b[1];
- for(int i=2;i<=N;i++) {
- int x0,y0;int c=b[i]-B;
- int GCD=EXGCD(A,a[i],x0,y0);
- if(c%GCD!=0) return -1;
- x0*=c/GCD;y0*=c/GCD;
- int x=x0*A+B;A=lcm(A,a[i]);
- 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[i]=='L') x--;
- else if(s[i]=='R') x++;
- else if(s[i]=='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 [k1,k2]:mp) {
- int x0,y0;
- int GCD=EXGCD(dx,W,x0,y0);
- if((W-k1.first)%GCD!=0) continue;
- x0*=(W-k1.first)/GCD;
- a[1]=W/GCD;
- b[1]=(x0%a[1]+a[1])%a[1];
- GCD=EXGCD(dy,H,x0,y0);
- if((H-k1.second)%GCD!=0) continue;
- x0*=(H-k1.second)/GCD;
- a[2]=H/GCD;
- b[2]=(x0%a[2]+a[2])%a[2];
- int num=EXCRT();
- if(num==-1||num>=k) {
- continue;
- }
- else {
- ans+=((k-1-num)/lcm(a[1],a[2])+1)*k2;
- }
- }
- cout<<ans<<'\n';
- //clear
- mp.clear();
- }
- return 0;
- }
|
