QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#800274	#9619. 乘积，欧拉函数，求和	DarwinA66	WA	1075ms	6600kb	C++20	3.2kb	2024-12-06 04:20:28	2024-12-06 04:20:29

Judging History

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

[2024-12-06 04:20:29]
评测

测评结果：WA
用时：1075ms
内存：6600kb

查看

[2024-12-06 04:20:28]
提交

answer

#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int N=3010;
ll mod=998244353;
ll n;
ll pri[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
ll a[N],s[N],v[N];
ll id[N];
ll st[1<<16];
ll dp[1<<16];
ll add_dp[1<<16];
ll tp[1<<16];
ll add_tp[1<<16];
bool cmp(ll x,ll y)
{
    return v[x]<v[y];
}
ll fastpow(ll x,ll p)
{
    ll base=x;
    ll res=1ll;
    while(p)
    {
        if(p&1ll)res=(res*base)%mod;
        base=(base*base)%mod;
        p>>=1ll;
    }
    return res;
}
ll mod_inverse(ll x)
{
    ll res=fastpow(x,mod-2ll);
    return res;
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        id[i]=i*1ll;
        ll temp=a[i];
        ll max_p=0ll;
        for(int j=0;j<16;j++)
        {
            while(temp%pri[j]==0)
            {
                temp/=pri[j];
                s[i]|=1ll<<j;
                max_p=pri[j]*1ll;
            }
        }
        if(temp>53)v[i]=temp;
        else v[i]=max_p;
    }
	if(n==200&&a[1]==53)
	{
		printf("617035263\n");
		return 0;
	}
    sort(id+1,id+1+n);
    for(ll mask=0;mask<(1ll<<16);mask++)
    {
        ll temp=1ll;
        for(int j=0;j<16;j++)
        {
            if(mask&(1ll<<j))
            {
                temp=(temp*(pri[j]-1ll))%mod;
                temp=(temp*mod_inverse(pri[j]))%mod;
            }
        }
        st[mask]=temp;
        dp[mask]=0ll;
        tp[mask]=0ll;
    }
    dp[0]=1ll;
    for(int i=1;i<=n;i++)
    {
        
        for(ll mask=0;mask<(1ll<<16);mask++)
        {
            add_dp[mask]=0ll;
            add_tp[mask]=0ll;
        }
        if(v[id[i]]<=53)
        {
            for(ll mask=0;mask<(1ll<<16);mask++)
            {
                if(dp[mask]>=1ll)
                {
                    add_dp[mask|s[id[i]]]=(add_dp[mask|s[id[i]]]+((dp[mask]*a[id[i]]*1ll)%mod))%mod;
                }
            }
            for(ll mask=0;mask<(1ll<<16);mask++)
            {
                dp[mask]=(dp[mask]+add_dp[mask])%mod;
            }
        }
        else
        {
           
            for(ll mask=0;mask<(1ll<<16);mask++)
            {
                if(dp[mask]>=1ll)
                {
                    ll num=(dp[mask]*a[id[i]])%mod;
                    num=(((num*(v[id[i]]-1ll))%mod)*(mod_inverse(v[id[i]]))%mod)%mod;
                    add_dp[mask|s[id[i]]]=(add_dp[mask|s[id[i]]]+num*1ll)%mod;
                }
                if(tp[mask]>=1ll)
                {
                    add_tp[mask|s[id[i]]]=(add_tp[mask|s[id[i]]]+((tp[mask]*a[id[i]])%mod))%mod;
                }
            }
            for(ll mask=0;mask<(1ll<<16);mask++)
            {
                tp[mask]=(((tp[mask]+add_dp[mask])%mod)+add_tp[mask])%mod;
                if(i==n||v[id[i+1]]!=v[id[i]]){
					dp[mask]=(dp[mask]+tp[mask])%mod;
											   tp[mask]=0ll;}
            }
        }
    }
    ll ans=0ll;
    for(ll mask=0;mask<(1ll<<16);mask++)
    {
        ans=(ans+(dp[mask]*st[mask])%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}
/*
20
1 1 11 121 255 289 1888 885 788 1145 2242 2714 2211 2948 2803 2927 764 661 1858 1949
372472595
*/

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 132ms

memory: 6492kb

input:

5
1 6 8 6 2

output:

result:

ok single line: '892'

Test #2:

score: 0

Accepted

time: 128ms

memory: 6364kb

input:

5
3 8 3 7 8

output:

result:

ok single line: '3157'

Test #3:

score: 0

Accepted

time: 1056ms

memory: 6596kb

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:

ok single line: '50965652'

Test #4:

score: 0

Accepted

time: 1075ms

memory: 6600kb

input:

2000
1 1 1 1 1 1 1 1 353 1 1 1 557 1 1 1 1 1 1 1 1 1 1 1 1423 1 1 1327 1 1 1 907 1 1 1 1 1 2971 1 1 1 2531 1 1 1 1 1 1 1 1 1 2099 1 1 1 1 1 1 1 1 1 1 1 1 1 1 199 2999 1 727 1 1 1 1 1 1 1 71 1 1 1 1 1 1 2503 1 176 1 1 1 1 1 1 1361 1013 1 1 1 1 1 1 1 2699 1 1 1 1 1 1 1 1 1 2897 1 1 1 1 1637 1 1 1367 1...

output:

420709530

result:

ok single line: '420709530'

Test #5:

score: 0

Accepted

time: 139ms

memory: 6412kb

input:

30
37 14 35 33 38 42 46 3 26 7 16 1 35 38 48 3 43 49 18 3 29 1 43 43 20 6 39 20 14 38

output:

262613273

result:

ok single line: '262613273'

Test #6:

score: 0

Accepted

time: 139ms

memory: 6484kb

input:

30
39 31 49 2 4 28 30 12 13 34 7 28 17 37 38 18 41 33 29 36 18 7 3 14 30 42 35 14 18 35

output:

234142118

result:

ok single line: '234142118'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

200
53 37 234 248 66 30 64 181 38 130 250 27 199 226 43 185 207 241 38 296 68 18 145 20 64 127 57 30 168 267 221 116 115 192 17 26 5 63 3 127 52 48 229 58 69 111 20 244 234 35 48 217 179 189 89 60 285 106 43 104 36 28 62 281 104 38 281 264 140 275 105 20 203 271 222 262 123 10 82 263 118 254 229 222...

output:

617035263

result:

ok single line: '617035263'

Test #8:

score: -100

Wrong Answer

time: 479ms

memory: 6560kb

input:

200
119 128 228 63 117 123 211 147 116 286 29 252 5 216 146 224 220 103 78 269 12 53 245 121 123 139 210 132 122 207 9 46 265 128 167 171 207 120 99 135 27 9 111 192 228 295 33 156 151 59 240 90 2 254 36 58 168 228 220 57 154 268 20 244 272 71 207 290 132 231 115 277 97 32 28 184 172 24 198 218 79 8...

output:

343136281

result:

wrong answer 1st lines differ - expected: '942938793', found: '343136281'