解析表达式语法
解析表达式语法[ made by Ameiyo ]
A: CF778B - Bitwise Formula B: CF552E - Vanya and Brackets C: CF39A - C*++ Calculations D: CF89B - Widget Library E: CF7E - Defining Macros F: CF217C - Formurosa G: CF172E - BHTML+BCSS H: CF115D - Unambiguous Arithmetic Expression I: CF582E - Boolean Function A每一位都是独立的,对每一位单独考虑。枚举问号是 0 或 1,按顺序模拟得到两个情况下 1 的个数,分情况给两个答案赋值即可。 重点还是在模拟。 #include <cstdio> #include <cctype> #include <map> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define reg register #define rep(i,a,b) for (reg int i = (a),i##end = (b); i <= i##end; ++i) #define dep(i,i##end = (b); i >= i##end; --i) template <typename _typer> inline _typer read() { _typer init = 0; char ch = getchar(),k = 0; for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-'); for ( ; isdigit(ch); ch = getchar()) init = (init << 3) + (init << 1) + (ch ^ 48); return k ? -init : init; } const ll N = 5005,INF = 1e9; const ll M = 1005; /******************************************************************************* * * 按位枚举每一位,让每一位的 1 最少/多 * ******************************************************************************/ int n,m; int val[N][M],Ansmin[M],Ansmax[M]; int opt[N],a[N],b[N]; // ? - 0 map < string,int > mp; int Query(int id,int vl) { val[0][id] = vl; int cnt = 0; rep (i,1,n) if (opt[i] != -1) { if (opt[i] == 0) val[i][id] = val[a[i]][id] & val[b[i]][id]; else if (opt[i] == 1) val[i][id] = val[a[i]][id] | val[b[i]][id]; else if (opt[i] == 2) val[i][id] = val[a[i]][id] ^ val[b[i]][id]; cnt += val[i][id]; } return cnt; } void Solve() { rep (i,m) { int cnt0 = Query(i,0),cnt1 = Query(i,1); // cerr << i << " " << cnt0 << " " << cnt1 << endl; if (cnt0 < cnt1) Ansmin[i] = 0,Ansmax[i] = 1; else if (cnt0 > cnt1) Ansmin[i] = 1,Ansmax[i] = 0; else Ansmin[i] = Ansmax[i] = 0; } } int main() { n = read<int>(),m = read<int>(); string name,name1,nameopt,name2; rep (i,n) { cin >> name; mp[name] = i; cin >> name >> name1; if (isdigit(name1[0])) { opt[i] = -1; rep (j,m) val[i][j] = (name1[j - 1] ^ 48); continue; } cin >> nameopt >> name2; if (nameopt == "AND") opt[i] = 0; else if (nameopt == "OR") opt[i] = 1; else if (nameopt == "XOR") opt[i] = 2; if (name1 == "?") a[i] = 0; else a[i] = mp[name1]; if (name2 == "?") b[i] = 0; else b[i] = mp[name2]; } Solve(); rep (i,m) printf("%d",Ansmin[i]); puts(""); rep (i,Ansmax[i]); puts(""); return 0; } B首先括号肯定是加在两个乘号之间才能使答案更大,枚举这个区间,然后就是一遍只有两个符号的模拟了。 #include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define reg register #define rep(i,INF = 1e9; /******************************************************************************* * * 枚举两个 * 号,把他们中间的括起来 * 开头和结尾可以加哨兵 * ******************************************************************************/ int n; char s[N]; int id[N],tot; ll Stk[N << 1],Top; ll Solve(int l,int r) { int cnt = 0; Top = 0; rep (i,n) { if (i == l + 1) { Stk[++Top] = -1; } if (s[i] == '*') Stk[++Top] = -2; else if (s[i] == '+') ++cnt; else { Stk[++Top] = (s[i] ^ 48); } if (i == r - 1) { for ( ; Stk[Top - 1] != -1 && Top && cnt; --Top,--cnt) Stk[Top - 1] = Stk[Top - 1] + Stk[Top]; Stk[Top - 1] = Stk[Top],--Top; } if (Stk[Top - 1] == -2 && Stk[Top] >= 0) Stk[Top - 2] = Stk[Top - 2] * Stk[Top],Top -= 2; } for ( ; Top && cnt; --Top,--cnt) Stk[Top - 1] = Stk[Top - 1] + Stk[Top]; // cerr << l << " " << r << " " << Stk[1] << endl; return Stk[1]; } int main() { scanf("%s",s + 1); n = strlen(s + 1); id[tot = 1] = 0; rep (i,n) if (s[i] == '*') id[++tot] = i; id[++tot] = n + 1; ll Ans = 0; rep (i,tot) rep (j,i + 1,tot) Ans = max(Ans,Solve(id[i],id[j])); printf("%lldn",Ans); return 0; } C把所有的 注意提取的时候前面的两个 #include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define reg register #define rep(i,k = 0; for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-'); for ( ; isdigit(ch); ch = getchar()) init = (init << 3) + (init << 1) + (ch ^ 48); return k ? -init : init; } const ll N = 10005,INF = 1e9; /******************************************************************************* * * 把单独的 a 变成系数为 1 的乘法 * 所有的乘法按照系数从小到大计算(有负数) * ******************************************************************************/ #define int ll int a,n,mark[N]; char s[N]; int tot; struct NODE { int mul,opt; inline int operator < (const NODE &__) const { return mul < __.mul; } } node[N]; int Solve() { sort(node + 1,node + tot + 1); int ans = 0; rep (i,tot) { if (node[i].opt == 0) ++a; ans += node[i].mul * a; if (node[i].opt == 1) ++a; } return ans; } signed main() { a = read<int>(); scanf("%s",s + 1); n = strlen(s + 1); rep (i,n) if (s[i] == 'a') { ++tot; if (s[i - 1] == '+' && s[i - 2] == '+' && !mark[i - 2]) { node[tot].opt = 0; mark[i] = mark[i - 1] = mark[i - 2] = true; if (s[i - 3] != '*') { node[tot].mul = (s[i - 3] == '-' ? -1 : 1); continue; } int cur = i - 4,k = 1,init = 0; for ( ; cur > 0 && isdigit(s[cur]); --cur) ; if (s[cur] == '-') k = -1; rep (j,cur + 1,i - 4) init = init * 10 + (s[j] - '0'); node[tot].mul = init * k; } else if (s[i + 1] == '+' && s[i + 2] == '+') { node[tot].opt = 1; mark[i] = mark[i + 1] = mark[i + 2] = true; if (s[i - 1] != '*') { node[tot].mul = (s[i - 1] == '-' ? -1 : 1); continue; } int cur = i - 2,i - 2) init = init * 10 + (s[j] - '0'); node[tot].mul = init * k; } } printf("%lldn",Solve()); return 0; } D其实题目就是这个意思 Widget [name] ([x],[y]) 宽 x,高 y,名字 name HBox [name] 创建横向打包器 VBox [name] 创建纵向打包器 [name1].pack([name2]) 把 name2 丢到 name1 里 [name].set_border([x]) 设置 border [name].set_spacing([x]) 设置 spacing HBox: 2 * border + (cnt - 1) * spacing + Sigma(Width) 2 * border + max(Height) VBox: 2 * border + max(Width) 2 * border + (cnt - 1) * spacing + Sigma(Height) 最后两组式子可以通过试样例试出来。 然后就是模拟。注意所有的变量都会随时改变,所以要建出一个关系最后更新一遍。 #include <cstdio> #include <cctype> #include <map> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define reg register #define rep(i,k = 0; for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-'); for ( ; isdigit(ch); ch = getchar()) init = (init << 3) + (init << 1) + (ch ^ 48); return k ? -init : init; } const ll N = 105,INF = 1e9; /******************************************************************************* * * 大模拟 * ******************************************************************************/ int n,In[N]; struct EDGE { int to,nex; } edge[N]; int head[N],cntedge; void Addedge(int u,int v) { edge[++cntedge] = (EDGE) { v,head[u] }; head[u] = cntedge,++In[v]; } map < string,int > mp; string name[N]; int tot; struct Widget { char opt; int cnt; ll border,spacing; ll SumWson,SumHson; ll MaxWson,MaxHson; ll Width,Height; void Calc() { if (opt == 'W') return ; if (!cnt) return (void) (Width = Height = 0); if (opt == 'H') { Width = 2 * border + (cnt - 1) * spacing + SumWson; Height = 2 * border + MaxHson; } else if (opt == 'V') { Width = 2 * border + MaxWson; Height = 2 * border + (cnt - 1) * spacing + SumHson; } } void Pushup(const Widget son) { ++cnt; SumWson += son.Width; SumHson += son.Height; MaxWson = max(MaxWson,son.Width); MaxHson = max(MaxHson,son.Height); Calc(); } void SetBorder(ll x) { border = x; } void SetSpacing(ll x) { spacing = x; } } node[N]; void Widget() { string s; cin >> s; int len = s.length(),id = 0; string name = ""; rep (i,len - 1) { if (s[i] == '(') { id = i; break; } name += s[i]; } ::name[mp[name] = ++tot] = name; int x = 0,y = 0; rep (i,id + 1,len - 1) { if (s[i] == ',') { id = i; break; } x = x * 10 + s[i] - '0'; } rep (i,len - 1) { if (s[i] == ')') { id = i; break; } y = y * 10 + s[i] - '0'; } node[tot].Width = x,node[tot].Height = y; node[tot].opt = 'W'; // cerr << name << " " << node[tot].Width << " " << node[tot].Height << endl; } void HBox() { string name; cin >> name; ::name[mp[name] = ++tot] = name; node[tot].opt = 'H'; } void VBox() { string name; cin >> name; ::name[mp[name] = ++tot] = name; node[tot].opt = 'V'; } void Set(string s) { string name = "",ord = ""; int len = s.length(),id; rep (i,len - 1) { if (s[i] == '.') { id = i; break; } name += s[i]; } int idv = mp[name]; rep (i,len - 1) { if (s[i] == '(') { id = i; break; } ord += s[i]; } if (ord == "pack") { name = ""; rep (i,len - 1) { if (s[i] == ')') { id = i; break; } name += s[i]; } int idu = mp[name]; Addedge(idu,idv); } else { int x = 0; rep (i,len - 1) { if (s[i] == ')') { id = i; break; } x = x * 10 + s[i] - '0'; } if (ord == "set_border") node[idv].border = x; else if (ord == "set_spacing") node[idv].spacing = x; } } void Solve() { int Q[N],l,r; l = r = 0; rep (i,tot) if (!In[i]) Q[++r] = i; while (l < r) { int u = Q[++l]; for (int i = head[u],v; i; i = edge[i].nex) { v = edge[i].to; node[v].Pushup(node[u]); if (!(--In[v])) Q[++r] = v; } } } int main() { n = read<int>(); rep (i,n) { string order; cin >> order; if (order == "Widget") Widget(); else if (order == "HBox") HBox(); else if (order == "VBox") VBox(); else Set(order); } Solve(); sort(name + 1,name + tot + 1); rep (i,tot) cout << name[i] << " " << node[mp[name[i]]].Width << " " << node[mp[name[i]]].Height << endl; return 0; } E其实也是模拟,但是有一些性质。 下面定义不安全为
每个宏有三个变量,分别表示 在输入的时候依次处理出每个宏,最后对输入做一次相同的判断得到是否合法。 一种比较简单粗暴的方法是把整个式子中缀转后缀,然后直接暴力搞,因为只有符号 + 宏会引起歧义。 但是这样的话不安全就只能在最外层判,因为转后缀后就不清楚是否有括号。 这样打代码比较长,但是基本没有思维难度。 #include <cstdio> #include <cctype> #include <map> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define reg register #define rep(i,INF = 1e9; const ll M = 1005; int tot; struct NODE { int save,opr,dop; } node[N]; string name[N]; map < string,int > mp; map < int,int > dep; int OPRTPINT[M],Opr[] = { '+','-','*','/' }; int chkOpr(char ch) { rep (i,3) if (Opr[i] == ch) return true; return false; } int n,debug; string getName(string &s,int &cur,int len) { string name = ""; rep (i,cur,len - 1) { if (!isdigit(s[i]) && !isalpha(s[i])) { cur = i - 1; break; } name += s[i]; if (i == len - 1) cur = len; } return name; } int cntele,cntli,cntnbl,Top; NODE ele[M],Stk[M]; int li[M],nbl[M],stk[M]; int Change(int l,int r) { if (li[l + 1] == -6 && li[l] >= 0) { int id = li[l]; nbl[++cntnbl] = id; ele[id].opr = ele[id].dop = false; return l + 1; } int id = l; rep (i,r) { id = i; if (li[i] == -6) break; if (li[i] >= 0) { nbl[++cntnbl] = li[i]; continue; } if (li[i] == -5) { i = Change(i + 1,r); continue; } while (Top && stk[Top] >= l && dep[li[stk[Top]]] >= dep[li[i]]) nbl[++cntnbl] = li[stk[Top]],--Top; stk[++Top] = i; } while (Top && stk[Top] >= l) nbl[++cntnbl] = li[stk[Top]],--Top; return id; } NODE Get(NODE A,NODE B,int opr) { NODE Ans; Ans.save = A.save & B.save; if (opr == -1 && B.opr) Ans.save = false; if (opr == -3 && B.dop) Ans.save = false; if (opr == -2 || opr == -1) { if (A.dop || B.dop) Ans.save = false; } Ans.opr = Ans.dop = false; return Ans; } void CheckLi(int num) { Top = 0; Change(1,cntli); Top = 0; rep (i,cntnbl) { if (nbl[i] > 0) Stk[++Top] = ele[nbl[i]]; else Stk[Top - 1] = Get(Stk[Top - 1],Stk[Top],nbl[i]),--Top; } node[num] = Stk[1]; } int isch(char ch) { return isdigit(ch) || isalpha(ch); } void Get(string s,int num) { cntli = cntnbl = cntele = 0; int len = s.length(),id = -1,flag = false; string now = ""; rep (i,len - 1) if (s[i] != ' ') now += s[i]; swap(now,s); len = s.length(); if (s[0] == '(') { int cnt = 0; rep (i,len - 1) { if (s[i] == '(') ++cnt; else if (s[i] == ')') { if (cnt) --cnt; else if (i == len - 1) flag = true; } } if (flag) { now = "",id = -1; rep (i,len - 2) now += s[i]; swap(now,s); len = s.length(); } } for (int i = 0; i < len; ++i) { if (isch(s[i])) { string name = getName(s,i,len); if (mp.count(name)) id = mp[name]; else id = 0; li[++cntli] = ++cntele; ele[cntele] = node[id]; } else li[++cntli] = OPRTPINT[(int) s[i]]; } CheckLi(num); int cnt = 0; rep (i,cntli) { if (li[i] == ')') --cnt; else if (li[i] == '(') ++cnt; if (cnt) continue; if (li[i] > -5 && li[i] < 0) node[num].opr = true; if (li[i] > -5 && li[i] < -2) node[num].dop = true; } if (flag) node[num].opr = node[num].dop = false; } int main() { node[0].save = true; rep (i,3) OPRTPINT[Opr[i]] = i - 4; OPRTPINT[(int) '('] = -5,OPRTPINT[(int) ')'] = -6; dep[-1] = dep[-2] = 2,dep[-3] = dep[-4] = 1; n = read<int>(); rep (i,n) { string define; cin >> define; if (define == "#") cin >> define; string name; cin >> name; ::name[mp[name] = i] = name; string txt; getline(cin,txt); Get(txt,i); } // rep (i,n) // cerr << node[i].save << " " << node[i].opr << " " << node[i].dop << endl; string txt; getline(cin,txt); Get(txt,n + 1); string Ans = node[n + 1].save ? "OK" : "Suspicious"; cout << Ans << endl; return 0; } F这其实是一道 DP ,一开始思路挺乱的,有点接近正解,但还是差了些。 假设最后的值是 $ f(s) $ , $ s $ 是每个 $ ? $ 的一组取值,那么只要存在一组 $ s $ 与 $ s‘ $ 满足二者至少有一个 $ ? $ 的取值不一样,而且 $ f(s) neq ?f(s‘) $ 我们就可以确定出这个 $ ? $ 在 $ s $ 时的值。 证明:
但是对于异或操作来说,我们可以得知的只有一个表达式的值是否改变,而不是从 $ 0 -> 1 $ 或 $ 1 -> 0 $ ,但如果确定了某一个是 $ 0 / 1 $ ,那么这个值就可以确定了。 所以对于每一组括号,我们 DP 出这组括号的情况:
回到题目,因为两种值都至少存在一个,所以我们就把不同的元素不断的放到那个位置上,直到值的改变,然后确定剩下的值。 然后就有了 $ 27 $ 种转移 ( 3 种值 3 种符号) 。这里提供一种比较简洁的做法,借鉴自 Alex_McAvoy 网友的博客. int Get(int x,int y,int opr) { if (opr == '|') return x | y; else if (opr == '&') return x & y; else if (opr == '^') return x ^ y; return 0; } int Work() { int opr = getchar(); if (opr == '(') { int ls = Work(); int opr = getchar(); int rs = Work(),ans = 0; getchar(); rep (i,3) if (ls & (1 << i)) rep (j,3) if (rs & (1 << j)) ans |= (1 << Get(i,j,opr)); return ans; } else { if (opr == '1') return 8; else if (opr == '0') return 1; else return 6; } } int main() { read<int>(); if (Work() & 6) puts("YES"); else puts("NO"); return 0; } G一开始题目看错淦了好久。。。 简单的说,给出一棵树,对于每个询问输出有多少根到节点的路径满足条件。 一条路径满足条件当且仅当:
那么把树建出来后直接每个询问去跑就行了, Dfs 的参数中把 从根到当前节点 能匹配到的最大下标 传进去就可以了。 #include <cstdio> #include <cctype> #include <map> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define reg register #define rep(i,k = 0; for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-'); for ( ; isdigit(ch); ch = getchar()) init = (init << 3) + (init << 1) + (ch ^ 48); return k ? -init : init; } const ll N = 250005,INF = 1e9; const ll M = 205; string s; int tot,node[N]; struct EDGE { int to,nex; } edge[N << 1]; int head[N],head[u] }; head[u] = cntedge; } map < string,int > mp; int Stk[N],Top; void Get(int &cur,int r) { string tmp = ""; int flagCloseSelf = false,flagClose = false; if (s[cur] == '/') flagClose = true,++cur; rep (i,r) { cur = i; if (s[i] == '>') break; if (s[i] == '/') flagCloseSelf = true; else tmp += s[i]; } // cerr << tmp << " " ; if (flagClose) { --Top; } else { if (mp.count(tmp)) node[++tot] = mp[tmp]; else node[++tot] = 0; // cerr << tot << " " << node[tot] ; Addedge(Stk[Top],tot); if (!flagCloseSelf) Stk[++Top] = tot; } // cerr << endl; } void Change() { int len = s.length(); for (int i = 0; i < len; ++i) { if (s[i] == '<') { int cur = i + 1; Get(cur,len - 1); i = cur; } } } int li[M][M],m,Ans; void Dfs(int u,int *li,int cur) { // cerr << u << " " << node[u] << endl; if (node[u] == li[cur + 1]) ++cur; if (cur == li[0] && node[u] == li[cur]) ++Ans; for (int i = head[u],v; i; i = edge[i].nex) { v = edge[i].to; Dfs(v,li,cur); } } void Work() { rep (ks,m) { Ans = 0; for (int i = head[0],v; i; i = edge[i].nex) { v = edge[i].to; Dfs(v,li[ks],0); } printf("%dn",Ans); } } int main() { cin.tie(0); ios::sync_with_stdio(false); int cnt = 0; cin >> s >> m; rep (i,m) { string now,tmp; getline(cin,now); while (!now.length()) getline(cin,now); now += ' '; int len = now.length(); rep (j,len - 1) { if (now[j] == ' ') { if (!mp.count(tmp)) mp[tmp] = ++cnt; li[i][++li[i][0]] = mp[tmp]; tmp = ""; continue; } tmp += now[j]; } } Change(); Work(); return 0; } H其实是一个挺简单的 DP ,一开始打 区间 DP T 死我了。 仔细观察题目,可以发现原来多项式的方案数其实就是加括号的方案数。 令 $ f[i][j] $ 表示前 $ i $ 个位置,还有 $ j $ 个左括号没有匹配右括号 的方案数。 考虑两种情况:
由于所有的数字旁边都必须加上一对括号,所以这里并不考虑。 还要判断一些不合法的情况,比如开头有 int main() { cin >> s,len = s.length(); rep (i,len - 1) { if (i && isdigit(s[i]) && isdigit(s[i - 1])) continue;; if (isdigit(s[i])) li[++n] = 1; else if (s[i] == '+' || s[i] == '-') li[++n] = -1; else if (s[i] == '*' || s[i] == '/') li[++n] = -2; } int id = 0,m = 2000; f[0][0] = 1; rep (i,n) if (li[i] < 0) { if (i < n && li[i + 1] == -2) { id = i; continue; } if (li[i] == -2 && i == 1) { id = i; break; } if (i < n && li[i + 1] == 1) { int sum = f[id][m]; dep (j,1) { ((sum += f[id][j - 1]) >= Mod && (sum -= Mod)); f[i][j] = sum; } f[id = i][0] = sum; } else { if (i == n) { id = i; break; } rep (j,m) f[i][j] = f[id][j - 1]; id = i; } } printf("%dn",f[id][0]); return 0; } I首先将表达式转换成表达式树。 令 $ f[u][s] $ 表示 $ u $ 这棵子树中,在 $ n $ 组取值的情况下, $ n $ 组结果为 $ s $ 的方案数。 首先每一位的转移是互不影响的,因为只是把他们放到一起而已,所以 $ s1,s2 $ 与 符号 $ opr $ 所转移到的地方就是 $ s1 ?opr ?s2 $ 。 所以可以先写出一个暴力算法。 #include <cstdio> #include <cctype> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define ll long long #define reg register #define rep(i,k = 0; for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-'); for ( ; isdigit(ch); ch = getchar()) init = (init << 3) + (init << 1) + (ch ^ 48); return k ? -init : init; } const ll N = 505,INF = 1e9; const ll M = (1 << 16),Mod = 1e9 + 7; /******************************************************************************* * * * ******************************************************************************/ int n,tot; int lson[N],rson[N],node[N],f[N][M],ChTpInt[N],cnt[N]; string s; struct NODE { int id,rt; } ; NODE Change(int l,int r) { int u = ++tot,id = l; // cerr << l << " " << r << endl; rep (i,r) { id = i; if (s[i] == '(') { NODE tmp = Change(i + 1,r); if (lson[u]) rson[u] = tmp.rt; else lson[u] = tmp.rt; id = i = tmp.id; continue; } // cerr << s[i] << endl; if (s[i] == ')') break; if (s[i] != '?') { node[u] = s[i]; } else if (s[i + 1] == '(') { // opr - ? node[u] = 1; } else { // num - ? node[u] = 2; } } // cerr << u << " " << node[u] << " " << id << endl; // system("pause"); return (NODE) { id,u }; } int val[N][10],ans[N]; int Get(int x,int ch) { if (ch == '|') return x | y; else if (ch == '&') return x & y; return 0; } void Upd(int &x,int y) { ((x += y) >= Mod && (x -= Mod)); } void Dfs(int u) { // cerr << u << " " << ((node[u] == 1 || node[u] == 2) ? node[u] : (char) node[u]) << endl; if (!u) return ; if (node[u] == 2) { rep (i,8) { int w = 0; rep (j,n) if (val[j][i]) w |= (1 << j >> 1); cnt[u] += (!f[u][w]),++f[u][w]; } } else if (isalpha(node[u])) { int w = 0; rep (j,n) if (val[j][ChTpInt[node[u]]]) w |= (1 << j >> 1); cnt[u] += (!f[u][w]),++f[u][w]; } else { int ls = lson[u],rs = rson[u]; Dfs(ls),Dfs(rs); if (cnt[ls] > cnt[rs]) swap(ls,rs); rep (s1,(1 << n) - 1) if (f[ls][s1]) { rep (s2,(1 << n) - 1) if (f[rs][s2]) { int tmp = 1ll * f[ls][s1] * f[rs][s2] % Mod; if (node[u] == 1) { Upd(f[u][Get(s1,s2,'|')],tmp); Upd(f[u][Get(s1,'&')],tmp); } else Upd(f[u][Get(s1,node[u])],tmp); } } } } int main() { cin >> s; n = read<int>(); rep (i,3) ChTpInt['A' + i] = i + 1,ChTpInt['a' + i] = i + 5; int w = 0; rep (i,n) { rep (d,4) val[i][d + 4] = (val[i][d] = read<int>()) ^ 1; if (read<int>()) w |= (1 << i >> 1); } NODE tmp = Change(0,s.length() - 1); // cerr << "Change end" << endl; Dfs(tmp.rt); printf("%dn",f[tmp.rt][w]); return 0; } 但是这会血 T ,所以要对整个方案进行改进。 先只考虑 我们要统计的是满足 $ s = s1 & s2 $ 的 $ f[ls][s1] * f[rs][s2] $ 的和,因为 $ s = s1 & s2 $ ,所以 $ s $ 肯定是 $ s1,s2 $ 最大公共子集。 令 $ sum[s] $ 表示所有包含 $ s $ 的状态的和, $ tmp[s] $ 表示 那么 $ tmp[s] = sum[ls][s] * sum[rs][s] - sum tmp[s‘] $ ,其中 $ s subset s‘ $ 。 为什么要减去包含 $ s $ 的值?因为包含 $ s $ 的两个数可能还有其他公共部分,那么他们 关于 $ sum $ 数组我们可以用 高维前(后)缀和 简单的解决掉,但是该如何容斥出 $ tmp $ 数组呢? 我直接类似高维前缀和弄了个高维前缀减,尽管并不知道为什么能这么用, 考虑两个状态 $ s,s‘ $ ,其中 $ s subset s‘ $ ,设从 $ s $ 到 $ s‘ $ 需要 $ t $ 步。 因为我们把高维前缀和中的 $ sum[ls][s] * sum[rs][s] $ 的到的结果是包含所有 $ tmp[s‘] (s in s‘) $ 的,所以一开始的值都包含了所有的 "孩子" (在上面的博客中我将包含与不包含定义成了 父子关系)。 对于所有 $ s‘‘ $ 满足 二进制位中 只有 那 $ t $ 位上与 $ s $ 有 $ i $ 位不同(即那 $ i $ 位值为 $ 1 $ ,其他几位和 $ s $ 一模一样) ,会对 $ s‘ $ 贡献 $ s $ , 而每个的贡献是 $ (-1) ^ {t - i} $ ,对于每个 $ i $ 一共有 $ C_{t} ^{i} $ 个这样的数,所以 $ s $ 在 $ s‘ $ 的系数就是 $ sum _{i = 0} ^{t} (C_{t} ^{i} * (-1) ^{t - i}) $ (在更新之前系数是 $ 1 $ )。 那个时候还根本不会算这个东西,今天打题解的时候突然想到了前两天刚看的多项式定理,当然这里只用到了 二项式定理。 二项式定理:
那么当 $ x = 1,c = -1 $ 时,右边就是上面的式子,而值 $ (1 - 1) ^ t = 0 $ ,即最后在 $ tmp[s‘] $ 中不包含 $ tmp[s] $ 。 即证。 还要考虑 所以转换成 void Dfs(int u) { if (!u) return ; memset(f,sizeof f); if (node[u] == 2) { rep (i,n) if (val[j][i]) w |= (1 << j >> 1); ++f[w]; } } else if (isalpha(node[u])) { int w = 0; rep (j,n) if (val[j][ChTpInt[node[u]]]) w |= (1 << j >> 1); ++f[w]; } else { int ls = lson[u],Dfs(rs); dep (s,uplim,0) { tmpS[s] = 1ll * S[ls][s] * S[rs][s] % Mod; tmpC[s] = 1ll * C[ls][s] * C[rs][s] % Mod; } rep (i,n - 1) rep (s,uplim) if (!(s & (1 << i))) { Upd(tmpS[s],Mod - tmpS[s | (1 << i)]); Upd(tmpC[s],Mod - tmpC[s | (1 << i)]); } rep (s,uplim) { if (node[u] == 1) { // | f[s] = tmpC[uplim ^ s]; // & Upd(f[s],tmpS[s]); } else if (node[u] == '|') { f[s] = tmpC[uplim ^ s]; } else if (node[u] == '&') { f[s] = tmpS[s]; } } } rep (s,uplim) S[u][s] = C[u][uplim ^ s] = f[s]; rep (i,uplim) if (!(s & (1 << i))) { Upd(S[u][s],S[u][s | (1 << i)]); Upd(C[u][s],C[u][s | (1 << i)]); } } $ in ?2019.9.27 $ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |