题目
如题。
算法
就是刚学习的插头DP。
从前往后和从后往前分别进行一次DP。
要点
合法的括号序列只有103个
如何合并两次dp的信息
一开始犯傻了，以为当且仅当两个轮廓线的状态相同才是合法的方案。其实很容易举出反例。
如果直接枚举的话，每次询问的时间复杂度是\(O(103^2 m)\)。
为了加快速度，可以把所有合法的方案先列举出来（就是预处理），只有\(103^2\)个。每次询问的复杂度优化为\(O(103^2)\)。
时间复杂度
\(O(103 \cdot n \cdot m + 103^2 * m + 103^2 Q)\)
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long i64;
const int MaxN = 1000;
const int MaxM = 6;
const int MaxS = 103;
const int MOD = (int) 1e9 + 7;
int n, m;
int A[MaxN][MaxM];
#define getbit(s, i) ((s) >> ((i) << 1) & 3)
#define clrbit(s, i) ((s) & ~(3 << ((i) << 1)))
#define clrbit2(s, i, j) (clrbit( clrbit(s, i), j))
#define cpbit(s, i, x) ((s) ^ ((x) << ((i) << 1)))
#define revbit(s, i) ((s) ^ (1 << ((i) << 1)))
template <class T>
void addIt(T &a, const T &b)
{
a += b;
if (a >= MOD) a -= MOD;
}
struct Hash
{
int n;
pair<int, int> A[MaxS];
struct Link
{
int to;
Link *next;
}pool[MaxS], *pool_cur, *info[MaxS];
void sort()
{
std::sort(A, A + n);
}
int find(const int &x)
{
pair<int, int> *p = lower_bound(A, A + n, make_pair(x, -1));
if (p->first == x) return p->second;
return 0;
}
Hash()
{
pool_cur = pool;
}
void update()
{
int i = 0;
while (i < n)
{
if (getbit(A[i].first, m))
A[i] = A[-- n];
else
i ++;
}
}
void push(const int &s, const int &x)
{
int hash = s % MaxS;
for (Link *p = info[hash]; p; p = p->next)
{
if (A[p->to].first == s)
{
addIt(A[p->to].second, x);
return;
}
}
pool_cur->to = n;
pool_cur->next = info[hash];
info[hash] = pool_cur ++;
A[n ++] = make_pair(s, x);
}
}dp[2][MaxN + 1][MaxM];
int getbracket0(const int &s, const int &i)
{
int cnt = 1;
for (int k = i + 1; k < m; k ++)
{
int t = getbit(s, k);
if (t)
{
if (t & 1) cnt --;
else cnt ++;
}
if (!cnt) return k;
}
return -1;
}
int getbracket1(const int &s, const int &i)
{
int cnt = -1;
for (int k = i - 1; k >= 0; k --)
{
int t = getbit(s, k);
if (t)
{
if (t & 1) cnt --;
else cnt ++;
}
if (! cnt) return k;
}
return -1;
}
void Process(Hash (*dp)[MaxM])
{
dp[0][0].push(0, 1);
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
{
Hash &cur = dp[i][j], &next = j == m - 1 ? dp[i + 1][0] : dp[i][j + 1];
for (int k = 0; k < cur.n; k ++)
{
int s = cur.A[k].first;
int x = cur.A[k].second;
int L = getbit(s, m);
int U = getbit(s, j);
#define send(st) next.push(st, x)
if (!A[i][j])
{
if (L && U)
{
L &= 1, U &= 1;
if (!L && !U)
send(revbit( clrbit2(s, j, m), getbracket0(s, j)));
else if (L && !U)
send(clrbit2(s, j, m));
else if (L && U)
send(revbit( clrbit2(s, j, m), getbracket1(s, j)));
}
else if (L)
{
send(s);
send(clrbit( cpbit(s, j, L), m));
}
else if (U)
{
send(s);
send(clrbit( cpbit(s, m, U), j));
}
else
{
send(s);
send(cpbit( cpbit(s, j, 2), m, 3));
}
}
else if (!L && !U)
send(s);
}
cerr << next.n << endl;
if (j == m - 1) next.update();
}
}
}
int P[729], Pn; // 3^m
int Qn;
pair<int, int> Q[729 * 729];
void dfs(int i, int cnt, int s)
{
if (i == m)
{
if (! cnt && s)
{
P[Pn ++] = s;
}
}
else
{
dfs(i + 1, cnt + 1, s ^ (2 << (i << 1)));
if (cnt)
dfs(i + 1, cnt - 1, s ^ (3 << (i << 1)));
dfs(i + 1, cnt, s);
}
}
int getbracket(const int &a, const int &j)
{
if (getbit(a, j) & 1)
{
int cnt = -1;
for (int i = j - 1; i >= 0; i --)
{
int t = getbit(a, i);
if (t)
{
if (t & 1) cnt --;
else cnt ++;
if (! cnt) return i;
}
}
}
else
{
int cnt = 1;
for (int i = j + 1; i < m; i ++)
{
int t = getbit(a, i);
if (t)
{
if (t & 1) cnt --;
else cnt ++;
if (! cnt) return i;
}
}
}
return -1;
}
bool eliminate(int &a, int at, int &b, const int &start)
{
if (getbit(a, at) == 0) return at == start;
int other = getbracket(a, at);
a = clrbit2(a, at, other);
if (!eliminate(b, other, a, start)) return false;
return true;
}
bool check(int a, int b)
{
for (int i = 0; i < n; i ++)
if (getbit(a, i))
{
if (! eliminate(a, i, b, i)) return false;
return a == 0 && b == 0;
}
return false;
}
int main()
{
int k;
scanf("%d%d", &n, &m);
scanf("%d", &k);
while (k --)
{
int x, y;
scanf("%d%d", &x, &y);
x --, y --;
A[x][y] = 1;
}
Process(dp[0]);
for (int i = 0; i < n >> 1; i ++)
{
int j = n - i - 1;
for (int k = 0; k < m; k ++)
swap(A[i][k], A[j][k]);
}
Process(dp[1]);
dfs(0, 0, 0);
for (int i = 0; i < Pn; i ++)
for (int j = 0; j < Pn; j ++)
{
if (check(P[i], P[j]))
{
Q[Qn ++] = make_pair(P[i], P[j]);
}
}
scanf("%d", &k);
for (int i = 0; i < n; i ++)
{
dp[0][i][0].sort();
dp[1][i][0].sort();
}
while (k --)
{
int x, y;
scanf("%d%d", &x, &y);
x --, y --;
int ans = 0;
for (int i = 0; i < Qn; i ++)
{
if (getbit(Q[i].first, y))
{
addIt(ans, (int) ((i64) dp[0][x + 1][0].find(Q[i].first) *
dp[1][n - x - 1][0].find(Q[i].second) % MOD));
}
}
printf("%d\n", ans);
}
return 0;
}