- 2019.07.10
- T0(Fibonacci sequence)
乍看数据极大, 实则暗藏玄机.
Baidu
原本想通过 Baidu 找一下 O(1) 的通项公式,
结果发现根本无法实现:
但是我却发现了这个:
兴奋之情溢于言表, 不说了, 放代码:
- #include<bits/stdc++.h>
- #define fi fifteen
- using namespace std;
- unsigned long long fifteen[15005],c[15000];
- int x,y,T;
- void yu()
- {
- fi[0]=0;fi[1]=1;
- for(int i=2;i<=15000;i++)
- {
- fi[i]=(fi[i-1]+fi[i-2])%10000;
- //cout<<fi[i]<<endl;
- }
- //cout<<fi[127]<<" ";
- }
- void add()
- {
- for(int i=1;i<=15000;i++)
- {
- int ii;
- ii=i;
- while(ii<=15000)
- {
- c[ii]+=fi[i]%10000;
- c[ii]=c[ii]%10000;
- ii+=ii&(-ii);//cout<<"c"<<c[4];
- //cout<<c[ii]<<" ";
- }
- }
- }
- int ask(long long op)
- {
- int ans=0;
- op=op%15000;
- while(op>0)
- {
- ans+=c[op]%10000;
- op-=op&(-op);
- //cout<<"op:"<<c[op]<<" ";
- //cout<<ans;
- }
- //cout<<"ans:"<<ans<<endl;
- return ans%10000;
- }
- int main()
- {
- memset(fifteen,0,sizeof(fifteen));
- yu();
- add();
- cin>>T;
- for(int i=1;i<=T;i++)
- {
- long long x,y,ll;
- scanf("%lld%lld",&x,&y);
- ll=ask(y)-ask(x-1);
- if((ll)<0)
- {
- ll+=10000;
- }
- printf("%d\n",ll);
- }
- return 0;
- }
- open
当老师讲的时候, 却利用了矩阵乘法 (Baidu)
纪中五测
来源: http://www.bubuko.com/infodetail-3121034.html