因为是哈密顿回路,所以每个点度数为2
假设我们已经考虑了i个点,其中b个B,w个W。
若存在x条由{1,2,...n}连向{i+1,...2n},
那么{1...n}内部的连边数为(2*i-x)/2
而只有不同颜色的点会连边,故(2*i-x)/2<=2*min(w,b)
x>=2(w+b)-4min(w,b)=2|w-b|
则x>=2max(1,|w-b|).
为了求得最短路,我们肯定希望x尽可能的小。而通过归纳法可以证明,这个下界一定可以取到。(虽然我不会证)(这真的需要大胆假设)
于是,我们观察取到下界时的性质。设fi 为考虑i个点的方案数
若w=b,则无论接下来是什么,都只有一种连接方法
若w>b
若si+1=W,那么只能新开一条路径,因此f【i】=f【i-1】
若si+1=B
若w=b+1,这个B可以接在左右两侧,故f【i】=2*f【i-1】
若w>b+1,那么就会有w-b条形如WBWBWBW的单独的回路,那么把B放入其中一条,再从剩下的(w-b-1)的回路中选择一条,接到B上,故f【i+1】=(w-b)(w-b-w)*f[i].
若w<b,对称过来即可。
直接递推,O(n)的复杂度
但是,我们在统计的时候,把
W1-->B-->W2
W1<--B<--W2
W2-->B-->W1
W2<--B<--W1
算成了4种,而实际上这只能算一种。
因此最后的答案为f【2n】/4 (还需注意除法取模)
(判断时的逻辑关系不能搞混)
所以,边权唯一的用处就是告诉我们要让x尽可能小。。。。。。
细节见代码
// ubsan: undefined // accoders #include <bits/stdc++.h> using namespace std; #define int long long typedef long long ll; const int N = 1e7 + 666; const int mod = 998244353; int w, b, T, n; ll f[N]; char c; signed main() { freopen("path.in", "r", stdin); freopen("path.out", "w", stdout); cin >> T; while (T--) { cin >> n; n <<= 1; w = 0; b = 0; f[0] = 1; /*for(int i=1;i<=1;i++){ cin>>c; if(c=='W') w++; else b++; }*/ f[0] = 1; for (int i = 1; i <= n; i++) { cin >> c; if (w == b) { f[i] = f[i - 1]; } else if ((c == 'W') == (w > b)) f[i] = f[i - 1]; else if (w == b + 1 || b == w + 1) { f[i] = f[i - 1] * 2 % mod; } else if (w > b) { if (c == 'W') f[i] = f[i - 1]; else f[i] = f[i - 1] * (w - b) % mod * (w - b - 1) % mod; } else { if (c == 'B') f[i] = f[i - 1]; else f[i] = f[i - 1] * (b - w) % mod * (b - w - 1) % mod; } if (c == 'W') w++; else b++; // cout<<i<<" "<<w<<" "<<b<<" "<<f[i]<<endl; } // cout<<f[n]*2%mod<<endl; // cout<<f[n]<<" "; printf("%lld\n", 1ll * f[n] * (mod / 2 + 1) % mod * (mod / 2 + 1) % mod); } return 0; }View Code
标签:哈密顿,--,++,long,else,条数,int,6.20,mod From: https://www.cnblogs.com/DongPD/p/17494019.html