ZOJ 3824 Fiber-optic Network
Fiber-optic Network
64-bit integer IO format: %lld Java class name: Main
one router. These routers are connected by optical cables in such a way that there is exactly one path between any two routers.
Each router should be initialized with an operating frequency Fi before it starts to work. Due to the limitations of hardware and environment, the operating frequency should be an integer number within [Li, Ri]. In order to reduce the signal noise, the operating frequency of any two adjacent routers should be co-prime.
Edward is the headmaster of Marjar University. He is very interested in the number of different ways to initialize the operating frequency. Please write a program to help him! To make the report simple and neat, you only need to calculate the sum of Fi (modulo 1000000007) in all solutions for each router.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains one integer N (1 <= N <= 50). The next line contains N integers Li (1 <= Li <= 50000). Then, the following line contains N integers Ri (Li <= Ri <= 50000).
For the next N - 1 lines, each line contains two integers Xi and Yi. That means there is an optical cable connecting router Xi and router Yi (indexes are 1-based).
Output
For each test case, output a line with N integers representing the sum of Fi (modulo 1000000007) in all solutions.
Sample Input
2 4 1 2 3 4 2 3 4 5 1 2 2 3 3 4 4 1 2 3 4 2 3 4 5 1 2 1 3 1 4
Sample Output
5 10 14 19 10 23 31 41
Hint
In the first sample test case, there are 4 ways to initialize the operating frequency:
- 1 2 3 4
- 1 2 3 5
- 1 3 4 5
- 2 3 4 5
Source
Author
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn = 50001; 5 const int maxm = 51; 6 const LL mod = 1000000007; 7 vector<int>p[maxn]; 8 vector<int>g[maxm]; 9 vector<int>fac[maxm][maxn]; 10 bool np[maxn] = {true,true}; 11 int L[maxm],R[maxm]; 12 LL dp[maxm][maxn],multi[maxm][maxn],sum[maxm],ans[maxm]; 13 void init() { 14 for(int i = 2; i < maxn; ++i) { 15 if(!np[i]) { 16 for(int j = i; j < maxn; j += i) { 17 np[j] = true; 18 p[j].push_back(i); 19 } 20 } 21 } 22 } 23 LL quickPow(LL base,LL index,LL mod) { 24 LL ret = 1; 25 while(index) { 26 if(index&1) ret = ret*base%mod; 27 base = base*base%mod; 28 index >>= 1; 29 } 30 return ret; 31 } 32 LL inv(LL b,LL mod) { 33 return quickPow(b,mod-2,mod); 34 } 35 void dfs(int u,int fa) { 36 for(int i = L[u]; i <= R[u]; ++i) dp[u][i] = 1; 37 for(int i = 0; i < g[u].size(); ++i) { 38 if(g[u][i] == fa) continue; 39 dfs(g[u][i],u); 40 } 41 for(int j = L[u]; j <= R[u]; ++j) { 42 fac[u][j].clear(); 43 for(int i = 0; i < g[u].size(); ++i) { 44 if(g[u][i] == fa) continue; 45 LL S = 0; 46 for(int k = 1,sz = (1<<p[j].size()); k < sz; ++k) { 47 LL tmp = 1; 48 int cnt = 0; 49 for(int t = 0; t < p[j].size(); ++t) { 50 if((k>>t)&1) { 51 ++cnt; 52 tmp *= p[j][t]; 53 if(tmp >= maxn) break; 54 } 55 } 56 if(tmp < maxn) S = (S + ((cnt&1)?multi[g[u][i]][tmp]:-multi[g[u][i]][tmp]))%mod; 57 } 58 LL num = ((sum[g[u][i]] - S)%mod + mod)%mod; 59 dp[u][j] = dp[u][j]*num%mod; 60 fac[u][j].push_back(num); 61 } 62 } 63 sum[u] = 0; 64 for(int i = 1; i < maxn; ++i) { 65 sum[u] = (sum[u] + dp[u][i])%mod; 66 multi[u][i] = 0; 67 for(int j = i; j < maxn; j += i) 68 multi[u][i] = (multi[u][i] + dp[u][j])%mod; 69 } 70 } 71 void dfs2(int u,int fa) { 72 ans[u] = 0; 73 for(int i = L[u]; i <= R[u]; ++i) ans[u] = (ans[u] + dp[u][i]*i)%mod; 74 for(int i = 0,c = 0; i < g[u].size(); ++i) { 75 if(g[u][i] == fa) continue; 76 for(int j = L[u]; j <= R[u]; ++j) 77 if(dp[u][j]) dp[u][j] = dp[u][j]*inv(fac[u][j][c],mod)%mod; 78 sum[u] = 0; 79 for(int k = 1; k < maxn; ++k) { 80 multi[u][k] = 0; 81 sum[u] = (sum[u] + dp[u][k])%mod; 82 for(int j = k; j < maxn; j += k) 83 multi[u][k] = (multi[u][k] + dp[u][j])%mod; 84 } 85 for(int j = L[g[u][i]]; j <= R[g[u][i]]; ++j) { 86 LL S = 0; 87 for(int k = 1,sz = p[j].size(); k < (1<<sz); ++k) { 88 int cnt = 0; 89 LL tmp = 1; 90 for(int t = 0; t < sz; ++t) 91 if((k>>t)&1) { 92 ++cnt; 93 tmp *= p[j][t]; 94 if(tmp >= maxn) break; 95 } 96 if(tmp < maxn) S = (S + ((cnt&1)?multi[u][tmp]:-multi[u][tmp]))%mod; 97 } 98 dp[g[u][i]][j] = dp[g[u][i]][j]*(((sum[u] - S)%mod + mod)%mod)%mod; 99 } 100 dfs2(g[u][i],u); 101 for(int j = L[u]; j <= R[u]; ++j) 102 if(dp[u][j]) dp[u][j] = dp[u][j]*fac[u][j][c]%mod; 103 ++c; 104 } 105 } 106 int main() { 107 init(); 108 int kase,n,u,v; 109 scanf("%d",&kase); 110 while(kase--) { 111 scanf("%d",&n); 112 for(int i = 1; i <= n; ++i){ 113 scanf("%d",L + i); 114 g[i].clear(); 115 } 116 memset(dp,0,sizeof dp); 117 for(int i = 1; i <= n; ++i) 118 scanf("%d",R + i); 119 for(int i = 1; i < n; ++i) { 120 scanf("%d%d",&u,&v); 121 g[u].push_back(v); 122 g[v].push_back(u); 123 } 124 dfs(1,-1); 125 dfs2(1,-1); 126 for(int i = 1; i <= n; ++i) 127 printf("%lld%c",ans[i],i==n?'\n':' '); 128 } 129 return 0; 130 }