题目
设 f s f_s fs?为集合 s s s的 ( ∑ w ) p ? [ s 合 法 ] (\sum w)^p * [s合法] (∑w)p?[s合法]
那么可以得到
d p S = 1 f S ∑ T ? S d p T f S ? T dp_S = \frac 1{f_S}\sum_{T\subset S} dp_T f_{S-T} dpS?=fS?1?∑T?S?dpT?fS?T?
因为子集和卷积是按照1的个数逐层转移的，所以这个转移可以和子集和卷积一起转移，
使用FMT复杂度O ( n 2 2 n ) O(n^2 2^n) O(n22n)
AC Code:
#include
#include
#include
#include
#define maxn 21
#define mod 998244353
using namespace std;
int n,m,p;
int c[maxn][maxn],lg[1<>i&1){
if(tp == 1)
A[j] = (A[j] + A[j^(1<>=1,base=1ll*base*base%mod)
if(k&1)
ret=1ll*ret*base%mod;
return ret;
}int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=2;
i<(1<>1] + 1;
for(int i=1;
i<=m;
i++){
int u,v;
scanf("%d%d",&u,&v);
u--,v--;
c[u][v]=c[v][u]=1;
}
for(int i=0;
i 【模板|LOJ #2340. 「WC2018」州区划分(FMT子集卷积)】省选前最后一篇博客了，rp++。
推荐阅读
- 分治|全排列算法整理
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组