QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#79658#3724. Strange PrimeQVQWA 271ms3804kbC++141023b2023-02-20 18:53:552023-02-20 18:53:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-20 18:53:58]
  • 评测
  • 测评结果:WA
  • 用时:271ms
  • 内存:3804kb
  • [2023-02-20 18:53:55]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll P=10000000019;
const int mod=1e9+7;
const int N=1e5+5;
ll ksm(ll x,ll y)
{
	if(!y)return 1;
	ll res=ksm(x,y/2);
	res=res*res%mod;
	if(y%2)res=res*x%mod;
	return res;
}
int n,a[N];ll inv;
void solve()
{
	if(n==1){
		cin>>n;
		cout<<1<<"\n";
		return;
	}
	ll ans,cur=ksm(P%mod,n-1);ans=cur;cur=1;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];cur=cur*a[i]%mod;
		ll val=ans*inv%mod*a[i]%mod;
		ans=(ans-val+mod)%mod;
	}
	if(n%2==0)ans=(ans-cur+mod)%mod;
	else ans=(ans+cur)%mod;
	cout<<ans<<"\n";return;
}
int main(){
	inv=ksm(P%mod,mod-2);
	while(cin>>n)solve();
	/*
	ll ans=0;
	for(int i=0;i<(1<<n)-1;i++)
	{
		int sz=__builtin_popcount(i);
		int tot=n-sz;ll val=1;
		for(int j=0;j<n;j++)
			if((i>>j)&1)
				val=val*a[j]%mod;
		val=val*ksm(P%mod,tot-1)%mod;
	//	cout<<i<<" "<<val<<"##\n";
		if(sz%2==0)ans+=val;
		else ans-=val;
		ans%=mod;
	}ans+=mod;ans%=mod;
	cout<<ans;//<<" "<<P%mod;*/
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 271ms
memory: 3804kb

input:

10
2357 42596 7212 30898 43465 68984 60783 59520 53767 77560
10
39115 88080 83553 61736 90821 39690 13194 81396 38051 55993
10
95070 81321 71632 21071 10807 46105 66844 63678 47577 75132
10
43898 93215 26791 11849 61857 1423 76971 83489 52044 61325
10
22610 16613 90 53598 80110 42651 64942 67114 242...

output:

395733442
976046445
367667297
164676001
13770487
804191412
525832730
279595883
318010713
881218327
602569318
487503400
970913860
383207204
669901797
946684976
16043971
73432466
451561314
887643513
661202322
657750828
301441894
955277197
840096396
625307812
786386094
690347763
947482880
632777321
464...

result:

wrong answer 1st numbers differ - expected: '8747181', found: '395733442'