网站建设项目经历,短视频运营基础知识,重庆网站搭建哪里可以做,wordpress 网址正题
题目链接:https://www.luogu.com.cn/problem/P6846 题目大意
给出nnn个点mmm条边的一张有向图#xff0c;保证两个点之间最多只有一条边。现在你可以取反一些边使得图变为一张DAGDAGDAG#xff0c;求所有方案的取反的边数和。 1≤n≤181\leq n\leq 181≤n≤18 解题思路…正题
题目链接:https://www.luogu.com.cn/problem/P6846 题目大意
给出nnn个点mmm条边的一张有向图保证两个点之间最多只有一条边。现在你可以取反一些边使得图变为一张DAGDAGDAG求所有方案的取反的边数和。
1≤n≤181\leq n\leq 181≤n≤18 解题思路
考虑到对于一种方案取反所有边就是另一种方案所以每种方案的取反边数的平均值肯定是m2\frac{m}{2}2m所以我们只需要统计方案数就好了。
然后再考虑dpdpdp朴素的做法是O(3n)O(3^n)O(3n)的记GSG_SGS表示集合SSS是否是独立集那么有 FS∑T⊆S(−1)∣T∣1FS−TGTF_S\sum_{T\sube S}(-1)^{|T|1}F_{S-T}G_TFST⊆S∑(−1)∣T∣1FS−TGT 然后化成集合幂级数的形式就是 FFG1⇒F11−GFFG1\Rightarrow F\frac{1}{1-G}FFG1⇒F1−G1
至于集合幂级数怎么求逆定义占位多项式 GS,i′∑S0n[count(S)i]GSG_{S,i}\sum_{S0}^n[count(S)i]G_SGS,i′S0∑n[count(S)i]GS 然后对于每个GSG_SGS视为一个多项式求逆。
然后求逆可以用O(n2)O(n^2)O(n2)的反正nnn很小。
对于aaa求逆首先有a−1[x0]1a[x0]a^{-1}[x_0]\frac{1}{a[x_0]}a−1[x0]a[x0]1然后有 ∑i0na[xi]a−1[xn−i]0⇒a−1[xn]∑i0n−1a−1[xi]a[xn−i]a[x0]\sum_{i0}^na[x^i]a^{-1}[x^{n-i}]0\Rightarrow a^{-1}[x^n]\frac{\sum_{i0}^{n-1}a^{-1}[x^i]a[x^{n-i}]}{a[x^0]}i0∑na[xi]a−1[xn−i]0⇒a−1[xn]a[x0]∑i0n−1a−1[xi]a[xn−i]
这样就可以O(n2)O(n^2)O(n2)递推了。
时间复杂度O(2nn2)O(2^nn^2)O(2nn2) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N18,P998244353;
ll n,m,MS,c[1N],g[1N],F[N1][1N],G[N1],H[1N];
void FWT(ll *f,ll op){for(ll p2;pMS;p1)for(ll k0,lenp1;kMS;kp)for(ll ik;iklen;i)(f[ilen]f[i]*opP)%P;return;
}
signed main()
{scanf(%lld%lld,n,m);for(ll i1,x,y;im;i){scanf(%lld%lld,x,y);x--;y--;g[(1x)|(1y)]1;}MS(1n);for(ll i0;in;i)for(ll s0;sMS;s)if(!((si)1))g[s^(1i)]|g[s];for(ll i1;iMS;i){c[i]c[i-(i-i)]1;if(!g[i])F[c[i]][i](c[i]1)?1:(P-1);}F[0][0]1;for(ll i0;in;i)FWT(F[i],1);for(ll s0;sMS;s){for(ll i0;in;i)F[i][s]P-F[i][s];G[0]1;for(ll i1;in;i){G[i]0;for(ll j1;ji;j)(G[i]P-G[i-j]*F[j][s]%P)%P;}H[s]G[n];
// printf(%lld ,G[n]);}FWT(H,-1);printf(%lld\n,(P1)/2*H[MS-1]%P*m%P);return 0;
}
