3.20
HDU 5647 DZY Loves Connecting
不能直接逆元搞，因为可能会变成0。（据说可以特判一下。
然而直接dp[0]子树方案数，dp[1]子树贡献一次dp就可以了。
考虑当前节点新加一个孩子树，增加的贡献分两部分，
一部分是原来树节点的贡献，增加原来的答案×新增孩子树方案数，
另一部分是新增孩子树的贡献，增加原来方案数×新增孩子树答案。
1 #pragma comment(linker, "/STACK:102400000,102400000") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 typedef long long LL; 8 const LL mod = 1e9 + 7; 9 const int maxn = 2e5 + 10; 10 11 // tree 12 int cnt, h[maxn]; 13 struct edge 14 { 15 int to, pre; 16 } e[maxn<<1]; 17 18 void add(int from, int to) 19 { 20 cnt++; 21 e[cnt].pre = h[from]; 22 e[cnt].to = to; 23 h[from] = cnt; 24 } 25 26 void init() 27 { 28 cnt = 0; 29 memset(h, 0, sizeof(h)); 30 } 31 32 // dp 33 LL dp[maxn][2]; 34 void dfs(int x, int f) 35 { 36 dp[x][0] = dp[x][1] = 1; 37 for(int i = h[x]; i; i = e[i].pre) 38 { 39 int to = e[i].to; 40 if(to == f) continue; 41 dfs(to, x); 42 dp[x][1] = (dp[x][1] * (dp[to][0] + 1) + dp[x][0] * dp[to][1]) % mod; 43 dp[x][0] = dp[x][0] * (dp[to][0] + 1) % mod; 44 } 45 } 46 47 int main(void) 48 { 49 int T; 50 scanf("%d", &T); 51 while(T--) 52 { 53 init(); 54 int n; 55 scanf("%d", &n); 56 for(int i = 2; i <= n; i++) 57 { 58 int p; 59 scanf("%d", &p); 60 add(i, p), add(p, i); 61 } 62 dfs(1, 0); 63 LL ans = 0; 64 for(int i = 1; i <= n; i++) ans = (ans + dp[i][1]) % mod; 65 printf("%I64d\n", ans); 66 } 67 return 0; 68 }
HDU 5648 DZY Loves Math
预处理每个数的子集（ 关于j = (j - 1) & i 这个飘逸写法我果然不是最后一个知道的- -。
枚举每对a = i & j, b = i | j，那么a就是i和j公用的bit，接下来任务就是把剩下的bit(即b - a)分配给i和j。
考虑把bit分给i，下界是b - m，小于这个值j就会大于m炸掉，上界是n - a，否则i爆掉。
然后在b - a的子集里面二分找上下界之间的个数就好了。
具体过程就是这样，但是要注意如果公共部分是0，两边至少都分配一个bit，因为i，j要正数。
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 typedef long long LL; 7 const int maxn = 1 << 16; 8 vector<int> A[maxn]; 9 int n, m, len; 10 LL ans; 11 12 int gcd(int a, int b) 13 { 14 if(!b) return a; 15 return a % b ? gcd(b, a % b) : b; 16 } 17 18 int get(int left, int x) 19 { 20 if(x < 0) return 0; 21 int l = 0, r = A[left].size() - 1, mid; 22 while(l < r) 23 { 24 mid = r - (r - l) / 2; 25 if(A[left][mid] <= x) l = mid; 26 else r = mid - 1; 27 } 28 return l + 1; 29 } 30 31 void dfs(int a, int b, int d) 32 { 33 if(d == len) 34 { 35 int left = b - a, l = left + a - m, r = n - a; 36 if(!a) r = min(r, left - 1), l = max(l, 1); 37 if(l > r) return; 38 // printf("a = %d , b = %d, gcd = %d, cnt = %d\n", a, b, gcd(a,b), get(left, r) - get(left, l - 1)); 39 ans += (LL) gcd(a, b) * (get(left, r) - get(left, l - 1)); 40 return; 41 } 42 dfs(a + (1 << d), b + (1 << d), d + 1); 43 dfs(a, b + (1 << d), d + 1); 44 dfs(a, b, d + 1); 45 } 46 47 int main(void) 48 { 49 for(int i = 0; i < maxn; i++) 50 { 51 for(int j = i; ; j = (j - 1) & i) 52 { 53 A[i].push_back(j); 54 if(!j) break; 55 } 56 reverse(A[i].begin(), A[i].end()); 57 } 58 int T; 59 scanf("%d", &T); 60 while(T--) 61 { 62 scanf("%d %d", &n, &m); 63 if(n < m) swap(n, m); 64 len = 0; 65 while((1 << len) <= n) len++; 66 ans = 0; 67 dfs(0, 0, 0); 68 printf("%I64d\n", ans); 69 } 70 return 0; 71 }
原文：http://www.cnblogs.com/Aguin/p/5304188.html
