封面：pixiv56803275

比赛链接：AtCoder Beginner Contest 189

最后五分钟把E题交到F题上去了...

D - Logical Expression

题目大意：
定义S[i]为操作符

bool f=x[0];
for (int i=1;i<=n;i++)
    f=f S[i] x[i];

要求计算符合f==truef==true条件x数组的数量
简单DP

struct solution{
	int n;
	vi v;
	solution(){
		n=gi();
		v.pb(-1);
		for (int i=1;i<=n;i++){
			string a;
			cin >> a;
			if (a[0]=='A') v.pb(1);
			else v.pb(0);
		}
	}
	
	void solve(){
		array<array<ll,2>,120> dp;
		dp[0][1]=1;
		dp[0][0]=1;
		for (int i=1;i<=n;i++){
			if (v[i]){//AND
				dp[i][0]=dp[i-1][0]*2+dp[i-1][1];
				dp[i][1]=dp[i-1][1];
			}else{//OR
				dp[i][0]=dp[i-1][0];
				dp[i][1]=dp[i-1][0]+dp[i-1][1]*2;
			}
		}
		cout << dp[n][1];
	}
};

E - Rotate and Flip

容易观察到，1,2操作涉及x,y之间的交换。如果排除这个交换来看所有操作都是线性变换，多个线性变换可合并且形式仍为a∗x+ba*x+b。我们称其具有线性。

定义点p=(x,y)p=(x,y)
定义线性变换函数l(x)=a∗x+bl(x)=a*x+b
定义Linear(p,l1,l2)=(l1(p.x),l2(p.y))Linear(p,l1,l2)=(l1(p.x),l2(p.y))
线性即Linear(Linear(p,l1,l2),l3,l4)=Linear(p,l3(l1),l4(l2))Linear(Linear(p,l1,l2),l3,l4)=Linear(p,l3(l1),l4(l2))

加入了交换之后，单独对于每一个横或纵坐标也是线性的，意味着交换操作和线性变换操作可合并为题目要求的总操作。
定义Swap(p)Swap(p)表示对点pp的xx和yy交换。

考虑交换的性质：
1、Swap(Linear(p,l1,l2))=Linear(Swap(p),l2,l1)Swap(Linear(p,l1,l2))=Linear(Swap(p),l2,l1)
2、Swap(Swap(p))=pSwap(Swap(p))=p

我们把最外层的Swap()数量存起来为swt
里层的线性函数l1的a,b；l2的a,b也存起来

可用线代知识证明1操作即为定义
l1(x)=−1∗x+0l1(x)=-1*x+0
l2(x)=1∗x+0l2(x)=1*x+0
下
Swap(Linear(p,l1,l2))Swap(Linear(p,l1,l2))
其他略

你已经掌握了足够多的数学知识，相信你一定能看得懂下面的代码。
加油，试试看！

// Problem: E - Rotate and Flip
// Contest: AtCoder - AtCoder Beginner Contest 189
// URL: https://atcoder.jp/contests/abc189/tasks/abc189_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
ll gi(){
    ll i=0;bool f=false;char c;
    while (!isdigit(c=cin.get())&&cin.good()) f=c=='-';
    if (!cin.good()) return 0;
    do i=(i<<3)+(i<<1)+c-'0'; while (isdigit(c=cin.get()));
    return f?-i:i;
}

struct solution{
	int n;
	vector<array<ll,2>> pv;
	vll axv,bxv,swt;
	vll ayv,byv;
	solution(){
		n=gi();
		for (int i=1;i<=n;i++)
			pv.pb({gi(),gi()});
		axv=bxv=ayv=byv=swt=vll();
		axv.pb(1);bxv.pb(0);
		ayv.pb(1);byv.pb(0);
		swt.pb(0);
		int qs=gi();
		for (int i=1;i<=qs;i++){
			int q=gi();
			if (q==1){
				auto f=[](vll &axv,vll &bxv,vll &ayv,vll &byv){
					ll ax=axv.back();ll bx=bxv.back();
					ll ay=ayv.back();ll by=byv.back();
					ayv.pb(ay);byv.pb(by);
					axv.pb(-ax);bxv.pb(-bx);
				};
				if (swt.back()) f(ayv,byv,axv,bxv);
				else f(axv,bxv,ayv,byv);
				swt.pb(!swt.back());
			}else if (q==2){
				auto f=[](vll &axv,vll &bxv,vll &ayv,vll &byv){
					ll ax=axv.back();ll bx=bxv.back();
					ll ay=ayv.back();ll by=byv.back();
					ayv.pb(-ay);byv.pb(-by);
					axv.pb(ax);bxv.pb(bx);
				};
				if (swt.back()) f(ayv,byv,axv,bxv);
				else f(axv,bxv,ayv,byv);
				swt.pb(!swt.back());
			}else if (q==4){
				auto f=[](vll &axv,vll &bxv,vll &ayv,vll &byv){
					ll d=gi();
					ll ax=axv.back();ll bx=bxv.back();
					ll ay=ayv.back();ll by=byv.back();
					axv.pb(ax);bxv.pb(bx);
					ayv.pb(-ay);byv.pb(2*d-by);
				};
				if (swt.back()) f(ayv,byv,axv,bxv);
				else f(axv,bxv,ayv,byv);
				swt.pb(swt.back());
			}else if (q==3){	
				auto f=[](vll &axv,vll &bxv,vll &ayv,vll &byv){
					ll d=gi();
					ll ax=axv.back();ll bx=bxv.back();
					ll ay=ayv.back();ll by=byv.back();
					axv.pb(-ax);bxv.pb(2*d-bx);
					ayv.pb(ay);byv.pb(by);
				};
				if (swt.back()) f(ayv,byv,axv,bxv);
				else f(axv,bxv,ayv,byv);
				swt.pb(swt.back());
			}
			#undef int
		}
	}
	
	void solve(){
		int q=gi();
		while (q--){
			int a=gi(),b=gi()-1;
			ll x=pv[b][0],y=pv[b][1];
			x=axv[a]*x+bxv[a];
			y=ayv[a]*y+byv[a];
			if (swt[a]) swap(x,y);
			cout << x << " " << y << endl;
		}
	}
};
 
int main(){
	ios::sync_with_stdio(false);
	solution().solve();
}