Advertisement
Guest User

Untitled

a guest
Mar 3rd, 2018
363
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef unsigned long long ull;
  5. typedef pair<int,int> pii;
  6. #define fi first
  7. #define se second
  8. #define sz(a) ((int)a.size())
  9. #define pb push_back
  10. #define int ll
  11. const int inf_int = 1e9;
  12. const ll inf_ll = 1e18;
  13. const int MAXN = 2e5+100;
  14. const int MOD = 1e9+7;
  15.  
  16. bool debug = 0;
  17. #define dout if(debug) cout
  18. vector<int> g[MAXN];
  19. vector<int> to_big[MAXN];
  20. ll val[MAXN];
  21. int s[MAXN];
  22. int used[MAXN];
  23. int check[MAXN];
  24.  
  25. int block = 500;
  26.  
  27. int cnt[MAXN]; // for all
  28. int inc[MAXN]; // for big
  29.  
  30. inline void add(ll &p1,ll &q1,ll p2,ll q2){
  31. p1 = (p1*q2 + p2 * q1)%MOD;
  32. q1 = (q1 * q2)%MOD;
  33. }
  34.  
  35. ll pow_2[MAXN];
  36. ll rev_pow2[MAXN];
  37. int add_last[MAXN][210];
  38.  
  39. ll binpow(ll a, int n) {
  40. ll res = 1;
  41. while (n) {
  42. if (n & 1){
  43. res = (res * a)%MOD;
  44. }
  45. a = (a*a)%MOD;
  46. n >>= 1;
  47. }
  48. return res;
  49. }
  50.  
  51. inline ll rev(ll x){
  52. return binpow(x,MOD-2);
  53. }
  54.  
  55. inline ll mul(ll a,ll b){
  56. return (a*b)%MOD;
  57. }
  58.  
  59. ll p1[MAXN],q1[MAXN];
  60.  
  61. void solve(){
  62. pow_2[0] = 1;
  63. for(int i=1;i<MAXN;++i){
  64. pow_2[i] = (pow_2[i-1]*2)%MOD;
  65. }
  66. for(int i=0;i<MAXN;++i){
  67. rev_pow2[i] = rev(pow_2[i]);
  68. }
  69. int n,m,k;
  70. cin >> n >>m >> k;
  71. for(int i=1;i<=n;++i){
  72. cin >> val[i];
  73. }
  74. for(int i=1;i<=k;++i){
  75. cin >> s[i];
  76. }
  77. for(int i=1;i<=m;++i){
  78. int a,b;
  79. cin >> a >> b;
  80. g[a].pb(b);
  81. g[b].pb(a);
  82. }
  83.  
  84. for(int i=1;i<=k;++i){
  85. used[s[i]] = 1;
  86. }
  87. for(int i=1;i<=k;++i){
  88. int v = s[i];
  89. if(check[v])
  90. continue;
  91. check[v] = 1;
  92. for(int to:g[v]){
  93. if(!used[to]){
  94. if(val[to]==0)
  95. continue;
  96. cout << -1<<"\n";
  97. return;
  98. }
  99. if(sz(g[to])>=block){
  100. to_big[v].pb(to);
  101. }
  102. }
  103. }
  104.  
  105. memset(used,0,sizeof used);
  106. for(int i=1;i<=n;++i){
  107. p1[i] = 0;
  108. q1[i] = 1;
  109. }
  110.  
  111. for(int i=1;i<=k;++i){
  112. int v = s[i];
  113. for(int e=0;e<sz(to_big[v]);++e){
  114. int to = to_big[v][e];
  115. cnt[v]+=inc[to] - add_last[v][e];
  116. add_last[v][e] = inc[to];
  117. }
  118. if(sz(g[v])>=block){ // BIG
  119. inc[v]++;
  120. } else{ // SMALL
  121. for(int to:g[v]){
  122. cnt[to]++;
  123. }
  124. }
  125. used[v]++;
  126. if(cnt[v]==0){
  127. continue;
  128. }
  129. dout << i <<" "<<cnt[v]<<endl;
  130. ll p2 = mul(cnt[v],val[v]);
  131. ll q2 = pow_2[used[v]-1];
  132. dout <<"add "<<p2 <<" "<<q2<<endl;
  133. add(p1[v],q1[v],p2,q2);
  134.  
  135. cnt[v] = 0;
  136. }
  137.  
  138. ll p = 0, q = 1;
  139. for(int i=1;i<=n;++i){
  140. add(p,q,p1[i],q1[i]);
  141. p1[i] = 0;
  142. q1[i] = 1;
  143. }
  144. dout << "First "<<endl;
  145. dout << p <<" "<<q<<endl;
  146. dout << mul(p,rev(q))<<endl;
  147.  
  148. for(int i=1;i<=k;++i){
  149. int v = s[i];
  150. for(int e=0;e<sz(to_big[v]);++e){
  151. int to = to_big[v][e];
  152. cnt[v]+=inc[to] - add_last[v][e];
  153. add_last[v][e] = inc[to];
  154. }
  155. if(sz(g[v])>=block){ // BIG
  156. inc[v]++;
  157. } else{ // SMALL
  158. for(int to:g[v]){
  159. cnt[to]++;
  160. }
  161. }
  162. used[v]++;
  163. if(cnt[v]==0){
  164. continue;
  165. }
  166. dout << i <<" "<<cnt[v]<<endl;
  167. ll p2 = mul(cnt[v],val[v]);
  168. ll q2 = pow_2[used[v]-1];
  169. add(p1[v],q1[v],p2,q2);
  170.  
  171. cnt[v] = 0;
  172. }
  173.  
  174. for(int i=1;i<=n;++i){
  175. ll b1 = mul(p1[i],rev(q1[i]));
  176. ll k = rev_pow2[used[i]/2];
  177.  
  178. ll p2 = b1;
  179. ll q2 = (1 - k + MOD)%MOD;
  180. add(p,q,p2,q2);
  181. }
  182. dout << p <<" "<<q<<endl;
  183. cout << mul(p,rev(q))<<endl;
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195. }
  196.  
  197. signed main(){
  198. #ifdef zxc
  199. debug = 1;
  200. freopen("input.txt","r",stdin);
  201. #endif // zxc
  202.  
  203. int t=1;
  204. ios_base::sync_with_stdio(0);
  205. cin.tie(0);
  206. cout.tie(0);
  207. while(t--)
  208. solve();
  209. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement