QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#740311 | #9619. 乘积,欧拉函数,求和 | jr_zch | WA | 104ms | 6088kb | C++14 | 1.7kb | 2024-11-13 08:47:53 | 2024-11-13 08:47:54 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e3+7,maxp=5e2+7,maxs=1<<16,mod=998244353;
const int p[60]={0,2,3,5,7,11,13,17,23,29,31,37,41,43,47,51,53};
int n,ans;
int a[maxn],w[maxn],f[maxp][maxs],g[maxs],h[maxs];
vector<int> big;
vector<int> e[maxn];
/*
f[i+1][s] <- f[i][s]
f[i+1][s^w[i+1]] <- f[i][s]*a[i+1]
*/
int _mod(int x){
return x>=mod?x-mod:x;
}
int qpow(int x,int y){
if(!y) return 1;
if(y==1) return x;
int val=qpow(x,y>>1ll);
if(y&1ll) return val*val%mod*x%mod;
else return val*val%mod;
}
void calc(int x){
int now=x;
for(int i=1;i<=16;i++){
if(!(now%p[i])){
w[x]|=1<<i-1;
while(!(now%p[i])) now/=p[i];
}
}
e[now].push_back(x);
big.push_back(now);
return ;
}
signed main(){
for(int s=0;s<maxs;s++){
h[s]=1;
for(int i=0;i<16;i++){
if(s&1<<i) h[s]=h[s]*(p[i+1]-1)%mod*qpow(p[i+1],mod-2)%mod;
}
}
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(!w[a[i]]) calc(a[i]);
}
sort(big.begin(),big.end());
big.erase(unique(big.begin(),big.end()),big.end());
int tot=big.size();
f[0][0]=1;
for(int i=0;i<tot;i++){
int num=big[i];
int mul=(num-1)*qpow(num,mod-2)%mod;
if(num==1) mul=1;
for(int s=0;s<maxs;s++) g[s]=f[i][s]*mul%mod;
for(int j=0;j<e[num].size();j++){
int val=e[num][j];
for(int s=maxs-1;s>=0;s--){
g[s^w[val]]=(g[s^w[val]]+g[s]*val)%mod;
}
}
for(int s=0;s<maxs;s++) f[i+1][s]=(f[i][s]+g[s]-f[i][s]*mul%mod+mod)%mod;
}
for(int s=0;s<maxs;s++) ans=(ans+f[tot][s]*h[s])%mod;
// printf("test:%lld\n",f[1][3]);
printf("%lld",ans);
return 0;
}
/*
input:
3
1 2 3
output:
12
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 104ms
memory: 6088kb
input:
5 1 6 8 6 2
output:
2544
result:
wrong answer 1st lines differ - expected: '892', found: '2544'