oj.uz

Submission #19986

# Submission time Handle Problem Language Result Execution time Memory
19986 2016-02-25T08:09:22 Z onjo0127 악수 (kriii4_D) C++
0 / 100
 0 ms 1088 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1088 KB Output is correct
2 Correct 0 ms 1088 KB Output is correct
3 Correct 0 ms 1088 KB Output is correct
4 Incorrect 0 ms 1088 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -