Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<int,int> pii;
- #define fi first
- #define se second
- #define sz(a) ((int)a.size())
- #define pb push_back
- #define int ll
- const int inf_int = 1e9;
- const ll inf_ll = 1e18;
- const int MAXN = 2e5+100;
- const int MOD = 1e9+7;
- bool debug = 0;
- #define dout if(debug) cout
- vector<int> g[MAXN];
- vector<int> to_big[MAXN];
- ll val[MAXN];
- int s[MAXN];
- int used[MAXN];
- int check[MAXN];
- int block = 500;
- int cnt[MAXN]; // for all
- int inc[MAXN]; // for big
- inline void add(ll &p1,ll &q1,ll p2,ll q2){
- p1 = (p1*q2 + p2 * q1)%MOD;
- q1 = (q1 * q2)%MOD;
- }
- ll pow_2[MAXN];
- ll rev_pow2[MAXN];
- int add_last[MAXN][210];
- ll binpow(ll a, int n) {
- ll res = 1;
- while (n) {
- if (n & 1){
- res = (res * a)%MOD;
- }
- a = (a*a)%MOD;
- n >>= 1;
- }
- return res;
- }
- inline ll rev(ll x){
- return binpow(x,MOD-2);
- }
- inline ll mul(ll a,ll b){
- return (a*b)%MOD;
- }
- ll p1[MAXN],q1[MAXN];
- void solve(){
- pow_2[0] = 1;
- for(int i=1;i<MAXN;++i){
- pow_2[i] = (pow_2[i-1]*2)%MOD;
- }
- for(int i=0;i<MAXN;++i){
- rev_pow2[i] = rev(pow_2[i]);
- }
- int n,m,k;
- cin >> n >>m >> k;
- for(int i=1;i<=n;++i){
- cin >> val[i];
- }
- for(int i=1;i<=k;++i){
- cin >> s[i];
- }
- for(int i=1;i<=m;++i){
- int a,b;
- cin >> a >> b;
- g[a].pb(b);
- g[b].pb(a);
- }
- for(int i=1;i<=k;++i){
- used[s[i]] = 1;
- }
- for(int i=1;i<=k;++i){
- int v = s[i];
- if(check[v])
- continue;
- check[v] = 1;
- for(int to:g[v]){
- if(!used[to]){
- if(val[to]==0)
- continue;
- cout << -1<<"\n";
- return;
- }
- if(sz(g[to])>=block){
- to_big[v].pb(to);
- }
- }
- }
- memset(used,0,sizeof used);
- for(int i=1;i<=n;++i){
- p1[i] = 0;
- q1[i] = 1;
- }
- for(int i=1;i<=k;++i){
- int v = s[i];
- for(int e=0;e<sz(to_big[v]);++e){
- int to = to_big[v][e];
- cnt[v]+=inc[to] - add_last[v][e];
- add_last[v][e] = inc[to];
- }
- if(sz(g[v])>=block){ // BIG
- inc[v]++;
- } else{ // SMALL
- for(int to:g[v]){
- cnt[to]++;
- }
- }
- used[v]++;
- if(cnt[v]==0){
- continue;
- }
- dout << i <<" "<<cnt[v]<<endl;
- ll p2 = mul(cnt[v],val[v]);
- ll q2 = pow_2[used[v]-1];
- dout <<"add "<<p2 <<" "<<q2<<endl;
- add(p1[v],q1[v],p2,q2);
- cnt[v] = 0;
- }
- ll p = 0, q = 1;
- for(int i=1;i<=n;++i){
- add(p,q,p1[i],q1[i]);
- p1[i] = 0;
- q1[i] = 1;
- }
- dout << "First "<<endl;
- dout << p <<" "<<q<<endl;
- dout << mul(p,rev(q))<<endl;
- for(int i=1;i<=k;++i){
- int v = s[i];
- for(int e=0;e<sz(to_big[v]);++e){
- int to = to_big[v][e];
- cnt[v]+=inc[to] - add_last[v][e];
- add_last[v][e] = inc[to];
- }
- if(sz(g[v])>=block){ // BIG
- inc[v]++;
- } else{ // SMALL
- for(int to:g[v]){
- cnt[to]++;
- }
- }
- used[v]++;
- if(cnt[v]==0){
- continue;
- }
- dout << i <<" "<<cnt[v]<<endl;
- ll p2 = mul(cnt[v],val[v]);
- ll q2 = pow_2[used[v]-1];
- add(p1[v],q1[v],p2,q2);
- cnt[v] = 0;
- }
- for(int i=1;i<=n;++i){
- ll b1 = mul(p1[i],rev(q1[i]));
- ll k = rev_pow2[used[i]/2];
- ll p2 = b1;
- ll q2 = (1 - k + MOD)%MOD;
- add(p,q,p2,q2);
- }
- dout << p <<" "<<q<<endl;
- cout << mul(p,rev(q))<<endl;
- }
- signed main(){
- #ifdef zxc
- debug = 1;
- freopen("input.txt","r",stdin);
- #endif // zxc
- int t=1;
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- while(t--)
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement