D - Logical Expression

题目大意:给定\(n\)个字符串,每个都是AND或者OR.要求你构造\(n+1\)个值,记入\(\{x0,x1,x2,...xn\}\).每个值只能取\(0/1\),同时根据你构造的\(x\)集合构造另外一个\(y\)集合:

• \(y0 = x0\)
• 对于\(i\geq 1\),\(y_i = y_{i-1} \& x_i\)当且仅当\(s_i=\)AND.\(y_i=y_{i-1}\| x_i\)当且仅当\(s_i=\)OR.

如果\(y_n=1\)那么则称构造出此\(y\)集合的\(x\)集合是牛逼的,求牛逼的\(x\)集合的方案个数.

数据范围:

\(1 \leq n \leq 60\)

思路

直接dp没什么好说的.

• 状态\(f[i][j]\)表示当前的\(y_i=j\)的方案数
• 入口:\(f[0][0] = f[0][1] = 1\)其余全\(0\).
• 转移:按情况讨论即可,如果当前是取AND,那么当前的\(y_i\)如果想要是\(1\)必须要是\(x_i=1\)且上一位也是\(1\),\(f[i][1]=f[i-1][1]\),如果当前\(y_i=0\)那么当前\(x_i=0\)时上一位任意选择,如果当前\(x_i=1\)时上一位只能选择\(0\)也就是\(f[i][0] = f[i - 1][1] * f[i - 1][0] + f[i - 1][0]\).对于取OR的情况对称处理就可以了.
• 出口:\(f[n][1]\).

直接暴力转移,反正就\(60\)位,方案数比较大,开\(ll\)就可以过了.

E - Rotate and Flip

题目大意:在二维平面上有\(n\)个点,给定\(m\)个操作,每个操作形如:

• 点关于原点顺时针旋转\(90\)°.
• 点关于原点逆时针旋转\(90\)°.
• 点关于直线\(x=p\)的对称.
• 点关于直线\(y=p\)的对称.

之后有\(q\)个询问,每个询问问一个指定的点\(B\)在执行了\(A\)次操作之后的坐标的值.特别的,如果询问的是第\(0\)次操作之后的位置,那么就是要求没有经过任何操作时的坐标.

数据范围:

\(1 \leq n \leq 2 * 10^5\)

\(1 \leq m \leq 2 * 10^5\)

\(1 \leq q \leq 2 * 10^5\)

\(10^{-9} \leq x_i,y_i \leq 10^9\)

\(10^{-9} \leq p \leq 10^9\)

思路

套路题,显然是要把所有的操作合并在一起直接对指定的坐标进行变换.考虑操作的表示和合并.一种初等做法是把坐标变换找出来并且发现本质是交换,对点加常数之后直接进行维护.另外一种更明了的做法是矩阵:

首先对于旋转操作,有比较套路的做法是套用旋转矩阵\(\begin{vmatrix}cos\theta & -sin\theta\\sin\theta & cos\theta \end{vmatrix}\).前两种操作可以直接旋转矩阵套出来,比较显然.后面两种可以先把坐标代换找出来,也是比较简单,以第三种为例,也就是要让\([x,y]*B=[2p-x,y]\),不过这里有个问题,如果直接待定系数去求\(B\)矩阵那么会发现求出来的\(B\)矩阵是依赖\(x\)的取值的,那么如果依赖于\(x\)的取值,这个操作就不能合并了,还需要做一些处理,这里可以把\([x,y]\)多加一个常数项变成\([x,y,1]\),那么再求就可以踢掉\(x\)的影响了,构造出来的矩阵就是\(\begin{vmatrix}-1 & 0 & 0\\0 & 1 & 0 \\2p &0 & 1 \end{vmatrix}\).对于第四种操作也是同理,那么顺次把所有操作以矩阵表示出来,可以发现对于求答案的这一步等价于是让\([x,y,1]\)顺次去乘每个操作的矩阵,而后面这部分可以先预处理出来,也就是做一个前缀积的矩阵\(op[i]\)表示前\(i\)个操作矩阵的前缀积,那么结果就是直接让\([x,y,1]\)乘上\(A\)次操作后的矩阵就可以了.

当然由于拓展了坐标的列,所以旋转矩阵也需要额外多加一个\(1\)在右下角保证常数项不变.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	
typedef pair<int,int> pii;
#define x first
#define y second

const int N = 3,_N = 2e5 + 7;
struct mat
{
	ll m[N][N];
};

pii a[_N];
mat op[_N];

mat mul(mat A,mat B,int len)
{
    mat c;memset(c.m,0,sizeof c.m);
    for(ll i = 0;i < len;++i)
        for(ll j = 0;j < len;++j)
            for(ll k = 0;k < len;++k)
            {
            	c.m[i][j]=(c.m[i][j]+(A.m[i][k]*B.m[k][j]));
            }
	return c;
}
mat qpow(mat a,ll len,ll k)
{
   	mat res;memset(res.m,0,sizeof res.m);
    for(ll i = 0;i < len;++i)   res.m[i][i] = 1;
    while(k)
    {
        if(k & 1)   res = mul(res,a,len);
        a = mul(a,a,len);
        k >>= 1;
    }
    return res;
}

int main()
{
	int n;scanf("%d",&n);
	forn(i,1,n)	scanf("%d%d",&a[i].x,&a[i].y);
    int m;scanf("%d",&m);
    forn(i,1,m)
    {
    	int t;scanf("%d",&t);
    	mat _;memset(_.m,0,sizeof _.m);
    	if(t == 1)
    	{
    		_.m[0][1] = -1;_.m[1][0] = 1;_.m[2][2] = 1;
    		op[i] = mul(op[i - 1],_,3);
    	}
    	else if(t == 2)
    	{
    		_.m[0][1] = 1;_.m[1][0] = -1;_.m[2][2] = 1;
    		op[i] = mul(op[i - 1],_,3);
    	}
    	else if(t == 3)
    	{
    		int p;scanf("%d",&p);
    		_.m[0][0] = -1;_.m[1][1] = 1;_.m[2][0] = 2 * p;_.m[2][2] = 1;
    		op[i] = mul(op[i - 1],_,3);
    	}
    	else
    	{
    		int p;scanf("%d",&p);
    		_.m[0][0] = 1;_.m[1][1] = -1;_.m[2][1] = 2 * p;_.m[2][2] = 1;
    		op[i] = mul(op[i - 1],_,3);
    	}
    	if(i == 1)	op[i] = _;
    }
    int q;scanf("%d",&q);
    while(q--)
    {
    	int A,B;scanf("%d%d",&A,&B);
    	if(A == 0)	printf("%d %d\n",a[B].x,a[B].y);
    	else
    	{
    		mat gamma;memset(gamma.m,0,sizeof gamma.m);
    		gamma.m[0][0] = a[B].x,gamma.m[0][1] = a[B].y,gamma.m[0][2] = 1;
    		gamma = mul(gamma,op[A],3);
    		printf("%lld %lld\n",gamma.m[0][0],gamma.m[0][1]);
    	}
    }
    return 0;
}

Atcoder ABC 189 DE

原文：https://www.cnblogs.com/HotPants/p/14320191.html