题面

$1\le n\le 10^5,1\le a_i,b_i\le 2n$ ，方案数对 $998244353$ 取模。

题解

这种看起来很炫打暴力只有指数算法的题，一般图论解决。

我们把所有 $a_i,b_i$ 之间连一条无向边，题意转化成每条边唯一配对一个端点，配对两个端点有不同的代价，问最小的代价以及此时的方案数。

我们对每个极大连通块讨论，如果该连通块边数大于点数，那么一定无解，输出两个 -1 程序结束。

否则，就是树或基环树。

基环树可以讨论环边的配对方向，剩下的枝杈配对方向也就确定了，整个基环树两种方案，暴力计算贡献比较。

树中确定不被配对的那个点的位置，方案就能被唯一确定，一共(树大小)种方案，每种方案的贡献用换根 DP 解决。

时间复杂度 $O(n)$ 。

CODE

建虚点代表一条边，选不同端点的贡献就可以直接变成边权，估计会好打一些。

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 300005
#define LL long long
#define ULL unsigned long long
#define DB double
#define lowbit(x) (-(x) & (x))
#define ENDL putchar('\n')
#define FI first
#define SE second
int xchar() {static const int maxn = 1000000;static char b[maxn];static int pos = 0,len = 0;if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);if(pos == len) return -1;return b[pos ++];
}
//#define getchar xchar
LL read() {LL f=1,x=0;int s = getchar(); while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}while(s >= '0' && s <= '9') {x = (x<<3) + (x<<1) + (s^48); s = getchar();}return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar('0'+(x%10));}
void putnum(LL x) {if(!x) {putchar('0');return ;}if(x<0) {putchar('-');x = -x;}return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}const int MOD = 998244353;
int n,m,s,o,k;
int hd[MAXN],v[MAXN<<2],nx[MAXN<<2],w[MAXN<<2],cne;
void ins(int x,int y,int z) {nx[++ cne] = hd[x]; v[cne] = y; hd[x] = cne; w[cne] = z;
}
bool f[MAXN],vs[MAXN];
int q[MAXN],cnq,cn1,cn2,pa,pb;
void dfs0(int x,int ff) {vs[x] = 1;q[++ cnq] = x;if(f[x]) cn2 ++;else cn1 ++;for(int i = hd[x];i;i = nx[i]) {int y = v[i];if(y != ff) {if(vs[y]) pa = x,pb = y;else dfs0(y,x);}}return ;
}
int ans = 0;
void dfs1(int x) {vs[x] = 1;for(int i = hd[x];i;i = nx[i]) {if(!vs[v[i]]) {if(f[x]) ans += w[i];dfs1(v[i]);}}return ;
}
int dp1[MAXN],dp2[MAXN],fe[MAXN];
void dfs(int x,int ff) {dp1[x] = dp2[x] = 0;for(int i = hd[x];i;i = nx[i]) {int y = v[i];if(y != ff) {fe[y] = w[i];dfs(y,x);if(f[x]) {dp1[x] += dp1[y] + w[i];}else {dp1[x] += dp1[y];}}}return ;
}
void dfs2(int x,int ff) {if(ff) {if(f[x]) {dp2[x] = (dp2[ff] + dp1[ff] - dp1[x]) + fe[x];}else {dp2[x] = dp2[ff];}}for(int i = hd[x];i;i = nx[i]) {if(v[i] != ff) {dfs2(v[i],x);}}return ;
}
int main() {freopen("card.in","r",stdin);freopen("card.out","w",stdout);m = read();n = m*3;for(int i = 1;i <= m;i ++) f[(m<<1)+i] = 1;for(int i = 1;i <= m;i ++) {s = read();o = read();k = (m<<1) + i;ins(s,k,0); ins(k,s,0);ins(o,k,1); ins(k,o,1);}int as = 0,as2 = 1;for(int i = 1;i <= n;i ++) {if(!vs[i]) {cnq = cn1 = cn2 = 0;dfs0(i,0);if(cn2 > cn1) {printf("-1 -1\n");return 0;}if(cn2 == cn1) {int cen = (f[pa] ? pa:pb);int A = hd[cen],B = nx[A];int ct1 = 0,ct2 = 0;for(int j = 1;j <= cnq;j ++) vs[q[j]] = 0;ans = w[A]; vs[cen] = 1; dfs1(v[A]); ct1 = ans;for(int j = 1;j <= cnq;j ++) vs[q[j]] = 0;ans = w[B]; vs[cen] = 1; dfs1(v[B]); ct2 = ans;as += min(ct1,ct2);if(ct1 == ct2) as2 = as2 *2ll % MOD;}else {int rt = 0;int mn = 0x3f3f3f3f,ct = 0;for(int j = 1;j <= cnq;j ++) {if(!f[q[j]]) {rt = q[j]; break;}}dfs(rt,0); dfs2(rt,0);for(int j = 1;j <= cnq;j ++) {if(!f[q[j]]) {if(dp1[q[j]] + dp2[q[j]] < mn) {mn = dp1[q[j]] + dp2[q[j]];ct = 1;}else if(dp1[q[j]] + dp2[q[j]] == mn) {ct ++;}}}as += mn; as2 = as2 *1ll* ct % MOD;}}}AIput(as,' '); AIput(as2,'\n');return 0;
}