先给一道题目给定n nnn ≤ 20 n \le 20n≤20个数用a 1 a_1a1​到a n a_nan​表示对于所有i ∈ [ 0 , 2 n − 1 ] i\in [0,2^n-1]i∈[0,2n−1]求f i ∑ j ∈ i a j f_i\sum_{j\in i}^{} a_jfi​∑j∈i​aj​其中i ii表示一个集合。这就是 SOS DP 的常见形式。SOS DP 本质上就是一个高维前缀和我们先思考一下二维前缀和是怎么求的for(inti1;in;i)for(intj1;jm;j)s[i][j]s[i-1][j];for(inti1;in;i)for(intj1;jm;j)s[i][j]s[i][j-1];这是二维前缀和的其中一种写法我们先将二维的其中一维相加再将另一维相加。仿造二维前缀和我们可以写出 SOS DPfor(inti0;in;i)for(intj0;j(1n);j)if(j(1i))f[j]f[j^(1i)];例题[COCI 2011/2012 #6] KOŠARE题意给定n nn个数用a 1 a_1a1​到a n a_nan​表示选出若干个数使得这些数的或和为2 m − 1 2^m-12m−1问有多少种选数的方式。n ≤ 10 6 , m ≤ 20 n\le 10^6,m\le 20n≤106,m≤20。思路设g i g_igi​表示满足a j ∈ i a_j\in iaj​∈i的j jj的个数d p i dp_idpi​表示有多少种选择方案使得选出的数的或和是i ii的子集显然有d p i 2 g i − 1 dp_i 2^{g_i}-1dpi​2gi​−1。考虑容斥答案即为∑ i 0 2 m − 1 ( − 1 ) m − b i d p i \sum_{i0}^{2^m-1} (-1)^{m-b_i} dp_i∑i02m−1​(−1)m−bi​dpi​其中b i b_ibi​表示i ii在二进制下1 11的个数。有了 SOS DP代码会非常好写。代码#includebits/stdc.husingnamespacestd;constintN2e65,mod1e97;intn,m,a[N];longlongg[N],dp[N],jie[N];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;for(inti1;in;i){intk;cink;while(k--){intx;cinx;a[i](1(x-1));}g[a[i]];}for(inti0;im;i)for(intj0;j(1m);j)if(j(1i))g[j]g[j^(1i)];jie[0]1;for(inti1;in;i)jie[i]2ll*jie[i-1]%mod;for(inti0;i(1m);i)dp[i]jie[g[i]]-1;for(inti0;im;i)for(intj0;j(1m);j)if(j(1i))dp[j]-dp[j^(1i)];cout(dp[(1m)-1]%modmod)%mod;return0;}