E

概率dp/期望dp

每一次投出一个点数y，范围$[1,n]$，如果比x小，结束。如果比x大，y=x，总分加$a_y$。问总分的期望？

两个思路，一是可以概率dp，因为总分的期望等于每个$a_i$的贡献的期望和，可以正着dp，算出来达到每个$i$的概率，这显然就是个前缀和优化。但这个并不自然

求期望，还是考虑期望dp，$d{p}_i$表示当前$x=i$开始玩，剩下的得分的期望。当前投一次有$n$种取值，只有投出比$i$大的才有意义，转移就是$d{p}_u=\frac{1}{n}({\sum }_{j=i+1}^{n}dp+a_i)$，这可以前缀和优化。

最后答案是$d{p}_0$

int dp[N],n,a[N];
void solve(void){
	cin>>n;
	rep(i,1,n)cin>>a[i];
	int sum=0;
	rep1(i,n-1,0){
		sum=(sum+(a[i+1]+dp[i+1])%M2)%M2;
		dp[i]=sum*inv(n)%M2;
	}
	cout<<dp[0];
}

F

折半搜索 状压 构造

每次要么左转90度要么右转90度，然后走$a_i$。问能否走到$(x,y)$，给出转向方案

这种必须转的，实际上就是奇数只能走一个轴，偶数只能走另外一个轴。x,y两个维度可以拆开。能不能到达目标点，每个维度就是一个给序列添加符号求和，问和能否为某个值。

看起来是个背包，但是值域太大。元素个数又不多。考虑搜索。每个维度都有$40$个元素，直接搜还是会超时，40是个比较敏感的数字，它的一半比较适合搜索，考虑折半搜索，搜出来前半部分和后半部分的所有方案，检查能否有一对拼成目标和。

具体实现时，由于每个元素只有两种选择，可以状压枚举所有状态，每一位0则减掉，1则加上。

我们还需要方案，需要把合法状态，前20和后20拼起来返回，然后初始状态，根据x,y轴的方案的mask，构造转向方案，如果x,y方向都有合法方案，这肯定是能构造出来的

void solve()
{
	int n,x,y;
	cin>>n>>x>>y;
	vi a,b;
	rep(i,1,n){
		int x;
		cin>>x;
		if(i&1){
			a.push_back(x);
		}
		else{
			b.push_back(x);
		}
	}
	
	auto cal=[](vi &a,int x)->int{
		int len=a.size();
		int pre=len/2,suf=len-pre;
		unordered_map<int,int>mp;
		for(int i=0;i<(1<<pre);i++){
			int sum=0;
			for(int j=0;j<pre;j++){
				if(i>>j&1){
					sum+=a[j];
				}
				else{
					sum-=a[j];
				}
			}
			mp[sum]=i;
		}	
		for(int i=0;i<(1<<suf);i++){
			int sum=0;
			for(int j=0;j<suf;j++){
				if(i>>j&1){
					sum+=a[j+pre];
				}
				else{
					sum-=a[j+pre];
				}
			}
			if(mp.count(x-sum)){
				return (i<<pre)|mp[x-sum];
			}
		}
		return -1;
	};
	int ansa=cal(a,y);
	int ansb=cal(b,x);
	if(ansa==-1||ansb==-1){
		cout<<"No\n";
	}
	else{
		cout<<"Yes\n";
		int dir=1,aa=0,bb=0;
		string res;
		rep(i,1,n){
			char ans;
			if(i&1){
				if(ansa>>aa&1){
					ans=(dir==1)?'L':'R';
					dir=2;	
				}
				else{
					ans=(dir==1)?'R':'L';
					dir=4;
				}
				aa++;
			}
			else{
				if(ansb>>bb&1){
					ans=(dir==2)?'R':'L';
					dir=1;
				}
				else{
					ans=(dir==2)?'L':'R';
					dir=3;
				}
				bb++;
			}
			res+=ans;
		}
		cout<<res;
	}
}