yukicoder : No.2965 Don't Stop the Game again

なんか問題文にびっくりさせられる問題。
https://yukicoder.me/problems/no/2965

問題

N=50要素の整数列A,Qがあり、そのうちQは入力で与えられる。
また、Qの各要素は1～40をそれぞれ1個以上含む。

初期状態で各要素0のN要素の整数列Bがある。
Bに以下の処理を250回まで行い、sum(A)=sum(B)とせよ。

• 整数jを指定すると、各B[i]にA[j]^Q[i]が加算される。
• 1～50の順列Pを指定すると、B[j]にsum(A[P[i]]^j^(i-1))が加算される。
• i,j,kを指定して、B[k]=B[i]*B[j]とする
• i,j,kを指定して、B[k]=B[i]+B[j]とする
• i,j,kを指定して、B[k]=B[i]^B[j]とする

解法

1つ目と4つ目さえあればよい。
まず1つ目の処理をj=1～50で行うと、Q[x]=1となるxでB[x]=sum(A)となる。
あとは、Bの他の要素を0にすればよい。
B[y]を1つMの倍数にできれば、それを4つ目の処理でB[y]+B[y]を他の要素の代入することで全部0にできる。
B[y]をMの倍数にするには、4つ目の処理で倍々にB[y],2*B[y],4*B[y],....と作って、総和がM*B[y]となるようにそれらの一部の和を取ればよい。

int M;
ll Q[55];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<vector<int>> R;
	cin>>M;
	FOR(i,50) {
		cin>>Q[i];
		if(Q[i]==1) x=i;
		if(Q[i]!=1) y=i;
	}
	int sum=x;
	FOR(i,50) R.push_back({1,i+1});
	vector<int> C={y};
	FOR(i,50) if(i!=y&&i!=x) C.push_back(i);
	FOR(i,30) {
		R.push_back({4,C[i]+1,C[i]+1,C[i+1]+1});
	}
	int first=-1;
	FOR(i,30) if(M&(1<<i)) {
		if(first==-1) {
			first=C[i];
		}
		else {
			R.push_back({4,first+1,C[i]+1,first+1});
		}
	}
	
	FOR(i,50) if(i!=first&&i!=sum) R.push_back({4,first+1,first+1,i+1});
	
	cout<<R.size()<<endl;
	FORR(r,R) {
		FOR(i,r.size()-1) cout<<r[i]<<" ";
		cout<<r.back()<<endl;
	}
	
}

まとめ

気が付いてしまえばすぐである。