NC19426. 简单
描述
输入描述
第一行三个整数 n,m,q,分别表示点的个数和边的个数和询问次数。
之后 n 行,第 i+1 行有两个整数 ai,bi,表示第 i 个点存在的概率是 。
之后 m 行,每行有两个整数 u,v,表示存在一条连接 u 和 v 的边,保证无重边无自环。
之后 q 行,每行两个整数 [l,r],表示一次询问。
输出描述
对于每一次询问,输出一行一个整数表示答案,输出对 109+7 取模。
示例1
输入:
2 1 1 1 1 1 1 1 2 1 2
输出:
1
说明:
一共就俩点,都一定存在,所以连接它们的这条边一定存在,所以这俩点构成的图的连通块个数一定是 1示例2
输入:
5 4 5 1 1 1 1 2 3 1 2 1 1 3 4 4 5 3 2 3 1 1 2 1 3 2 5 1 2 1 3
输出:
2 333333337 666666673 2 333333337
示例3
输入:
10 9 10 2922 17409 11774 17075 4095 19350 5213 7090 21155 26703 9167 16671 257 1197 201 308 13874 27985 12034 32560 1 6 1 9 6 5 6 4 1 10 4 3 4 2 10 7 6 8 2 3 3 9 1 3 2 2 2 6 3 5 2 2 3 5 5 8 4 4
输出:
613369885 419229271 380731593 15695462 543771231 562072744 15695462 562072744 891100707 526234137
说明:
(以下内容与本题无关)C++14(g++5.4) 解法, 执行用时: 459ms, 内存消耗: 6764K, 提交时间: 2019-09-10 23:01:03
//https://ac.nowcoder.com/acm/contest/275/G #include<bits/stdc++.h> using namespace std; #define ll long long const int mod=1e9+7; const int N=1e5+100; ll a[N]; ll c[N],p[N],ans[N]; int n,m,k; struct edge { int l,r; ll w; bool operator<(const edge &x)const { return r<x.r; } }e[N]; struct node { int l,r,id; bool operator<(const node &x) const { return r<x.r; } }q[N]; ll qpow(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=(ans*a)%mod; a=a*a%mod; b>>=1; } return ans; } void add(int x,ll v) { while(x<=n) { c[x]=(c[x]+v)%mod; x+=x&-x; } } ll getsum(int x) { ll ans=0; while(x) { ans=(ans+c[x])%mod; x-=x&-x; } return ans; } int main() { cin>>n>>m>>k; for(int i=1;i<=n;i++) { ll x,y; cin>>x>>y; a[i]=x*qpow(y,mod-2)%mod; p[i]=(p[i-1]+a[i])%mod; } for(int i=1;i<=m;i++) { cin>>e[i].l>>e[i].r; if(e[i].l>e[i].r) swap(e[i].l,e[i].r); e[i].w=a[e[i].l]*a[e[i].r]%mod; } for(int i=1;i<=k;i++) cin>>q[i].l>>q[i].r,q[i].id=i; sort(q+1,q+1+k); sort(e+1,e+m+1); int j=1; for(int i=1;i<=k;i++) { while(j<=m&&e[j].r<=q[i].r) { add(e[j].l,e[j].w); j++; } ll x=(getsum(q[i].r)-getsum(q[i].l-1)+mod)%mod; ans[q[i].id]=(p[q[i].r]-p[q[i].l-1]+mod-x+mod)%mod; } for(int i=1;i<=k;i++) cout<<ans[i]<<endl; return 0; }
C++ 解法, 执行用时: 121ms, 内存消耗: 11668K, 提交时间: 2021-11-27 17:08:21
#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; struct node { int l,r,id; }Q[100005]; bool cmp(node a,node b) { return a.r<b.r; } vector<int>R[100005],W[100005]; int i,j,k,n,m,q,P[100005],S[100005]={0},pre[100005]={0},ans[100005]; long long fastpow(long long a,int b) { long long s=1; for(;b;b>>=1,a=a*a%mod)if(b&1)s=s*a%mod; return s; } int lowbit(int x) { return x&(-x); } void update(int i,int x) { while(i<=n)S[i]=(S[i]+x)%mod,i+=lowbit(i); } long long getsum(int i) { int s=0; while(i)s=(s+S[i])%mod,i-=lowbit(i); return s; } int main() { scanf("%d%d%d",&n,&m,&q); for(i=1;i<=n;i++) { scanf("%d%d",&j,&k); P[i]=j*fastpow(k,mod-2)%mod,pre[i]=(pre[i-1]+P[i])%mod; } while(m--) { scanf("%d%d",&i,&j); if(i<j)swap(i,j); R[i].push_back(j),W[i].push_back((long long)P[i]*P[j]%mod); } for(i=0;i<q;i++)scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i; sort(Q,Q+q,cmp); for(i=1,j=0;i<=n;i++) { for(k=0;k<R[i].size();k++)update(R[i][k],W[i][k]); for(;j<q&&Q[j].r<=i;j++)ans[Q[j].id]=(pre[i]-pre[Q[j].l-1]-getsum(i)+getsum(Q[j].l-1)+2*mod)%mod; } for(i=0;i<q;i++)printf("%d\n",ans[i]); return 0; }