QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#743606 | #9225. Fibonacci Fusion | ucup-team134# | TL | 3332ms | 210860kb | C++14 | 3.0kb | 2024-11-13 19:37:37 | 2024-11-13 19:37:39 |
Judging History
answer
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
typedef long double ld;
const int maxd=2e6+10;
const int maxn=2e5+10;
int n;
const int nmods=2;
int mods[nmods]={998244353, (int)1e9+7};
struct bnum{
bnum(){
for(int i=0;i<nmods;i++){
a[i]=0;
}
}
bnum(string s){
for(int i=0;i<nmods;i++){
mod=mods[i];
a[i]=0;
for(int j=0;j<s.size();j++){
a[i]=mul(a[i],10);
a[i]=add(a[i],s[j]-'0');
}
}
}
bnum operator - (bnum& b){
bnum ret;
for(int i=0;i<nmods;i++){
mod=mods[i];
ret.a[i]=sub(a[i],b.a[i]);
}
return ret;
}
bnum operator + (bnum& b){
bnum ret;
for(int i=0;i<nmods;i++){
mod=mods[i];
ret.a[i]=add(a[i],b.a[i]);
}
return ret;
}
bool operator <(const bnum& b)const{
for(int i=0;i<nmods;i++){
if(a[i]==b.a[i])continue;
return a[i]<b.a[i];
}
return false;
}
int a[nmods];
};
string s[maxn];
bool numcmp(string& a,string& b){
if(a.size()!=b.size())return a.size()<b.size();
for(int i=0;i<a.size();i++){
if(a[i]==b[i])continue;
return a[i]<b[i];
}
return false;
}
bnum a[maxn];
vector<bnum>bucket[maxd+10];
void prek(){
bucket[1].pb(bnum("1"));
bnum p1("1"),p2("1");
ld digs1=log10(1);
ld digs2=log10(1);
int cnt = 0;
while(((int)digs2+1)<maxd){
ld digs = digs1 + log10(1+pow(10,digs2-digs1));
bnum nxt = p1+p2;
bucket[((int)digs2+1)].pb(nxt);
p1=p2;
p2=nxt;
digs1=digs2;
digs2=digs;
cnt++;
}
///printf("%d CNT\n",cnt);
}
int main(){
///freopen("test.txt","r",stdin);
prek();
///return 0;
scanf("%d",&n);
for(int i=0;i<n;i++){
cin>>s[i];
}
sort(s,s+n,numcmp);
for(int i=0;i<n;i++){
a[i]=bnum(s[i]);
}
ll rez=0;
map<bnum,ll>mapa;
for(int i=0;i<n;i++){
int d=s[i].size();
int lp=max(1,d-2);
int rp=min(d+2,maxd);
for(int j=lp;j<=rp;j++){
for(int k=0;k<bucket[j].size();k++){
bnum pom = bucket[j][k]-a[i];
if(mapa.find(pom)==mapa.end())continue;
rez+=mapa[pom];
}
}
mapa[a[i]]++;
}
printf("%lld\n",rez);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3175ms
memory: 201368kb
input:
6 50 8 8 5 72 354224848179261915070
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 3279ms
memory: 206204kb
input:
28 200878223506436882933619847964496455022155117513398820563747455993172799881403389571477889821109288771413214004090719097929400406252135763028179112130390003528046316900603668569910008417315162907579003880220844686222148696041857432602133894827753998572080650383305777912447151917272483538029469449...
output:
27
result:
ok 1 number(s): "27"
Test #3:
score: 0
Accepted
time: 3332ms
memory: 210860kb
input:
5187 2640352926124261912741724778991366987330659389621881876017670644497364093930668042530271338851702874394631009332660937266680740235862107353443518003194307853104942996827176097428402408674756368623972812842571069642405111849826172879369776309763468485788964245903781380419155348915131587410703749...
output:
6073
result:
ok 1 number(s): "6073"
Test #4:
score: 0
Accepted
time: 3229ms
memory: 201420kb
input:
200000 2 2 2 2 1 2 1 1 2 2 1 1 1 2 2 1 1 2 1 1 2 2 1 2 2 2 1 1 1 1 2 2 1 2 1 2 1 1 2 2 1 1 1 2 1 1 2 1 2 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 2 1 2 2 1 1 1 2 2 2 1 1 2 1 1 2 1 2 1 1 1 2 2 2 1 1 1 1 2 1 2 1 1 2 2 1 1 2 1 1 2 1 2 2 1 2 1 2 2 1 1 2 1 1 1 2 2 2 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 2 2 1 1 1 1 2 2 2 2...
output:
15003749259
result:
ok 1 number(s): "15003749259"
Test #5:
score: -100
Time Limit Exceeded
input:
200000 944176313232170622314 2590599414036674999101 753315073608896000424 9299685298577430049245 9361800333778142620806 8988699166328904060999 9606920674025578304023 4203331868598952026136 5183047027116137697788 3968714342776915029801 8130984095583566992354 3206443643596048048798 6248561214283254355...