Submission #7591

#	Time	Username	Problem	Language	Result	Execution time	Memory
7591		dohyun0324	경비원 (GA8_guard)	C++98	37 / 100	380 ms	1372 KiB

guard

#include<stdio.h>
int cnt,n,a[2510],m,ch[30],w,b[2510],cnt2;
long long int dap,d[2][17000];
int p[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43};
int gcd(int x,int y)
{
    if(x%y==0) return y;
    return gcd(y,x%y);
}
void dfs(int x)
{
    int i;
    if(x==n)
    {
        if(w>=2)
        {
            cnt++;
        }
        return;
    }
    dfs(x+1);
    for(i=1;i<=w;i++)
    {
        if(gcd(ch[i],a[x+1])!=1) break;
    }
    if(i!=w+1) return;
    ch[++w]=a[x+1];
    dfs(x+1);
    ch[w--]=0;
}
int main()
{
    int i,j,s;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(m<a[i]) m=a[i];
        if(a[i]==1) cnt2++;
    }
    //subtask 1,2
    if(n<=44)
    {
        dfs(1);
        ch[++w]=a[1];
        dfs(1);
        printf("%d",cnt);
    }
    //subtask 3
    else
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=14;j++)
            {
                if(a[i]%p[j]==0) b[i]+=(1<<(j-1));
            }
        }
        d[1][b[1]]=1;
        for(i=2;i<=n;i++)
        {
            for(j=0;j<1<<14;j++) d[i%2][j]=0;
            d[i%2][b[i]]++;
            for(j=0;j<1<<14;j++)
            {
                d[i%2][j]+=d[(i-1)%2][j];
            }
            for(j=0;j<1<<14;j++)
            {
                if((j&b[i])!=0) continue;
                d[i%2][j|b[i]]+=d[(i-1)%2][j];
                d[i%2][j|b[i]]%=1000000007;
            }
        }
        for(i=0;i<1<<14;i++)
        {
            dap+=d[n%2][i];
            dap%=1000000007;
        }
        dap-=n;
        if(dap<0) dap+=1000000007;
        printf("%lld",dap);
    }
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 0 / 27
• Subtask 5: 0 / 36