QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#79905 | #3724. Strange Prime | H_zwei | AC ✓ | 109ms | 5836kb | C++17 | 5.2kb | 2023-02-21 10:00:23 | 2023-02-21 10:00:23 |
Judging History
answer
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC target("avx,avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("Ofast,fast-math")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#include<iostream>
//#include<string>
//#include<cmath>
//#include<cstdio>
//#include<cctype>
//#include<cstring>
//#include<iomanip>
//#include<cstdlib>
//#include<ctime>
//#include<set>
//#include<map>
//#include<utility>
//#include<queue>
//#include<vector>
//#include<stack>
//#include<sstream>
//#include<algorithm>
using namespace std;
/*=====================================================================*/
#define ll long long
#define int ll
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pdd pair<double,double>
#define ull unsigned long long
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(s) (s).begin(),(s).end()
#define repd(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define forr(i,a,b,c) for(int i=(int)(a);i<=(int)(b);i+=(int)(c))
#define forn(i,p,n) for(int i=(int)(p);i<=(int)(n);++i)
#define ford(i,p,n) for(int i=(int)(n);i>=(int)(p);--i)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();++i)
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define Endl(x) cout<<x<<endl;
#define Blank(x) cout<<x<<" ";
#define modcg(x) if(x>=mod)x-=mod;
#define modcl(x) if(x<0)x+=mod;
#define lowbit(x) x&(-x)
/*=====================================================================*/
string int_to_string(ll n)
{
string s="";
while(n)
{
ll now=n%10;
s+=now+'0';
n/=10;
}
reverse(s.begin(),s.end());
return s;
}
ll string_to_int(string s)
{
ll n=0;
rep(i,s.size())
{
n*=10;
n+=s[i]-'0';
}
return n;
}
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
int Rand(int l,int r)
{
uniform_int_distribution<>RAND1(l,r);
return RAND1(gen);
}
/*======================================================================*/
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
const int month[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};
//think twice,code once
//think once,debug forever
const int MAXN=1e5+10,p=999999956,mod=1e9+7;
int a[MAXN];
int n;
int dp[MAXN][2];
int quickpower(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
{
res*=a;
res%=mod;
}
a*=a;
a%=mod;
b>>=1;
}
return res;
}
int inv(int x)
{
return quickpower(x,mod-2);
}
int f[MAXN][2];
void solve()
{
int all=1;
forn(i,1,n)
{
cin>>a[i];
all*=a[i];
all%=mod;
}
f[0][0]=1;
forn(i,1,n)
{
f[i][0]=f[i-1][1]*a[i]%mod+f[i-1][0]*p%mod;
modcg(f[i][0]);
f[i][1]=f[i-1][0]*a[i]%mod+f[i-1][1]*p%mod;
modcg(f[i][1]);
// cout<<f[i][0]<<" "<<f[i][1]<<endl;
}
int ans=f[n][0]-f[n][1];
modcl(ans);
// cout<<ans<<endl;
ans-=all;
modcl(ans);
ans*=inv(p);
ans%=mod;
cout<<ans<<endl;
}
/*======================================================================*/
signed main()
{
cin.tie(0);
cout.tie(0);
std::ios::sync_with_stdio(false);
//#define Hank2007
#ifdef Hank2007
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
/*====================================================================*/
// int TEST_CASE=1;
// cin>>TEST_CASE;
while(cin>>n)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 109ms
memory: 5836kb
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:
8747181 109223012 855771490 541976436 590061154 362989597 987338731 316507988 571293823 811262072 971678511 475746045 438611414 341241863 155506989 174497292 470085592 844919405 114498965 739370426 38587099 214008686 506810838 254574502 480440711 792847181 303917854 79001517 310250674 834963010 1907...
result:
ok 11305 numbers