说在前面
luogu什么情况= =
me就交了三次，还都被卡常了
再交了一遍就直接全部返回RE了？合着以为me是在卡评测吗……？
然后就去UOJ上过了这题……
luogu差评*1
题目 UOJ#348传送门
看题可戳传送门
解法
之前去WC的时候还不会FWT（或者FMT，反正都不会），于是考场上只写了 3n3 n 做法
（还记得当时，怎么都过不了样例的绝望hhhh）
嗯！然后现在把这个坑给填了
首先根据题意，可以写出一个很显然的dp，就是： dp[k][s]=∑i∑j[i+j→s] dp[k?1][i]?(sum[j]sum[s])pd p [ k ] [ s ] = ∑ i ∑ j [ i + j → s ]d p [ k ? 1 ] [ i ] ? ( s u m [ j ] s u m [ s ] ) p 。 dp[k][s]d p [ k ] [ s ] 表示分了k个州，选择的城市集合为s时，满意度乘积的和。 i+j→si + j → s 的意思是， ii 与 jj 无交，且 ii 并 jj 是 ss 。其中需要保证 jj 是一个合法的划分，这个可以预处理
可以发现，第一维并没有什么卵用。因为最终我们想要的，不是分组怎么样，而是只要分组合理就可以了。所以可以把第一维省掉
然后就变成了这样： dp[s]=∑i∑j[i+j→s] dp[i]?(sum[j]sum[s])pd p [ s ] = ∑ i ∑ j [ i + j → s ]d p [ i ] ? ( s u m [ j ] s u m [ s ] ) p
化简一下变成了这样： sum[s]p?dp[s]=∑i∑j[i+j→s] dp[i]?sum[j]ps u m [ s ] p ? d p [ s ] = ∑ i ∑ j [ i + j → s ]d p [ i ] ? s u m [ j ] p
发现这已经是一个很明显的子集卷积的形式，于是把数组按二进制1的个数拆开，然后做FMT即可
【[UOJ#348]-[WC2018]州区划分-FMT】这时候，如果你觉得，这是一个自己和自己卷积的形式，因此无法做拆位FMT的话……那么恭喜你！你和me一样蠢……QAQ
因为这个dp式子，虽然看起来是自己和自己卷，然而如果把拆位的那一维也写出来，就可以发现，其实已经形成了普通的子集卷积形式，因此是可以直接按照顺序求的
下面是自带大常数的代码
#include 
