QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#743606#9225. Fibonacci Fusionucup-team134#TL 3332ms210860kbC++143.0kb2024-11-13 19:37:372024-11-13 19:37:39

Judging History

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

  • [2024-11-13 19:37:39]
  • 评测
  • 测评结果:TL
  • 用时:3332ms
  • 内存:210860kb
  • [2024-11-13 19:37:37]
  • 提交

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...

output:


result: