比较有特色的网站,长沙网红打卡点,南通的互联网公司网站,做网站和做软件一样吗考虑题目转化#xff0c;二进制下满足 i ⊆ j , ( i x ) ⊆ ( j y ) i\subseteq j,(ix)\subseteq (jy) i⊆j,(ix)⊆(jy)
这显然是个数位dp形式
考虑枚举每一位与进位#xff0c; d p k , p 1 , p 2 dp_{k,p_1,p_2} dpk,p1,p2 表示第 k − 1 k-1 k−1 位向第 k k…考虑题目转化二进制下满足 i ⊆ j , ( i x ) ⊆ ( j y ) i\subseteq j,(ix)\subseteq (jy) i⊆j,(ix)⊆(jy)
这显然是个数位dp形式
考虑枚举每一位与进位 d p k , p 1 , p 2 dp_{k,p_1,p_2} dpk,p1,p2 表示第 k − 1 k-1 k−1 位向第 k k k 位分别进位 p 1 , p 2 p_1,p_2 p1,p2 的方案数
考虑当前 ( i , j ) (i,j) (i,j) 二进制下分别为 q 1 , q 2 q_1,q_2 q1,q2则 ( i x , j y ) ( p 1 q 1 x i , p 2 q 2 y i ) ( n 1 , n 2 ) (ix,jy)(p_1q_1x_i,p_2q_2y_i)(n_1,n_2) (ix,jy)(p1q1xi,p2q2yi)(n1,n2)
必须满足 q 1 ⊆ q 2 , n 1 1 ⊆ n 2 1 q1\subseteq q2,n1\1\subseteq n2\1 q1⊆q2,n11⊆n21由 d p ( i 1 , n 1 2 , n 2 2 ) dp(i1,\frac{n_1}2,\frac{n_2}2) dp(i1,2n1,2n2) 转移过来
综上 d p ( k , i , j ) ∑ q 1 ⊆ q 2 , n 1 p 1 q 1 x i , n 2 p 2 q 2 y i [ n 1 1 ⊆ n 2 1 ] d p ( i 1 , n 1 2 , n 2 2 ) \Large dp(k,i,j)\sum_{q1\subseteq q2,n1p1q1x_i,n2p2q2y_i}[n1\1\subseteq n2\1]dp(i1,\frac{n_1}2,\frac{n_2}2) dp(k,i,j)q1⊆q2,n1p1q1xi,n2p2q2yi∑[n11⊆n21]dp(i1,2n1,2n2)
dp[n][0][0].a[1]1;
for(in-1; i0; --i) {for(p10; p11; p1) for(p20; p21; p2) {for(q10; q11; q1) for(q2q1; q21; q2) {n1p1q1x[i]; n2p2q2y[i]; if(n1%2n2%2) continue; dp[i][p1][p2]dp[i][p1][p2]dp[i1][n1/2][n2/2]; }}}
dp[0][0][0].print();
