cf711D 成环的和不成环的要单独计算，环用双联通做的QAQ

/*所有情况-成环的情况 */#include
      
       using namespace std;#define maxn 200005#define mod 1000000007#define ll long longstruct 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]
       
        >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<
       
      

cf340B 开始推公式了

/*数组a组成的全排列求差值之和显然|ai-aj|出现的次数是(n-1)!次那么答案就是sum|si-sj| / n怎么求sum|si-sj|?排个序，然后用前缀和求即可  8-4+2+1+2+3=4+8=12+12*/#include
      
       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<
      

cf500D开始在树上推公式了，要注意最后用double。。ll不知道为什么会炸。。。

/*找出所有路径然后求平均值就是sum|(d(a,b)+d(b,c))*2|/C(n,3)如何求sum，边
      
       的贡献次数是    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
       
        using namespace std;#define maxn 300005#define ll long longstruct 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
        
         >n;    init();    for(int i=1;i
         
          >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
          
           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
           
            >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); }}
           
          
         
        
       
      

 cf150B 又是回文串拆分成奇偶串的题。。需要特判一些情况

/*若k==n，那么就是可以组成的回文的个数 m^(n/2) k=1或k是偶数:全等 k是奇数：分奇偶串后全等即可 */#include
      
       using namespace std;#define mod 1000000007#define ll long longll n,m,k;ll Pow(ll a,ll b){    ll c=1;    while(b){        if(b%2)c=c*a%mod;        b>>=1;a=a*a%mod;    }    return c;}int main(){    cin>>n>>m>>k;    if(k==1 || k>n){        cout<<(ll)Pow(m,n);        return 0;    }    if(k
      

cf626D 好题！求c1+c2<c3的对数，由于数值较小，所以开个桶完美解决！

/*显然有C(n,2)中选球组合我们另第i中选球组合选出的求权值为(ai,bi)那么选三次后要使得第二个人的总权值大于第一个人    即a1+a2+b3
      
       using namespace std;#define maxn 5005#define ll long longll n,a[maxn],cnt[maxn],sum[maxn<<1];int main(){    double F=1;    cin>>n;    F=n*(n-1)/2;F=F*F*F;    for(int i=1;i<=n;i++)cin>>a[i];    for(int i=1;i
      

cf272D 难点在于m不是个质数，不用逆元的话要用别的办法转化一下消去2即可

/*统计每列的点数量用乘法原理处理列间即可，注意还要除以每列中相同的点的情况因为一列中完全相同的点最多是2 2x=1(%m)*/#include
      
       #include