T1：

　　转化题意，显然的思路是转化为每个点的贡献，于是考虑贡献的形式

集合大小乘以集合权值和，考虑每个点的贡献，考虑其实际意义，可以理解为

若存在点对u，v则对造成w[u] + w[v]的贡献

　　于是总分配方案即为第二类斯特林数，考虑首先若u点与自己进行配对时

会造成w[u]贡献，当与其余点配对时，考虑钦定u，v同组，这里的套路即为将

u，v合并为同一点，那么方案数仍为第二类斯特林数

　　对于单个斯特林数的求解直接设f[i]表示恰好有i个空集，g[i]表示至少有i个

空集，二项式反演即可

T2：

　　套路题，考虑如何更优这里的思路为考虑两次函数的变量比较变量即可

得出二者的优劣，排序即可，于是当a[i] > 0时发现T指数级增长，于是只需要

背包logT即可，对于a[i] == 0，发现只需要对于dp最终状态贪心选择即可

T3：

　　考虑设f[i]表示i堆异或和为0，p[i]为i堆方案数（下降幂），转移考虑

f[i] = p[i - 1] - f[i - 1]类似于Nim游戏的分析，若i - 1步异或非0，那么显然

存在一种操作使得第i次操作异或为0，然而发现这种情况是有限制的

　　因为各堆数量不能相同，也就数重复计算在于i - 2堆异或为0，第i- 1

堆异或非0，那么第i堆则不能异或出0，减去即可

T4：

　　可以发现本质上实际是求e * (x / v) ^ 2，因此70pts做法就机器及其简单，

状压枚举所有点集在枚举边集进行匹配即可

　　考虑其选取的策略，容易发现完全图时显然更优（比较函数即可），而

完全图中点数越大越优，于是问题转化为求最大完全图，Dfs+剪枝即可

　　考虑类似于DP，设f[i][j][k]表示当前最大团点集为i，正在查询j点是否能加入

最大团，当前最大团siz为k，剪枝最优性+可行性即可，详见代码注释

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define I int
 4 #define C char
 5 #define B bool
 6 #define V void
 7 #define S short
 8 #define D double
 9 #define LL long long
10 #define LD long double
11 #define UI unsigned int
12 #define UL unsigned long long
13 #define P pair<I,I>
14 #define MP make_pair
15 #define a first
16 #define b second
17 #define lowbit(x) (x & -x)
18 #define debug cout << "It's Ok Here !" << endl;
19 #define FP(x) freopen (#x,"r",stdin)
20 #define FC(x) freopen (#x,"w",stdout)
21 #define Tem template<typename T>
22 #define memset(name,val,typ,len) memset (name,val,sizeof (typ) * (len))
23 const I N = 40;
24 D w;
25 LL s[N];
26 I n,m,rec,num[N];
27 inline I read() {
28     I x (0), y (1); C z (getchar());
29     while (!isdigit(z)) z = getchar();
30     while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
31     return x * y;
32 }
33 Tem inline T abs (T &a) { return a >= 0 ? a : -a; }
34 Tem inline V Max (T &a,T  b) { a = a > b ? a : b; }
35 Tem inline V Min (T &a,T  b) { a = a < b ? a : b; }
36 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
37 #ifdef mod 
38 Tem inline V Mod1 (T &a,T b) { a = a + b > mod ? a + b - mod : a + b; }
39 Tem inline V Mod2 (T &a,T b) { a = a - b <  0  ? a - b + mod : a - b; }
40 Tem inline T Mod3 (T  a,T b) { return a + b > mod ? a + b - mod : a + b; }
41 Tem inline T Mod4 (T  a,T b) { return a - b <   0 ? a - b + mod : a - b; }
42 #endif
43 inline P operator + (const P &a,const P &b) {
44     return MP (a.a + b.a,a.b + b.b);
45 }
46 inline P operator - (const P &a,const P &b) {
47     return MP (a.a - b.a,a.b - b.b);
48 }
49 B Dfs (LL ste,I from,I siz) {   /* ste ：当前最大团的点集  from ：搜索起始点  siz ：最大团大小*/
50     for (I i(from);i < n && siz + num[i] > rec; ++ i)
51         if ((ste & s[i]) == ste /*判断当前点是否能继续构成最大团*/ && Dfs (ste | 1ll << i,i + 1,siz + 1))
52             return true;        /*若当前点能够形成大于rec的最大团那么之后的点一定不会超过当前siz*/
53     return siz > rec ? rec = siz, true : false; /*更新最大团rec*/
54 }
55 signed main () {
56     FP (nanami.in), FC (nanami.out);
57     n = read (), m = read (), scanf ("%lf",&w);
58     for (I i(1);i <= m; ++ i) {
59         I x (read () - 1), y (read () - 1);
60         s[x] |= 1ll << y, s[y] |= 1ll << x;
61     }
62     for (I i(n - 1);~i; -- i)   /*倒序正序同理*/
63         Dfs (1ll << i,i + 1,1), num[i] = rec;   /*记录该点及之后的点所能形成的最大团siz（dp）*/
64     printf ("%.6lf",0.5 * w * w * (rec - 1) / rec); 
65 }

View Code