cf711D 成环的和不成环的要单独计算, 环用双联通做的 QAQ
- /*
- 所有情况 - 成环的情况
- */
- #include<bits/stdc++.h>
- using namespace std;
- #define maxn 200005
- #define mod 1000000007
- #define ll long long
- struct Edge{int to,nxt;}edge[maxn<<1];
- int n,head[maxn],tot;
- ll ans;
- void init(){
- memset(head,-1,sizeof head);
- tot=0;
- }
- void addedge(int u,int v){
- edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;
- }
- ll Pow(ll a,ll b){
- ll res=1;
- while(b){
- if(b%2)res=(res*a)%mod;
- b>>=1;a=a*a%mod;
- }
- return res;
- }
- int dfn[maxn],low[maxn],ind,bridge[maxn<<1];
- void tarjan(int x,int in_edge){
- dfn[x]=low[x]=++ind;
- for(int i=head[x];i!=-1;i=edge[i].nxt){
- int y=edge[i].to;
- if(!dfn[y]){
- tarjan(y,i);
- low[x]=min(low[x],low[y]);
- if(low[x]<low[y])bridge[i]=bridge[i^1]=1;
- }
- else if(i!=(in_edge^1))
- low[x]=min(low[x],dfn[y]);
- }
- }
- int c[maxn],size[maxn],dcc;
- void dfs(int u){
- c[u]=dcc;size[dcc]++;
- for(int i=head[u];i!=-1;i=edge[i].nxt){
- int v=edge[i].to;
- if(c[v]||bridge[i])continue;
- dfs(v);
- }
- }
- int main(){
- init();
- ans=1;
- cin>>n;
- int v,cnt=0;
- for(int u=1;u<=n;u++){
- cin>>v;
- addedge(u,v);addedge(v,u);
- }
- for(int i=1;i<=n;i++)
- if(!dfn[i])tarjan(i,0);
- // 染色
- for(int i=1;i<=n;i++)
- if(!c[i]){++dcc;dfs(i);}
- for(int i=1;i<=dcc;i++){
- if(size[i]==1)cnt++;
- else ans=ans*(Pow(2,size[i])-2)%mod;
- }
- ans=ans*Pow(2,cnt)%mod;
- cout<<ans;
- return 0;
- }
- View Code
cf340B 开始推公式了
- /*
- 数组 a 组成的全排列
- 求差值之和
- 显然 | ai-aj | 出现的次数是 (n-1)! 次
- 那么答案就是 sum|si-sj| / n
- 怎么求 sum|si-sj|?
- 排个序, 然后用前缀和求即可
- 8-4+2+1+2+3=4+8=12+12
- */
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define maxn 200005
- ll tot,n,a[maxn],sum[maxn];
- int main(){
- cin>>n;
- for(int i=1;i<=n;i++)cin>>a[i];
- sort(a+1,a+1+n);
- for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
- for(int i=1;i<=n;i++){
- tot+=sum[n]-sum[i]-a[i]*(n-i);
- tot+=a[i]*(i-1)-sum[i-1];
- }
- //tot*=2;
- tot+=sum[n];
- ll d=__gcd(n,tot);
- cout<<tot/d<<" "<<n/d<<endl;
- }
- View Code
cf500D 开始在树上推公式了, 要注意最后用 double..ll 不知道为什么会炸...
- /*
- 找出所有路径然后求平均值
- 就是 sum|(d(a,b)+d(b,c))*2|/C(n,3)
- 如何求 sum,
- 边 < u,v > 的贡献次数是
- cnt=C(size[u],2)*C(n-size[u]-1,1)+C(size[u],1)*C(n-size[u]-1,2)
- 其贡献是 cnt*2*w
- */
- #include<bits/stdc++.h>
- using namespace std;
- #define maxn 300005
- #define ll long long
- struct Edge{int to,nxt;}edge[maxn<<1];
- struct E{int u,v,w;}e[maxn];
- int head[maxn],tot,n;
- double F;
- void init(){
- memset(head,-1,sizeof head);
- tot=0;
- F=1;
- F=((double)n*(n-1)*(n-2))/6;
- }
- void addedge(int u,int v){
- edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;
- }
- ll size[maxn];
- void dfs(int u,int pre){
- size[u]=1;
- for(int i=head[u];i!=-1;i=edge[i].nxt){
- int v=edge[i].to;
- if(v==pre)continue;
- dfs(v,u);size[u]+=size[v];
- }
- }
- ll cnt[maxn];
- ll C(ll a,ll b){
- if(a<b)return 0;
- if(b==1)return a;
- if(b==2)return (ll)a*(a-1)/2;
- }
- int main(){
- cin>>n; init();
- for(int i=1;i<n;i++){
- cin>>e[i].u>>e[i].v>>e[i].w;
- addedge(e[i].u,e[i].v);
- addedge(e[i].v,e[i].u);
- }
- dfs(1,0);
- for(int i=1;i<n;i++){
- int u=e[i].u,v=e[i].v;
- if(size[u]>size[v])swap(u,v);
- cnt[i]=(ll)C(size[u],2)*C(n-size[u],1)+(ll)C(size[u],1)*C(n-size[u],2);
- }
- double sum=0;
- for(int i=1;i<n;i++)
- sum+=(double)cnt[i]*2*e[i].w;
- //cout<<sum;
- int q;
- cin>>q;
- while(q--){
- int id,w;
- cin>>id>>w;
- sum+=(double)(-(cnt[id]*2*e[id].w)+(cnt[id]*2*w));
- e[id].w=w;
- printf("%lf\n",sum/F);
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-3011911.html