吉安永新哪里做网站,互联网创业项目零成本,做网站维护学什么编程语言,淘宝网站页面设计假设三种颜色的边都存在#xff0c;并且不存在这样的路径
首先观察到#xff0c;对于一个简单环上的边#xff0c;颜色一定相同
因此#xff0c;考虑建立圆方树#xff0c;问题转化为圆方树上的 D P DP DP问题。限制是对于方点所连接的边#xff0c;必须涂上相同的颜色…假设三种颜色的边都存在并且不存在这样的路径
首先观察到对于一个简单环上的边颜色一定相同
因此考虑建立圆方树问题转化为圆方树上的 D P DP DP问题。限制是对于方点所连接的边必须涂上相同的颜色也就是不存在一条路径上有三种颜色的方点
注意到如果有两个相邻的颜色不同的方点那么其对应的子树内的方点一定只有一种颜色。又因为三种颜色的方点都出现过因此将圆点删除后剩下的连通块内方点也一定只有一种颜色。考虑到圆方树的性质只有方点和圆点有边相连因此枚举这个圆点并统计答案即可。
需要注意的是当 n ≤ 4 n\le 4 n≤4时需要暴搜解决。这是因为环上会出现反例。同理对于大小为 3 3 3的点双也要特判环上的点颜色互不相同出边只有一条其他边的颜色都和环上某一条边的颜色相同。
复杂度 O ( n m ) O(nm) O(nm)。 remark \text{remark} remark 对于圆方树上的 D P DP DP问题分析性质有时候比设计状态更重要。
#includebits/stdc.h
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f
using namespace std;
const int mod998244353;
const int N2e55;
int n,m,cnt;
int dfn[N],low[N],du[N],num;
vectorintG[N];
stackints;
ll res;
ll fpow(ll x,ll ymod-2){ll z(1);for(;y;y1){if(y1)zz*x%mod;xx*x%mod;}return z;
}
vectorintvec[N];
void tarjan(int u){dfn[u]low[u]num,s.push(u);for(auto v:G[u]){if(!dfn[v]){tarjan(v),low[u]min(low[u],low[v]);if(low[v]dfn[u]){int tmp0;du[u],cnt;do{tmps.top(),s.pop();du[tmp],vec[cnt].pb(tmp);}while(tmp!v);vec[cnt].pb(u);}}else low[u]min(low[u],dfn[v]);}
}
void add(ll x,ll y){x(xy)%mod;
}
vectorpairint,intedge;
int w[10][10],p[10];
void dfs(int x){if(xm){int ok0;for(int i1;in;i)p[i]i;do{int sz0;for(int i2;in;i){if(~w[p[i]][p[i-1]]){sz|1w[p[i]][p[i-1]]-1;if(sz7)break;}else break;}if(sz7){ok1;break;}}while(next_permutation(p1,p1n));resok;return;}int uedge[x].fi,vedge[x].se;for(int i1;i3;i){w[u][v]w[v][u]i,dfs(x1);}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnm;for(int i1;im;i){int x,y;cinxy;G[x].pb(y),G[y].pb(x),edge.pb({x,y});}if(n3){cout0;return 0;}if(n4){memset(w,-1,sizeof w),dfs(0);coutres;return 0;}for(int i1;in;i)if(!dfn[i])tarjan(i);res(fpow(3,m)-3*fpow(2,m)3)%mod;for(int i1;in;i){if(du[i]3){add(res,-fpow(3,du[i])3*fpow(2,du[i])-3);}}for(int i1;icnt;i){if(vec[i].size()3){int tot0;for(auto e:vec[i])if(du[e]1)tot;if(tot1)add(res,-6);}}cout(resmod)%mod;
}
