虽然说A simple problem但好像不是很simple的样子..

题意:

给你n个点的一个空图,你一共进行n次操作

第i次操作你将在i号点和一个随机点之间连一条边,可能有重边或自环

问:期望有多少个点是割点,即把这个点吃掉后连通块个数会增多

嗯..

把答案乘以[tex]n^n[/tex]后modo 1,000,000,007即可

所以..

这题是个很果断的数学题..又是数学题..

我们思考

到底什么样的点是割点?

假设某个点的度数>=3,或者度数>=2且不在一个环上,那么就是一个割点?

似乎好有道理的样子..我们来反过来看看哪些点不是割点吧

如果某个点:

1,如果度数为1,显然不是割点(把它吃了不影响)

2,如果是个自环,显然不是割点(把它吃了连通块-1)

3,如果是个自环,并除了自环度数为1,显然不是割点(同1,吃了不影响)

4,如果这个点在一个环上,并且度数为2,那么它不是割点(吃了以后,环还是可以连通的)

我们枚举环的长度即可

那么答案就是

[tex]n*(n^n-(n-1)^n-(n-1)^{n-1}-(n-1)^{n-2}*(n-1)-\sum_{i=2}^{n}(n-1)^{n-i}*P_{n-1}^{i-1})[/tex]

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int modo=1000000007;
int power(int x,int y)
{
    if (y==0) return 1;
    int t=power(x,y/2);
    t=(long long)t*t%modo;
    if (y%2==1) t=(long long)t*x%modo;
    return t;
}
int fact[100005];
int antifact[100005];
int main()
{
    #ifdef absi2011
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    int i;
    fact[0]=1;
    for (i=1;i<=100000;i++)
    {
        fact[i]=(long long)fact[i-1]*i%modo;
    }
    antifact[100000]=power(fact[100000],modo-2);
    for (i=99999;i>=0;i--)
    {
        antifact[i]=(long long)antifact[i+1]*(i+1)%modo;
    }
    for (zu=0;zu<t;zu++)
    {
        int n;
        scanf("%d",&n);
        int ans=(long long)n*power(n,n)%modo;
        ans=(ans-power(n-1,n)*(long long)n%modo)%modo;
        ans=(ans-power(n-1,n-1)*(long long)n%modo)%modo;
        ans=(ans-power(n-1,n-2)*(long long)(n-1)%modo*n%modo)%modo;
        int val=1;
        for (i=n;i>=2;i--)
        {
            ans=(ans-(long long)val*fact[n-1]%modo*antifact[n-i]%modo*n%modo)%modo;
            val=(long long)val*(n-1)%modo;
        }
        printf("Case #%d: %d\n",zu+1,(ans+modo)%modo);
    }
    return 0;
}