CF-927

依旧……难绷……

E有思路，等睡醒再补-^-

B

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=2e5+5;
int a[N];
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t,n,x,cnt=0,ans=0;cin>>t;
	while(t--){
		cin>>n;
		rep(i,1,n){
			cin>>a[i];
		}
		ans=a[1];
		rep(i,2,n){
			ans=a[i]*(1+ans/a[i]);
			a[i]=ans;
		}
		cout<<ans<<endl;
	}
	return 0;
}

C

分析

不能直接求积作除——关键在于除法的模运算要用到逆元，而m又不一定为质数。所以应该考虑不用除法运算的方法。

操作

1. 可以用线段树维护区间积，读入指令相当与查询的左右边界移动
2. 题中的操作我们可以理解成按指令顺序把乘积除以删掉的数再取模输出，那反过来想，输出的反向顺序是不是就是把1乘上倒序的删数顺序的数再取模输出？

如

4 6
3 1 4 2
LRRL
删数顺序：3 2 4 1
其倒序为：1 4 2 3
输出的倒序为：1 4(1*4%6) 2(1*4*2%6) 0(1*4*2*3%6) 

代码

线段树做法

用区间和的板子改的……

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define endl '\n'
#define int long long
#define debug(x) cout<<x<<" "<<endl;
#define _debug(a,n) for(int i=0;i<n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a, b) memset(a, b, sizeof(a))
#define lc p<<1
#define rc p<<1|1
const int N=2e5+5;
int a[N],n,m;
struct tree{
	int l,r,sum;
}tr[N<<2];
void pushup(int p){
	tr[p].sum=(tr[lc].sum%m*tr[rc].sum%m)%m;
}
void build(int p,int l,int r){	
	tr[p]={l,r,a[l]};
	if(l==r) return; 
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(p);
}
int query(int p,int x,int y){ 
	if(x<=tr[p].l&&y>=tr[p].r){
		return tr[p].sum%m;
	}	
	int mid=tr[p].l+tr[p].r>>1;
	int sum=1;
	if(x<=mid) sum*=query(lc,x,y)%m;
	if(y>mid) sum*=query(rc,x,y)%m;
	sum%=m;
	return sum;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int x,y,op,k,t;cin>>t;
	while(t--){
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];	
		string s;cin>>s;
		build(1,1,n);
		x=1,y=n;	
		for(auto i:s){
			cout<<query(1,x,y)<<" ";
			if(i=='L') x++;			
			else y--;
		}		
		cout<<endl;
	}

    return 0;
}

倒序做法

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t,n,x,m,cnt=0,ans=0;cin>>t;
	while(t--){
		cin>>n>>m;
		deque<int>q,tmp,out;
		rep(i,1,n){
			cin>>x;
			q.push_back(x);
		}
		string s;cin>>s;
		for(auto i:s){
			if(i=='R'){
				tmp.push_back(q.back());
				q.pop_back();
			}
			else{
				tmp.push_back(q.front());
				q.pop_front();
			}
		}
//		for(auto i:tmp) cout<<i<<" ";
		reverse(tmp.begin(),tmp.end());
		int e=1;
		for(auto i:tmp){
			e*=i;
			e%=m;
			out.push_front(e);
		}
		for(auto i:out){
			cout<<i<<" ";
		}
		cout<<endl;
	}
	return 0;
}

E