做导购网站多少钱,wordpress 小说,企业网站主页 优帮云,土地推介网[ZJOI2016]小星星
题目描述
luogu题面 给定一个n个点的树和n个点m条边的无向图#xff0c;求将树嵌入图的方案数。 其中 n≤17,m≤n∗(n−1)2n \leq 17,m \leq \frac{n*(n-1)}{2}n≤17,m≤2n∗(n−1)。
Solution
点数很少#xff0c;考虑状压DP。
令f[i][j][k]f[i][j]…[ZJOI2016]小星星
题目描述
luogu题面 给定一个n个点的树和n个点m条边的无向图求将树嵌入图的方案数。 其中 n≤17,m≤n∗(n−1)2n \leq 17,m \leq \frac{n*(n-1)}{2}n≤17,m≤2n∗(n−1)。
Solution
点数很少考虑状压DP。
令f[i][j][k]f[i][j][k]f[i][j][k]表示以iii结点为根的子树iii号结点对应图上的jjj号结点kkk集合中的结点已经被使用了。
转移就是枚举iii的儿子sonsonson枚举儿子对应的结点为ttt枚举kkk的子集sssf[i][j][k]∑son,t,sf[son][t][s]∗f[i][j][k−s]f[i][j][k]\sum_{son,t,s} f[son][t][s]*f[i][j][k-s]f[i][j][k]∑son,t,sf[son][t][s]∗f[i][j][k−s]
时间复杂度为O(3nnbalabala...)O(3^nn^{balabala...})O(3nnbalabala...)TLE。
考虑如何优化DP中枚举集合的状态。 有一种巧妙的容斥方法。
我们思考哪一些方案是不合法的显然倘若选出的若干树上的结点对应了相同的图上结点这一种方案不合法。
我们不在DP中枚举集合而是让他任意选择允许重复选同一个图上节点。 枚举可用的图上结点集合s用f[i][j]f[i][j]f[i][j]表示以iii结点为根的子树iii号结点对应图上的jjj号结点只能选择图上s集合包含的结点的方案数。
此时的最终答案Ans∑s∑jf[1][j](−1)popcount(2n−1−s)Ans\sum_{s} \sum_{j} f[1][j](-1)^{popcount(2^n-1-s)}Ans∑s∑jf[1][j](−1)popcount(2n−1−s) 时间复杂度O(2nn3)O(2^nn^3)O(2nn3)luoguO2luogu\;\;O2luoguO2可过。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
vectorint e[20];
ll f[20][20];
int pick[20],flag[20][20],n,m;
void tree_dp(int x,int father)
{for (auto v:e[x]){if (vfather) continue;tree_dp(v,x);}for (int i1;in;i) f[x][i]pick[i];for (auto v:e[x]){if (vfather) continue;for (int j1;jn;j)if (pick[j]){ll sum0;for (int k1;kn;k)if (flag[j][k]pick[k]) sumf[v][k];f[x][j]*sum;}}
}
int main()
{nread(),mread();for (int i1;im;i){int uread(),vread();flag[u][v]flag[v][u]1;}for (int i1;in;i){int uread(),vread();e[u].PB(v),e[v].PB(u);}ll ans0;for (int i1;i1n;i){int opt((n-__builtin_popcount(i))1)?-1:1;for (int j1;jn;j) pick[j](i(j-1))1;tree_dp(1,0);for (int j1;jn;j) ansf[1][j]*opt;}printf(%lld\n,ans);return 0;
}
