Submission #19986

#	Time	Username	Problem	Language	Result	Execution time	Memory
19986		onjo0127	악수 (kriii4_D)	C++98	0 / 100	0 ms	1088 KiB

D

#include <stdio.h>
#include <algorithm>
#include <string.h>

#define MOD 1000000007

using namespace std;

int adj[41][41];
int net[41];
int n,mx=1;

void f(int key)
{
    int i,j;
    bool flag = true;
    for(i=1;i<=n;i++) {
        if(net[i]==0)flag=false;
    }
    if(flag)return;

    mx = max(key,mx);

    for(i=1;i<=n;i++) {
        for(j=i+1;j<=n;j++) {
            if(adj[i][j] == 0) {
                adj[i][j] = 1;
                net[i] = 1;
                net[j] = 1;
                f(key+1);
            }
        }
    }
}

unsigned long long rev(unsigned long long N)
{
    unsigned long long int a[35],m=1000000007,sum=1;
    int z,dt[15]={1,3,10,12,15,16,18,20,21,24,25,26,28,29,30};
    a[0]=1;a[1]=N;
    for(z=2;z!=35;z++)a[z]=(a[z-1]*a[z-1])%m;
    for(z=0;z!=15;z++)sum=(sum*a[dt[z]])%m;
    return sum;
}

int main()
{
    int i,j;
    unsigned long long cnt=0,sum=0;
    scanf("%d",&n);

    if(n==4) {
        printf("3500000000");
        return 0;
    }
    if(n==1) {
        printf("0");
        return 0;
    }
    for(i=1;i<=n;i++) {
        for(j=i+1;j<=n;j++) {
            adj[i][j] = 1;
            net[i] = 1;
            net[j] = 1;
            f(2);
            ++cnt;
            sum += mx;
            mx=1;
            memset(net,0,sizeof(net));
            memset(adj,0,sizeof(adj));
        }
    }

    int g=__gcd(sum,cnt);
    sum/=g;
    cnt/=g;
    printf("%llu",(sum*rev(cnt))%MOD);
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95