QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#741433#9619. 乘积,欧拉函数,求和ucup-team4479#ML 2ms7716kbC++231.8kb2024-11-13 14:21:262024-11-13 14:21:30

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 14:21:30]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:7716kb
  • [2024-11-13 14:21:26]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=2005,M=16;
constexpr int MOD=998244353;
constexpr int prime[M]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int n;
int a[N],ret[N];
int id[N];
int state[N];
int f[N][1<<M][2];
void calc(int l,int r)
{
    for(int i=l;i<=r;i++)
    {
        int u=id[i];
        for(int j=0;j<(1<<M);j++)
            f[i][j][0]=f[i-1][j][0],f[i][j][1]=f[i-1][j][1];
        for(int j=0;j<(1<<M);j++)
            for(int o=0;o<=1;o++)
                if(f[i-1][j][o])
                {
                    int x=a[u];
                    int k=j|state[u];
                    for(int l=0;l<M;l++)
                        if(!((j>>l)&1)&&((k>>l)&1))
                        {
                            x=x*(prime[l]-1)/prime[l];
                        }
                    if(o==0&&ret[u]>1) x=x*(ret[u]-1)/ret[u];
                    f[i][k][1]=(f[i][k][1]+(long long)f[i-1][j][o]*x)%MOD;
                }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        int x=a[i];
        for(int j=0;j<M;j++)
            if(x%prime[j]==0)
            {
                while(x%prime[j]==0) x/=prime[j];
                state[i]|=1<<j;
            }
        ret[i]=x;
    }
    iota(id+1,id+n+1,1);
    sort(id+1,id+n+1,[&](const int &x,const int &y){return ret[x]<ret[y];});
    f[0][0][0]=1;
    for(int i=1,j=1;i<=n;i=j)
    {
        while(j<=n&&ret[id[i]]==ret[id[j]]) j++;
        calc(i,j);
        for(int s=0;s<(1<<M);s++)
            f[j-1][s][0]=(f[j-1][s][0]+f[j-1][s][1])%MOD,f[j-1][s][1]=0;
    }
    int ans=0;
    for(int j=0;j<(1<<M);j++)
        ans=(ans+f[n][j][0])%MOD;
    cout<<ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7588kb

input:

5
1 6 8 6 2

output:

892

result:

ok single line: '892'

Test #2:

score: 0
Accepted
time: 2ms
memory: 7716kb

input:

5
3 8 3 7 8

output:

3157

result:

ok single line: '3157'

Test #3:

score: -100
Memory Limit Exceeded

input:

2000
79 1 1 1 1 1 1 2803 1 1 1 1 1 1 1609 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2137 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 613 1 499 1 211 1 2927 1 1 1327 1 1 1123 1 907 1 2543 1 1 1 311 2683 1 1 1 1 2963 1 1 1 641 761 1 1 1 1 1 1 1 1 1 1 1 1489 2857 1 1 1 1 1 1 1 1 1 1 1 1 1 967 1 821 1 1 1 1 2143 1861...

output:

50965652

result: