网站制作的流程包括,网站 系统设置,做装饰工程的在什么网站投标,太原网站制作多少钱因为只有std#xff0c;没有自我实现#xff0c;所以是无码专区
主要是为了训练思维能力
solution才是dls正解#xff0c;但是因为只有潦草几句#xff0c;所以大部分会有我自己基于正解上面的算法实现过程#xff0c;可能选择的算法跟std中dls的实现不太一样。
std可能…因为只有std没有自我实现所以是无码专区
主要是为了训练思维能力
solution才是dls正解但是因为只有潦草几句所以大部分会有我自己基于正解上面的算法实现过程可能选择的算法跟std中dls的实现不太一样。
std可能也会带有博主自己的注释。 problem
有 nnn 个整数第 iii 个整数在 [xi,yi][x_i,y_i][xi,yi] 区间。
给定 mmm 个限制形如 li,ri,sil_i,r_i,s_ili,ri,si 要求第 lil_ili 到 rir_iri 的数字加起来对 222 取模余数为 sis_isi。
求有多少种整数序列满足上面限制答案对 109710^971097 取模。
以及输出字典序最小的整数序列。
n≤40,m≤100,0≤xi≤yi≤1e9n\le 40,m\le 100,0\le x_i\le y_i\le 1e9n≤40,m≤100,0≤xi≤yi≤1e9
1s,128MB1s,128MB1s,128MB my idea
因为限制是在模 222 意义下的所以真的有关系的只是这个数是奇数还是偶数。
对于 50%50\%50% 的数据点 n≤20n\le 20n≤20直接 2n2^n2n 枚举每一位是选的奇数还是偶数然后枚举所有限制判断是否合法顺道可以记录一下字典序最小解及个数时间复杂度 O(2nm)O(2^nm)O(2nm)。
将 [li,ri][l_i,r_i][li,ri] 的限制转化为前缀和做差的限制即 sum(r)−sum(l−1)sum(r)-sum(l-1)sum(r)−sum(l−1)。
将 sum(i)sum(i)sum(i) 看作一个点将一个限制看作 li−1→ril_i-1\rightarrow r_ili−1→ri 的有向边边权为 sis_isi。
这样会形成若干个相互独立的有向图。
考虑将这些图以及图内一个点可能引发的若干条边合并起来变成一条链。
i.e. 要求 [3,5]1,[4,8]0,[4,7]1⇒2→5(1),3→8(0),3→7(1)[3,5]1,[4,8]0,[4,7]1\Rightarrow 2\rightarrow 5(1),3\rightarrow 8(0),3\rightarrow 7(1)[3,5]1,[4,8]0,[4,7]1⇒2→5(1),3→8(0),3→7(1)
⇒2→3(x)→5(x⨁1)→7(x⨁1)→8(x)\Rightarrow 2\rightarrow 3(x)\rightarrow 5(x\bigoplus 1)\rightarrow 7(x\bigoplus1)\rightarrow 8(x)⇒2→3(x)→5(x⨁1)→7(x⨁1)→8(x)
当最开始的一条边上的权确定时整条链就确定了。 具体而言直接枚举两两限制进行合并[l1,r1][l2,r2],l1l2r1r2⇒l1→l2→r1→r2[l_1,r_1][l_2,r_2],l_1l_2r_1r_2\Rightarrow l_1\rightarrow l_2\rightarrow r_1\rightarrow r_2[l1,r1][l2,r2],l1l2r1r2⇒l1→l2→r1→r2。 然后对于每个参与点进行限制的 dfsdfsdfs开始跑每条边的边权。 如果到相同点的边权在取模 222 意义下不同说明限制之间出现矛盾。 注意到并不是每个数都在这条链上i.e. 4,6,1...4,6,1...4,6,1...
这些边只是起将限制紧密联系在一起的作用。
每两个点之间的原区间的方案数是可以通过 dpdpdp 计算的。
设 dpi,0/1:dp_{i,0/1}:dpi,0/1: 前 iii 个数和为 0/10/10/1 在(mod2)\pmod 2(mod2) 的意义下的方案数。
一个数的取值区间 [li,ri][l_i,r_i][li,ri]无非可以划分为奇数 xxx 个偶数 yyy 个。
选奇数会改变奇偶选偶数则不改变。 dpi,0←dpi−1,0×ydpi−1,1×xdpi,1←dpi−1,0×xdpi−1,1×ydp_{i,0}\leftarrow dp_{i-1,0}\times ydp_{i-1,1}\times x\\dp_{i,1}\leftarrow dp_{i-1,0}\times xdp_{i-1,1}\times y dpi,0←dpi−1,0×ydpi−1,1×xdpi,1←dpi−1,0×xdpi−1,1×y 没有限制的区间就这么转移一旦有类似与上面的边限制去除掉不合法继续转移即可。
貌似这样转移很困难w(Д)w solution
首先 考虑前缀和 每个 [l,r][l,r][l,r] 的限制转化为 l−1l-1l−1 到 rrr 两个前缀和之间的限制。
然后对所有限制进行连边。
每个连通块的奇偶性只有两种选择方法。【并不需要像我那么傻逼地去缩成一条链】
我们可以枚举每个连通块的奇偶性 然后统计答案。
注意到 如果一个连通块只有 111 个数我们不需要枚举放到后面去 dpdpdp
因为这个位置的奇偶性不会影响到别的元素。
所以只要在枚举完每个大于等于 222 的连通块的奇偶性之后 从右往左做一遍 dpdpdp 记录一下当前前缀和的奇偶性是多少 对应的方案数即可。
时间复杂度 O(2n2n)O(2^\frac{n}{2}n)O(22nn)。 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 ) { //带权并查集实现前缀和限制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 ; //计算i可选范围内奇数和偶数的个数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]:计算[l,r]区间内数的奇偶性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);
}
