NOIP 2022 游记（题解）
目录更好的阅读体验戳此进入
周五的时候通知考试取消了，改为三月份春测。。就挺突然的。
于是来（假装）VP 一下，看看能做上多少分。
T1 [NOIP2022] 种花
题面
大概就是在有障碍的网格图里分别问能填充多少 C 和 F 形状的图形。严谨地叙述太复杂了，这里就不多叙述，直接去看 洛谷题面 吧。
然后顺便吐槽一下，这不愧是经典的 NOIP T1，感觉和上次的报数差不多，难度有点低了，比 CSP 的 T1 T2 都要简单，可惜考试取消了没考上。
Solution
做完之后翻了一下讨论区，似乎还有一些高妙的悬线法之类的解法，可以很简短地切掉这题。不过我不会我感觉不是很好像，所以这里提供一个思维难度极低，代码略长的做法，比较无脑，但是是妥妥的 $ O(n^2) $。
大概就是手画一下找性质，然后发现，对于 C 型来说，当我们固定其上下两行之后，若最左侧列从上至下都是 $ 0 $，那么这样的方案书就是上端横行向右最大延申的 $ 0 $ 乘上下端延伸的。换句话说，我们就是要枚举确定每个 C 的左侧的竖直的部分，然后把上下两侧可以延伸的乘起来加到方案里。
然后这东西是 $ O(n^3) $ 的，也就是枚举每个点然后再枚举竖直能延申多少。
然后我们发现这东西实际上是可以优化的，也就是说当我们确定一个竖直部分上端点所在行为 $ i $ 的时候，如果这个点竖直向下最长可以延申 $ \xi $，那么我们要的就是行数为 $ [i + 2, i + \xi] $ 之间的所有可能水平延伸的长度之和。
这样的话我们就随便做一个竖直方向上的前缀和即可优化 $ O(n^3) \longrightarrow O(n^2) $，则对于 C 型的就过了。
对于维护最长能延申的距离，随便写一个 deque 即可，也就是双端队列，里面存下标，对于每个值如果为 $ 0 $ 那么直接插进去，如果为 $ 1 $ 那么更新队列里所有的下标的值即可，具体可看代码，很好理解。
然后考虑 F 型，这个需要想一下，发现对于一个确定的 C 型，变成 F 型就是乘上其下端点能够延伸的距离。这个正常做还是 $ O(n^3) $ 的，优化方式也类似，类比之前的方式，维护水平延申长度的时候直接乘上竖直延申长度，然后再做个前缀和即可，具体实现可以参考代码。
Tips：有一些循环能压在一起，会让代码可读性变差这里就不压了。然后因为是 VP 也没打对拍，交上去最后两个点 WA 了，随便写了个满的数据才发现是最后加法没有取模。。。不过这种错误随便拍一下就能调出来，然后这题本身也很好调，思路非常直观，一步一步检查即可。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (ll)(998244353)
template < typename T = int >
inline T read(void);
int N, M, C, F;
bool mp[1100][1100];
int cline[1100][1100];
int srow[1100][1100];
int crow[1100][1100];
int line_x_row[1100][1100];
ll srowF[1100][1100];
ll cntC(0), cntF(0);
int main(){
int T = read(); (void)read();
while(T--){
memset(mp, 0, sizeof mp);
memset(cline, 0, sizeof cline);
memset(srow, 0, sizeof srow);
memset(crow, 0, sizeof crow);
memset(line_x_row, 0, sizeof line_x_row);
memset(srowF, 0, sizeof srowF);
cntC = cntF = 0;
N = read(), M = read(), C = read(), F = read();
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j){
char c = getchar();
while(c != '1' && c != '0')c = getchar();
mp[i][j] = c - '0';
}
for(int i = 1; i <= N; ++i){//i = line, j - row
deque < int > cur;
for(int j = 1; j <= M; ++j)
if(!mp[i][j])cur.emplace_back(j);
else while(!cur.empty())cline[i][cur.front()] = cur.size() - 1, cur.pop_front();
while(!cur.empty())cline[i][cur.front()] = cur.size() - 1, cur.pop_front();
}
// for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)printf("%d%c", cline[i][j], j == M ? '\n' : ' ');
for(int i = 1; i <= M; ++i){//i - row, j - line
deque < int > cur;
for(int j = 1; j <= N; ++j)
if(!mp[j][i])cur.emplace_back(j);
else while(!cur.empty())crow[i][cur.front()] = cur.size() - 1, cur.pop_front();
while(!cur.empty())crow[i][cur.front()] = cur.size() - 1, cur.pop_front();
}
// for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)printf("%d%c", crow[j][i], j == M ? '\n' : ' ');
for(int i = 1; i <= M; ++i)//i - row, j - line
for(int j = 1; j <= N; ++j)
srow[i][j] = srow[i][j - 1] + cline[j][i];
for(int i = 1; i <= M; ++i)
for(int j = 1; j <= N; ++j)
line_x_row[i][j] = crow[i][j] * cline[j][i] % MOD;
for(int i = 1; i <= M; ++i)
for(int j = 1; j <= N; ++j)
srowF[i][j] = (srowF[i][j - 1] + line_x_row[i][j]) % MOD;
for(int i = 1; i <= M; ++i)
for(int j = 1; j <= N - 2; ++j){
if(crow[i][j] < 2)continue;
(cntC += (ll)cline[j][i] * (srow[i][j + crow[i][j]] - srow[i][j + 1]) % MOD) %= MOD;
if(!crow[i][j + 2])continue;
(cntF += (ll)cline[j][i] * (srowF[i][j + crow[i][j]] - srowF[i][j + 1]) % MOD) %= MOD;
}
printf("%lld %lld\n", cntC * C, cntF * F);
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T2 [NOIP2022] 喵了个喵
题面
存在 $ n $ 个栈，给定 $ m $ 张卡牌，每张卡牌有图案 $ a_i $，给定 $ k $，有 $ a_i \in [1, k] $。保证每种图案的卡牌数均为偶数。初始所有栈为空。
你可以进行两种操作：
- 将剩余卡牌中最先的一张插入某个栈，如果此时该栈最上方两张卡牌的图案相同则会被消除。
- 选定两个非空栈，如果这两个栈底卡牌图案相同则这两张卡牌会被消除。
输入保证有解，求一个合法操作方案。
Solution
这道题实际上是可以通过每个部分分来慢慢推出方案的。
首先第一档部分分，对于 $ k = 2n - 2 $，不难想到，我们将一个栈空出来作为备用栈，并保证其它栈里永远最多只有两个卡牌，也就是一个在栈顶一个在栈底，实现上可以把所有可以放卡牌的栈顶和栈底存下来并动态维护，注意要先用栈底再插栈顶。然后顺序遍历所有卡牌。如果当前所有栈中不存在这个颜色，那么找个栈内卡牌数不足 $ 2 $ 的丢进去。如果存在的话，考虑如果其在栈顶，那就把这个卡牌放在对应的栈顶来消除，然后重新将这个位置置为可以放置卡牌。如果在栈底那么将这张卡牌放在备用栈里，然后用操作二将这一对删除即可。
然后考虑后面的 $ k = 2n - 1 $ 的部分分。我们还是按照刚才的思路，保留一个备用栈，然后老样子处理卡牌。显然处理一段时间之后就会出现一个状态，即已经有 $ 2n - 2 $ 个颜色的卡牌被放到了栈里，然后此时又多了个新的栈中不存在的颜色的卡牌。
这时不难想到有如下方案：我们先将这张卡牌搁置，令其颜色为 $ a $，然后继续向后遍历，如果再碰到了颜色为 $ a $ 的直接结束，这里还要注意如果循环结束之后 $ a $ 的两个位置的答案没有被更新，那么需要额外更新一下，即把两个 $ a $ 都塞进备用栈里消除一下。然后考虑过程中碰到的其它颜色的卡牌，显然第一次遇到的时候其一定是在前面的栈中存在的，因为颜色一共就有 $ 2n - 1 $ 个。如果碰到在栈顶的颜色，那么直接将其消除，并且标记这个该颜色的位置为这个位置，如果本次遍历过程中再次碰到这个颜色还要再次把这个颜色放到这个位置上。如果碰到在栈底的颜色，那么这时候考虑当前其对应的栈顶是否已经在本次遍历过程中被删除。我们令这个栈底颜色为 $ b $，栈顶颜色为 $ c $。
如果 $ c $ 被删除的话，那么我们将 $ a $ 放在备用栈里，然后将新的 $ b $ 放到原来的 $ b $ 栈，将其消除，则此时备用栈的位置会多一个栈顶的空位，$ b $ 栈会变空，则我们这时直接将 $ b $ 栈作为新的备用栈即可让状态又变成原来的样子。
如果 $ c $ 依然存在，那么先将 $ a $ 放在 $ b $ 栈里，然后再将新的 $ b $ 放到备用栈里，这样可以将 $ b $ 栈和备用栈栈底的卡牌对应消除掉，此时则 $ b $ 栈又变回两个元素，备用栈又为空。
然后这个时候我们可能会发现一点问题，比如如果有一个实际的结果：$ (2, 1, 3, 1, 1, 1, 1) $（这里记左侧为栈底，右侧为栈顶），但是按照我们的写法实际是变成了 $ (2, 1, 1, 1, 1, 1, 3) $，表面上这些是不同的，但是结果上其都为 $ (2, 1, 3) $。对于剩下的 $ 1 $ 为奇数个的，写一下会发现也是等效的。
思路看起来还是比较简单容易想的，但是这东西实现起来就能感受到恶心了，这里为了方便理解，大概说明一下代码中的部分关键变量名的作用。
对于每个 pair 前者表示栈的索引，后者为栈顶或栈底，$ 1 $ 表示栈底，$ 0 $ 表示栈顶，ans 存的是答案，mp 指的是某个颜色对应的在栈中的位置，stk 存储的是对应位置中存的是什么颜色，mark 是指对应颜色被固定的位置（在遇到 $ a $ 之后遍历的时候使用），unfix 存储的是所有空着的可以使用的栈的位置。
写在后面
建议先做 T3 T4 再做这题
这个应该算是我写过最恶心的题之一了，调代码已经人调麻了。如果是在考场上我绝对部分分一拿就跑路。最开始有个思路然后写了一百多行写完了，调试的过程中发现假掉了。。。然后是参考的 @sssmzy 的思路，上面说的也是这个做法，然后做完就开始阴间调试的过程。最后本地对拍全过然后交上去就 WA，各种找样例各种手动模拟，不知道调了多久才找到问题：备用栈切换的时候 unfix 中可能有剩余的新栈中的空位，需要删除。
然后改来改去的代码可能变得很难看，敬请谅解，并且我的实现也可能不够精细，或许会有更简便的方法和更简便的实现，这里只是提供一个思路。还有个问题就是这个 erase 理论上最坏可能是 $ O(n) $ 的，理论上似乎最坏情况下 $ O(S) $ 次，$ O(nS) $ 似乎理论上能被卡，但是这也是理论上，实际上完全卡不满，基本上是无法被卡掉的，并且本身 $ O(nS) $ 也超的不多，再加上 O2 那基本上就是稳稳过。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template < typename T = int >
inline T read(void);
int N, M, K;
int a[2100000];
namespace Sub1{
struct Ans{int flag; int a, b;};
pair < int, bool > mp[610];
int stk[310][2];
basic_string < pair < int, bool > > unfix;
basic_string < Ans > ans[2100000];
void Make(void){
memset(mp, 0, sizeof mp);
memset(stk, 0, sizeof stk);
for(int i = 1; i <= M; ++i)ans[i].clear(), ans[i].shrink_to_fit();
unfix.clear();
for(int i = N - 1; i >= 1; --i)unfix += {{i, 0}, {i, 1}};
for(int i = 1; i <= M; ++i){
int col(a[i]), cur(N);
if(mp[col].first){
if(mp[col].second){
ans[i] += {Ans{1, cur}, Ans{2, mp[col].first, cur}};
if(stk[mp[col].first][0])
unfix += {mp[col].first, 0},
mp[stk[mp[col].first][0]].second = 1;
else
unfix += {mp[col].first, 1};
stk[mp[col].first][1] = stk[mp[col].first][0];
stk[mp[col].first][0] = 0;
mp[col] = {0, 0};
}
else{
ans[i] += {Ans{1, mp[col].first}};
unfix += mp[col];
stk[mp[col].first][mp[col].second] = 0;
mp[col] = {0, 0};
}
}else{
if(!unfix.empty()){
ans[i] += Ans{1, unfix.back().first};
mp[a[i]] = unfix.back();
stk[mp[col].first][mp[col].second] = col;
unfix.pop_back();
}else{
printf("Error!\n"), exit(1);
}
}
// printf("Finish %d\n", i);
// printf("unfix: ");
// for(auto tmpp : unfix)printf("(%d, %d) ", tmpp.first, tmpp.second ? 1 : 0);
// printf("\n");
// for(int i = 1; i <= 4; ++i)
// printf("mp[%d] = %d, %d\n", i, mp[i].first, mp[i].second ? 1 : 0);
}
ll tot(0);
for(int i = 1; i <= M; ++i)tot += ans[i].size();
printf("%lld\n", tot);
for(int i = 1; i <= M; ++i)
for(auto opt : ans[i])
if(opt.flag == 1)printf("1 %d\n", opt.a);
else printf("2 %d %d\n", opt.a, opt.b);
}
}
namespace Sub2{//1 - down, 0 - up
struct Ans{int flag; int a, b;};
basic_string < Ans > ans[2100000];
pair < int, bool > mp[610];
int cur(N);
basic_string < pair < int, bool > > unfix;
int stk[310][2];
pair < int, bool > mark[610];
void Make(void){
for(int i = 1; i <= M; ++i)ans[i].clear(), ans[i].shrink_to_fit();
memset(mp, 0, sizeof mp);
memset(mark, 0, sizeof mark);
memset(stk, 0, sizeof stk);
cur = N, unfix.clear();
for(int i = N - 1; i >= 1; --i)unfix += {{i, 0}, {i, 1}};
for(int i = 1; i <= M; ++i){
int col = a[i];
if(mp[col].first){
if(mp[col].second){
ans[i] += {Ans{1, cur}, Ans{2, mp[col].first, cur}};
if(stk[mp[col].first][0])
unfix += {mp[col].first, 0},
mp[stk[mp[col].first][0]].second = 1;
else
unfix += {mp[col].first, 1};
stk[mp[col].first][1] = stk[mp[col].first][0];
stk[mp[col].first][0] = 0;
mp[col] = {0, 0};
}
else{
ans[i] += {Ans{1, mp[col].first}};
unfix += mp[col];
stk[mp[col].first][mp[col].second] = 0;
mp[col] = {0, 0};
}
}else{
if(!unfix.empty()){
ans[i] += Ans{1, unfix.back().first};
mp[col] = unfix.back();
stk[mp[col].first][mp[col].second] = col;
unfix.pop_back();
}else{
int nxt;
for(nxt = i + 1; nxt <= M; ++nxt){
if(a[nxt] == col)break;
// if(!ans[nxt].empty())continue;
int ccol(a[nxt]);
if(!mp[ccol].first){
ans[nxt] += Ans{1, mark[ccol].first};
unfix.erase(find(unfix.begin(), unfix.end(), mark[ccol]));
mp[ccol] = mark[ccol];
stk[mp[ccol].first][mp[ccol].second] = ccol;
mark[ccol] = {0, 0};
// if(!unfix.empty()){
// ans[nxt] += Ans{1, unfix.back().first};
// mp[ccol] = unfix.back();
// stk[mp[ccol].first][mp[ccol].second] = ccol;
// unfix.pop_back();
// }else{
// printf("Error\n"), exit(0);
// }
}else{
if(!mp[ccol].second){
mark[ccol] = mp[ccol];
ans[nxt] += Ans{1, mp[ccol].first};
unfix += mp[ccol];
stk[mp[ccol].first][mp[ccol].second] = 0;
mp[ccol] = {0, 0};
}else{
if(stk[mp[ccol].first][0]){
ans[i] += Ans{1, mp[ccol].first};
ans[nxt] += {Ans{1, cur}, Ans{2, mp[ccol].first, cur}};
int stkpos = mp[ccol].first;
mp[stk[mp[ccol].first][0]].second = 1;
mp[col] = {mp[ccol].first, 0};
mp[ccol] = {0, 0};
stk[stkpos][1] = stk[stkpos][0];
stk[stkpos][0] = col;
break;
}else{
stk[mp[ccol].first][0] = 0;
ans[i] += Ans{1, cur};
ans[nxt] += Ans{1, mp[ccol].first};
mp[col] = {cur, 1};
unfix += {cur, 0};
cur = mp[ccol].first;
for(auto it = unfix.begin(); it != unfix.end();)
if(it->first == cur)it = unfix.erase(it);
else advance(it, 1);
stk[mp[ccol].first][1] = 0;
mp[ccol] = {0, 0};
break;
}
}
}
}
if(ans[i].empty()){
ans[i] += Ans{1, cur};
ans[nxt] += Ans{1, cur};
}i = nxt;
}
}
// printf("Finish %d\n", i);
// printf("unfix: ");
// for(auto tmpp : unfix)printf("(%d, %d) ", tmpp.first, tmpp.second ? 1 : 0);
// printf("\n");
// for(int i = 1; i <= 3; ++i)
// printf("mp[%d] = %d, %d\n", i, mp[i].first, mp[i].second ? 1 : 0);
}
ll tot(0);
for(int i = 1; i <= M; ++i)tot += ans[i].size();
printf("%lld\n", tot);
for(int i = 1; i <= M; ++i)
for(auto opt : ans[i])
if(opt.flag == 1)printf("1 %d\n", opt.a);
else printf("2 %d %d\n", opt.a, opt.b);
}
}
int main(){
int T = read();
while(T--){
N = read(), M = read(), K = read();
for(int i = 1; i <= M; ++i)a[i] = read();
if(K == N * 2 - 2)Sub1::Make();
else Sub2::Make();
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T3 [NOIP2022] 建造军营
题面
给定连通图，需要选定至少一个关键点，然后保护至少一条边，被保护的边不会被破坏，需要保证无论破坏哪条边都不会影响关键点之间的连通性。求方案数。
Solution
这题我感觉还是有点难度的，主要是细节很多，如果不是我写的太麻烦了的话，感觉评个紫应该比较合理（不过似乎洛谷上西西弗的题难度评级都偏低一些
首先这个题意读完应该就能想到 Tarjan 边双缩点吧，这个还是很显然的。如果在同一个边双里，那么无论删去这里面的任意哪条边都不会使方案不合法，所以可以直接进行 e-BCC 缩点，这样对于每一个 e-BCC 里，如果设其中的边数为 $ \xi $，点数为 $ \epsilon $，那么只考虑这个 e-BCC 的话，如果不在其中设置关键点（军营）其方案数就是 $ 2^{\xi} $，设置的话就是 $ 2^\xi \times (2^\epsilon - 1) $。
然后同时不难发现因为图本身是连通的，所以进行 e-BCC 缩点之后原图就会变成一棵树，所以此时这个东西就很显然变成了一个 树形DP。或者说就是变成了 $ 12 - 14 $ 的部分分，如果想通了树形 DP，再缩个点之后就直接可以切了。
考虑 DP，不难想到一个很显然的状态，设 $ dp(p, 0/1) $ 表示考虑到点 $ p $ 所在子树，且其子树中是否设置关键点（军营）的合法方案数，且此时必须满足 $ p $ 子树的所有关键节点都和 $ p $ 连通，这个继续讨论下去就会发现如果不这样设定就无法转移了。
考虑转移，对于任意一个 $ p $ 的子节点 $ son $，首先显然有：
\[dp(p, 0) \longleftarrow dp(p, 0) \times dp(son, 0) \times 2 \]然后考虑 $ dp(p, 1) $ 的转移：
- 如果从 $ dp(son, 0) $ 转移，那么这条边（桥）就是可保护也可不保护，且 $ p $ 点必须设为关键点。
- 如果从 $ dp(son, 1) $ 转移，那么则需要考虑，对于 $ p $ 为关键点的，则桥必须被保护。
- 同2，对于 $ p $ 不为关键点的，显然要从前面所有子树转移后的 $ dp(p, 0) $ 转移而来，且此时这个桥也必须被保护，因为我们要保证子树的关键节点和 $ p $ 连通。
同时注意对于这里的转移 $ dp(p, 0/1) $，我们用到的都是上一次的 $ dp(p, 0/1) $，这个东西可以直接类似滚动数组思想写一下，也就是先转移 $ dp(p, 1) $ 然后 $ dp(p, 0) $。
于是我们就发现，这东西假了。。
因为我们漏下了一些情况，再回头考虑我们设置的时候为必须满足 $ p $ 子节点的关键节点都和 $ p $ 连通，但是如果不连通，且除 $ p $ 子树之外的所有节点都非关键节点，那么此时我们这几条从 $ p $ 子树中关键节点到 $ p $ 的边无论是否保护都是合法的，但是我们却忽略了，所以此时要考虑维护一下这个东西。
这个东西我们可以考虑将状态改为 $ dp(p, 0/1/2) $，分别表示考虑 $ p $ 所在子树，子树内没有关键点，或有关键点且要求子树外没有关键点，或有关键点且不要求子树外没有关键点。当然这个东西写起来要多考虑一些东西，所以我们也可以换个思路，直接尝试去补上漏下的。
我们实际上可以在 e-BCC 缩点之后再跑一遍 dfs，维护一下对应子树中的包括被缩掉的所有边的数量，设其为 $ s_p $，（或者给 树形DP 加个返回值记录一下好像也行，不过细节会更多）不失一般性，设根为 $ 1 $，那么当我们维护完 $ dp(p, 1) $ 的时候，我们算漏的方案数似乎就是：$ dp(p, 1) \times 2^{s_1 - s_p} $，也就是子树内设置关键点，子树外不设置关键点，则子树外的所有边都是任意的。然后你会发现这个东西又假了。。
考虑发现如果 $ p \longleftrightarrow fa $ 的边被连上了，那么这个东西已经被 $ dp(fa, 1) $ 给计算过了，这样会重，所以我们钦定 $ p \longleftrightarrow fa $ 的边不选择，即可做到不重不漏，这样最终此处的贡献就是 $ dp(p, 1) \times 2^{s_1 - s_p - 1} $。
然后注意对于根节点时，其不存在我们刚才说的漏下的那些方案，但需要加上一般的答案，也就是 $ dp(1, 1) $。
至此，这道细节巨多的题就做完了。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (ll)(1e9 + 7)
template < typename T = int >
inline T read(void);
struct Edge{
Edge* nxt;
Edge* rev;
int to;
bool vis;
OPNEW;
}ed[4100000];
ROPNEW(ed);
Edge* head[1100000];
Edge* ehead[1100000];
int N, M;
int dfn[1100000], low[1100000], eBCC(0), belong[1100000];
int cnte[1100000], cntv[1100000];
int sume[1100000];
bool inS[1100000];
ll dp[1100000][2];
ll pow2[2100000];
ll ans(0);
void Tarjan(int p = 1){
static stack < int > cur;
static int cdfn(0);
cur.push(p); inS[p] = true;
low[p] = dfn[p] = ++cdfn;
for(auto i = head[p]; i; i = i->nxt){
if(i->vis)continue;
i->vis = i->rev->vis = true;
if(!dfn[SON]){
Tarjan(SON);
low[p] = min(low[p], low[SON]);
if(low[SON] > dfn[p]){
++eBCC;
while(true){
int tp = cur.top(); cur.pop();
belong[tp] = eBCC;
inS[tp] = false;
++cntv[eBCC];
if(tp == SON)break;
}
}
}else if(inS[SON])
low[p] = min(low[p], dfn[SON]);
}
if(p == 1 && !cur.empty()){
++eBCC;
while(true){
int tp = cur.top(); cur.pop();
belong[tp] = eBCC;
inS[tp] = false;
++cntv[eBCC];
if(tp == p)break;
}
}
}
void dfs_edge(int p = 1, int fa = 0){
sume[p] = cnte[p];
for(auto i = ehead[p]; i; i = i->nxt){
if(SON == fa)continue;
dfs_edge(SON, p);
sume[p] += sume[SON] + 1;
}
}
void MakeDP(int p = 1, int fa = 0){
dp[p][0] = pow2[cnte[p]];
dp[p][1] = (pow2[cntv[p]] - 1) * pow2[cnte[p]] % MOD;
for(auto i = ehead[p]; i; i = i->nxt){
if(SON == fa)continue;
MakeDP(SON, p);
dp[p][1] = (dp[p][1] * dp[SON][0] * 2 % MOD + dp[p][1] * dp[SON][1] % MOD + dp[p][0] * dp[SON][1] % MOD) % MOD;
dp[p][0] = dp[p][0] * dp[SON][0] * 2 % MOD;
}(ans += (p == 1 ? dp[p][1] : dp[p][1] * pow2[sume[1] - sume[p] - 1] % MOD)) %= MOD;
}
int main(){
N = read(), M = read();
pow2[0] = 1;
for(int i = 1; i <= 2010000; ++i)pow2[i] = pow2[i - 1] * 2 % MOD;
for(int i = 1; i <= M; ++i){
int s = read(), t = read();
head[s] = new Edge{head[s], npt, t};
head[t] = new Edge{head[t], npt, s};
head[s]->rev = head[t], head[t]->rev = head[s];
}Tarjan();
for(int p = 1; p <= N; ++p)
for(auto i = head[p]; i; i = i->nxt)
if(belong[p] != belong[SON])
ehead[belong[p]] = new Edge{ehead[belong[p]], npt, belong[SON]};
else ++cnte[belong[p]];
for(int i = 1; i <= eBCC; ++i)cnte[i] >>= 1;
dfs_edge();
MakeDP();
printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
ABC补完再继续回来写
T4
题面
Solution
Code
UPD
update-2022__ 初稿
标签：NOIP,int,题解,void,卡牌,SON,2022,dp,define From： https://www.cnblogs.com/tsawke/p/16945789.html