因?yàn)橹挥衧td，沒有自我實(shí)現(xiàn)，所以是無碼專區(qū)

主要是為了訓(xùn)練思維能力

solution才是dls正解，但是因?yàn)橹挥辛什輲拙?#xff0c;所以大部分會(huì)有我自己基于正解上面的算法實(shí)現(xiàn)過程，可能選擇的算法跟std中dls的實(shí)現(xiàn)不太一樣。

std可能也會(huì)帶有博主自己的注釋。

---

problem

有 $n$ 個(gè)整數(shù)，第 $i$ 個(gè)整數(shù)在 $[x_i,y_i]$ 區(qū)間。

給定 $m$ 個(gè)限制，形如 $l_i,r_i,s_i$ ，要求第 $l_i$ 到 $r_i$ 的數(shù)字加起來對(duì) $2$ 取模余數(shù)為 $s_i$。

求有多少種整數(shù)序列滿足上面限制，答案對(duì) $10^9+7$ 取模。

以及輸出字典序最小的整數(shù)序列。

$n\le 40,m\le 100,0\le x_i\le y_i\le 1e9$

$1s,128MB$

---

my idea

因?yàn)橄拗剖窃谀?$2$ 意義下的，所以真的有關(guān)系的只是這個(gè)數(shù)是奇數(shù)還是偶數(shù)。

對(duì)于 $50\%$ 的數(shù)據(jù)點(diǎn) $n\le 20$，直接 $2^n$ 枚舉每一位是選的奇數(shù)還是偶數(shù)，然后枚舉所有限制判斷是否合法，順道可以記錄一下字典序最小解及個(gè)數(shù)，時(shí)間復(fù)雜度 $O(2^{n}m)$。

將 $[l_i,r_i]$ 的限制轉(zhuǎn)化為前綴和做差的限制，即 $sum(r)?sum(l?1)$。

將 $sum(i)$ 看作一個(gè)點(diǎn)，將一個(gè)限制看作 $l_i?1\to r_i$ 的有向邊，邊權(quán)為 $s_i$。

這樣會(huì)形成若干個(gè)相互獨(dú)立的有向圖。

考慮將這些圖，以及圖內(nèi)一個(gè)點(diǎn)可能引發(fā)的若干條邊合并起來，變成一條鏈。

i.e. 要求 $[3,5]=1,[4,8]=0,[4,7]=1?2\to 5(1),3\to 8(0),3\to 7(1)$

$?2\to 3(x)\to 5(x?1)\to 7(x?1)\to 8(x)$

當(dāng)最開始的一條邊上的權(quán)確定時(shí)，整條鏈就確定了。

具體而言：直接枚舉兩兩限制進(jìn)行合并，$[l_1,r_1][l_2,r_2],l_1<l_2<r_1<r_2?l_1\to l_2\to r_1\to r_2$。

然后對(duì)于每個(gè)參與點(diǎn)進(jìn)行限制的 $dfs$，開始跑每條邊的邊權(quán)。

如果到相同點(diǎn)的邊權(quán)在取模 $2$ 意義下不同，說明限制之間出現(xiàn)矛盾。

注意到并不是每個(gè)數(shù)都在這條鏈上，i.e. $4,6,1...$

這些邊只是起將限制緊密聯(lián)系在一起的作用。

每兩個(gè)點(diǎn)之間的原區(qū)間的方案數(shù)是可以通過 $dp$ 計(jì)算的。

設(shè) $d{p}_{i,0/1}:$ 前 $i$ 個(gè)數(shù)和為 $0/1$ （在$(\mathrm{m}\mathrm{o}\mathrm{d}2)$ 的意義下）的方案數(shù)。

一個(gè)數(shù)的取值區(qū)間 $[l_i,r_i]$，無非可以劃分為奇數(shù) $x$ 個(gè)，偶數(shù) $y$ 個(gè)。

選奇數(shù)會(huì)改變奇偶，選偶數(shù)則不改變。
$$\begin{gathered} d{p}_{i,0}\leftarrow d{p}_{i?1,0}\times y+d{p}_{i?1,1}\times x \\ d{p}_{i,1}\leftarrow d{p}_{i?1,0}\times x+d{p}_{i?1,1}\times y \end{gathered}$$
沒有限制的區(qū)間就這么轉(zhuǎn)移，一旦有類似與上面的邊限制，去除掉不合法，繼續(xù)轉(zhuǎn)移即可。

貌似這樣轉(zhuǎn)移很困難w(ﾟДﾟ)w

---

solution

首先， 考慮前綴和， 每個(gè) $[l,r]$ 的限制轉(zhuǎn)化為 $l?1$ 到 $r$ 兩個(gè)前綴和之間的限制。

然后對(duì)所有限制進(jìn)行連邊。

每個(gè)連通塊的奇偶性只有兩種選擇方法。【并不需要像我那么傻逼地去縮成一條鏈】

我們可以枚舉每個(gè)連通塊的奇偶性， 然后統(tǒng)計(jì)答案。

注意到， 如果一個(gè)連通塊只有 $1$ 個(gè)數(shù)，我們不需要枚舉（放到后面去 $dp$）

因?yàn)檫@個(gè)位置的奇偶性不會(huì)影響到別的元素。

所以只要在枚舉完每個(gè)大于等于 $2$ 的連通塊的奇偶性之后， 從右往左做一遍 $dp$， 記錄一下當(dāng)前前綴和的奇偶性是多少， 對(duì)應(yīng)的方案數(shù)即可。

時(shí)間復(fù)雜度 $O(2^{\frac{n}{2}}n)$。

---

std

#include <bits/stdc++.h> using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 42 ; const int mod = 1e9 + 7 ;char buf[1000000] ; int len ; int p[MAXN], c[MAXN] ; int L[MAXN], R[MAXN], odd[MAXN], even[MAXN] ; int dp[MAXN][MAXN][2] ; pair < int, int > nxt[MAXN][MAXN][2] ; int ans[MAXN], tmp[MAXN] ; int rt[MAXN], col[MAXN] ; int idx[MAXN] ; int use[MAXN] ; int n, m ; int T ;int F ( int x ) { //帶權(quán)并查集實(shí)現(xiàn)前綴和限制if ( p[x] == x ) return x ;int res = F ( p[x] ) ;c[x] ^= c[p[x]] ;return p[x] = res; }int upd ( int x, int y, int o, int n ) {if ( dp[y][x][o] == 0 )return 0 ;int m = y - x ;for ( int i = x ; i <= y ; ++ i ) {tmp[i] = nxt[y][i][o].first ;o = nxt[y][i][o].second ;}return 1 ; }void up ( int ok ) {if ( !ok )return ;for ( int i = 1 ; i <= n ; ++ i ) {if ( tmp[i] > ans[i] )return ;if ( tmp[i] < ans[i] ) {for ( int j = 1 ; j <= n ; ++ j ) {ans[j] = tmp[j] ;}return ;}} }void add ( int x ) {if ( x / 10 )add ( x / 10 ) ;buf[len ++] = x % 10 + '0' ; }int main() {freopen("parity.in", "r", stdin);freopen("parity.out", "w", stdout);scanf ( "%d%d", &n, &m ) ;for ( int i = 0 ; i <= n ; ++ i ) {p[i] = i ;c[i] = 0 ;use[i] = 0 ;}for ( int i = 1 ; i <= n ; ++ i ) {scanf ( "%d%d", &L[i], &R[i] ) ;int tmp = R[i] - L[i] + 1 ; //計(jì)算i可選范圍內(nèi)奇數(shù)和偶數(shù)的個(gè)數(shù)odd[i] = tmp / 2 + ( tmp % 2 == 1 && R[i] % 2 == 1 ) ;even[i] = tmp / 2 + ( tmp % 2 == 1 && R[i] % 2 == 0 ) ;}for ( int i = 1 ; i <= n ; ++ i ) {for ( int j = 1 ; j <= n + 1 ; ++ j ) {dp[i][j][0] = dp[i][j][1] = 0 ;nxt[i][j][0] = make_pair ( mod, mod ) ;nxt[i][j][1] = make_pair ( mod, mod ) ;}}//dp[l][r][0/1]:計(jì)算[l,r]區(qū)間內(nèi)數(shù)的奇偶性for ( int i = 1 ; i <= n ; ++ i ) {dp[i][i + 1][0] = 1 ;for ( int j = i ; j >= 1 ; -- j ) {dp[i][j][0] = ( 1LL * dp[i][j + 1][1] * odd[j] + 1LL * dp[i][j + 1][0] * even[j] ) % mod ;dp[i][j][1] = ( 1LL * dp[i][j + 1][0] * odd[j] + 1LL * dp[i][j + 1][1] * even[j] ) % mod ;}for ( int j = 1 ; j <= i ; ++ j ) {if ( dp[i][j + 1][1] && odd[j] ) {nxt[i][j][0] = min ( nxt[i][j][0], make_pair ( L[j] + ( L[j] % 2 == 0 ), 1 ) ) ;}if ( dp[i][j + 1][0] && even[j] ) {nxt[i][j][0] = min ( nxt[i][j][0], make_pair ( L[j] + ( L[j] % 2 == 1 ), 0 ) ) ;}if ( dp[i][j + 1][0] && odd[j] ) {nxt[i][j][1] = min ( nxt[i][j][1], make_pair ( L[j] + ( L[j] % 2 == 0 ), 0 ) ) ;}if ( dp[i][j + 1][1] && even[j] ) {nxt[i][j][1] = min ( nxt[i][j][1], make_pair ( L[j] + ( L[j] % 2 == 1 ), 1 ) ) ;}}}int ok = 1 ;for ( int i = 1 ; i <= m ; ++ i ) {int u, v, w, x, y ;scanf ( "%d%d%d", &u, &v, &w ) ;-- u ;x = F ( u ) ;y = F ( v ) ;use[u] = use[v] = 1 ;if ( x != y ) {if ( x < y ) swap ( x, y ) ;p[x] = y ;c[x] = ( c[u] - c[v] + 2 + w ) % 2 ;} else if ( ( c[u] ^ c[v] ) != w ) ok = 0 ;}if ( !ok ) { //限制沖突 無解-1buf[len ++] = '0' ;buf[len ++] = '\n' ;buf[len ++] = '-' ;buf[len ++] = '1' ;buf[len ++] = '\n' ;return 0;}int cnt = 0, tot = 0, uns = 0;for ( int i = 0 ; i <= n ; ++ i )if ( use[i] ) {if ( F ( i ) == i )rt[cnt ++] = i;idx[tot ++] = i;} elseuns++;int res = 0, OK = 0 ;for ( int i = 1 ; i <= n ; ++ i )ans[i] = mod ;for ( int s = 0 ; s < 1 << cnt ; ++ s ) {if ( cnt && rt[0] == 0 && s % 2 )continue ;col[0] = 0 ;for ( int i = 0 ; i < cnt ; ++ i ) {col[rt[i]] = s >> i & 1 ;}int ans = 1, j = 0, ok = 1 ;for ( int o = ( rt[0] == 0 ) ; o < tot ; ++ o ) {int i = idx[o], x = p[i] ;if ( x != i )col[i] = col[x] ^ c[x] ^ c[i] ;ans = 1LL * ans * dp[i][j + 1][col[j] ^ col[i]] % mod ;ok &= upd ( j + 1, i, col[j] ^ col[i], j ) ;if ( !ok )break ;j = i ;}if ( ok && j < n ) {ans = 1LL * ans * ( dp[n][j + 1][0] + dp[n][j + 1][1] ) % mod ;int a = upd ( j + 1, n, 0, j ) ;up ( ok && a ) ;int b = upd ( j + 1, n, 1, j ) ;up ( ok && b ) ;ok &= a | b ;} elseup ( ok ) ;if ( ok )OK = 1 ;res = ( res + ans ) % mod ;}if ( !OK ) {buf[len ++] = '0' ;buf[len ++] = '\n' ;buf[len ++] = '-' ;buf[len ++] = '1' ;buf[len ++] = '\n' ;} else {add ( res ) ;buf[len ++] = '\n' ;for ( int i = 1 ; i <= n ; ++ i ) {add ( ans[i] ) ;buf[len ++] = i < n ? ' ' : '\n' ;}}buf[len] = 0;printf("%s", buf); }

總結(jié)

以上是生活随笔為你收集整理的【无码专区9】序列统计（带权并查集 + 前缀和建边 + dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。