oj.uz

Submission #7673

# Submission time Handle Problem Language Result Execution time Memory
7673 2014-08-13T16:14:03 Z moonrabbit2 경비원 (GA8_guard) C++
0 / 100
 468 ms 25520 KB 
#include <cstdio>
#include <algorithm>
#define N 1000000007
using namespace std;
int n;
int a[2500];
int b[2500][2500];
int check[2500];
bool checks=true;
int sum,s,sum2;
int gcd(int a,int b)
{
    if(a%b==0)return b;
    return gcd(b,a%b);
}
int ncr(int n,int r)
{
    int i;
    double b=1;
    for(i=1;i<=r;i++)
        b*=(n-i+1)/(double)i;
    return (int)b;
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(check[a[i]])checks=false;
        check[a[i]]=1;
    }
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(i==j)continue;
            if(gcd(a[i],a[j])!=1){
                b[i][j]=1;
                s++;
            }
        }
    }
    for(i=2;i<=n;i++){
        sum+=ncr(n,i);
        sum2+=max(ncr(n,i)-(int)s,0);
        sum2%=N;
    }
    if(checks)sum2=max(0,sum2-s);
    sum2%=N;
    printf("%d",max(sum-s*s,0));
    return 0;
}

Subtask #1
0.0 / 8.0

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

Subtask #2
0.0 / 13.0

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

Subtask #3
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 276 ms 25520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 460 ms 25520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 468 ms 25520 KB Output isn't correct
2 Halted 0 ms 0 KB -