加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 （https://www.lidatong.com.cn/）- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置： 首页 > 大数据 > 正文

HDU 5351 MZL's Border(大数+规律)

发布时间：2020-12-14 02:26:20 所属栏目：大数据 来源：网络整理
导读：MZL's Border Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others) Problem Description As is known to all,MZL is an extraordinarily lovely girl. One day,MZL was playing with her favorite data structure,strings

MZL's Border

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)


Problem Description
As is known to all,MZL is an extraordinarily lovely girl. One day,MZL was playing with her favorite data structure,strings.

MZL is really like? Fibonacci?Sequence ,so she defines? Fibonacci?Strings ?in the similar way. The definition of? Fibonacci?Strings ?is given below.
??
??1)? fib1=b
??
??2)? fib2=a
??
??3)? fibi=fibi?1fibi?2,?i>2
??
For instance,? fib3=ab,?fib4=aba,?fib5=abaab .

Assume that a string? s ?whose length is? n ?is? s1s2s3...sn . Then? sisi+1si+2si+3...sj ?is called as a substring of? s ,which is written as? s[i:j] .

Assume that? i<n . If? s[1:i]=s[n?i+1:n] ,then? s[1:i] ?is called as a? Border ?of? s . In? Borders ?of? s ,the longest? Border ?is called as? s '? LBorder . Moreover,136)"> s[1:i] 's? LBorder ?is called as? LBorderi .

Now you are given 2 numbers? n ?and? m . MZL wonders what? LBorderm ?of? fibn ?is. For the number can be very big,you should just output the number modulo? 258280327(=2×317+1) .

Note that? 1≤T≤100,?1≤n≤103,?1≤m≤|fibn| .
?

Input
The first line of the input is a number? T ,which means the number of test cases.

Then for the following? T ?lines,each has two positive integers? n ?and? m ,whose meanings are described in the description.
?

Output
The output consists of? T ?lines. Each has one number,meaning? fibn 's? LBorderm ?modulo? 258280327(=2×317+1) .
?

Sample Input 
  
  

   
   2
4 3
5 5
?

Sample Output 
  
  

   
   1
2
?

Source
2015 Multi-University Training Contest 5
?
/*******************************************************************************/

题意：题目定义了一个斐波那契串

1) fib1=b;

2) fib2=a;

3) fibi=fibi-1fibi-2,i>2

举例，fib3=ab,fib4=aba,fib5=abaab

我们暂时将字符串sisi+1si+2si+3…sj记做s[i:j]

求满足s[1:i]=s[m-i+1:m](i<m)的i的最大值,记做LBorderm

例如m=5时，LBorderm=2,因为abaab中前两个和末尾两个相同，即黑色部分

解题思路：

一看到题目的数据这么大，理所当然就会想到必定存在规律，先列出几项观察一下

m ?LBorderm ?D-value(差值)

1 ? ? ? ? ?0 ? ? ? ? ? ? ? 1

2 ? ? ? ? ?0 ? ? ? ? ? ? ? 2

3 ? ? ? ? ?1 ? ? ? ? ? ? ? 2

4 ? ? ? ? ?1 ? ? ? ? ? ? ? 3

5 ? ? ? ? ?2 ? ? ? ? ? ? ? 3

6 ? ? ? ? ?3 ? ? ? ? ? ? ? 3

7 ? ? ? ? ?2 ? ? ? ? ? ? ? 5

8 ? ? ? ? ?3 ? ? ? ? ? ? ? 5

9 ? ? ? ? ?4 ? ? ? ? ? ? ? 5

10 ? ? ? ?5 ? ? ? ? ? ? ? 5

11 ? ? ? ?6 ? ? ? ? ? ? ? 5

12 ? ? ? ?4 ? ? ? ? ? ? ? 8

13 ? ? ? ?5 ? ? ? ? ? ? ? 8

14 ? ? ? ?6 ? ? ? ? ? ? ? 8 ?

由上述例子可知，m与结果之间的差值是斐波那契数，仔细观察一下，便会得出这样一个结论：

当我们找到第一个i满足m+1<|fibi|时，LBorderm=m-|fibi-2|(|fibi-2|表示斐波那契串fibi-2的长度) ?

另外需要提及一下的是该题数据比较大，所以就需要用到大数了，两种方法都可以，一种拉一下大数模板，另一种就是用Java提供的大数packet

方法(1) 利用大数模板

/*
+,-,*,/,% 可直接使用.
CIN读入
bignum数据类型
*/
#include <iostream>
#include <string.h>
#include<stdio.h>
#include<iostream>
using namespace std;
#define DIGIT    4
#define DEPTH    10000
#define MAX     100
typedef int bignum_t[MAX+1];
int read(bignum_t a,istream& is=cin){
    char buf[MAX*DIGIT+1],ch;
    int i,j;
    memset((void*)a,sizeof(bignum_t));
    if (!(is>>buf))    return 0;
    for (a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--)
        ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch;
    for (a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j<a[0]*DIGIT;buf[j++]='0');
    for (i=1;i<=a[0];i++)
        for (a[i]=0,j=0;j<DIGIT;j++)
            a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0';
    for (;!a[a[0]]&&a[0]>1;a[0]--);
    return 1;
}

void write(const bignum_t a,ostream& os=cout){
    int i,j;
    for (os<<a[i=a[0]],i--;i;i--)
        for (j=DEPTH/10;j;j/=10)
            os<<a[i]/j%10;
}

int comp(const bignum_t a,const bignum_t b){
    int i;
    if (a[0]!=b[0])
        return a[0]-b[0];
    for (i=a[0];i;i--)
        if (a[i]!=b[i])
            return a[i]-b[i];
    return 0;
}

int comp(const bignum_t a,const int b){
    int c[12]={1};
    for (c[1]=b;c[c[0]]>=DEPTH;c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++);
    return comp(a,c);
}

int comp(const bignum_t a,const int c,const int d,const bignum_t b){
    int i,t=0,O=-DEPTH*2;
    if (b[0]-a[0]<d&&c)
        return 1;
    for (i=b[0];i>d;i--){
        t=t*DEPTH+a[i-d]*c-b[i];
        if (t>0) return 1;
        if (t<O) return 0;
    }
    for (i=d;i;i--){
        t=t*DEPTH-b[i];
        if (t>0) return 1;
        if (t<O) return 0;
    }
    return t>0;
}

void add(bignum_t a,const bignum_t b){
    int i;
    for (i=1;i<=b[0];i++)
        if ((a[i]+=b[i])>=DEPTH)
            a[i]-=DEPTH,a[i+1]++;
    if (b[0]>=a[0])
        a[0]=b[0];
    else
        for (;a[i]>=DEPTH&&i<a[0];a[i]-=DEPTH,i++,a[i]++);
    a[0]+=(a[a[0]+1]>0);
}

void add(bignum_t a,const int b){
    int i=1;
    for (a[1]+=b;a[i]>=DEPTH&&i<a[0];a[i+1]+=a[i]/DEPTH,a[i]%=DEPTH,i++);
    for (;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);
}

void sub(bignum_t a,const bignum_t b){
    int i;
    for (i=1;i<=b[0];i++)
        if ((a[i]-=b[i])<0)
            a[i+1]--,a[i]+=DEPTH;
    for (;a[i]<0;a[i]+=DEPTH,a[i]--);
    for (;!a[a[0]]&&a[0]>1;a[0]--);
}

void sub(bignum_t a,const int b){
    int i=1;
    for (a[1]-=b;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);
    for (;!a[a[0]]&&a[0]>1;a[0]--);
}

void sub(bignum_t a,const bignum_t b,const int d){
    int i,O=b[0]+d;
    for (i=1+d;i<=O;i++)
        if ((a[i]-=b[i-d]*c)<0)
            a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH;
    for (;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,i++);
    for (;!a[a[0]]&&a[0]>1;a[0]--);
}

void mul(bignum_t c,const bignum_t a,j;
    memset((void*)c,sizeof(bignum_t));
    for (c[0]=a[0]+b[0]-1,i=1;i<=a[0];i++)
        for (j=1;j<=b[0];j++)
            if ((c[i+j-1]+=a[i]*b[j])>=DEPTH)
                c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH;
    for (c[0]+=(c[c[0]+1]>0);!c[c[0]]&&c[0]>1;c[0]--);
}

void mul(bignum_t a,const int b){
    int i;
    for (a[1]*=b,i=2;i<=a[0];i++){
        a[i]*=b;
        if (a[i-1]>=DEPTH)
            a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH;
    }
    for (;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[0]++);
    for (;!a[a[0]]&&a[0]>1;a[0]--);
}

void mul(bignum_t b,const int d){
    int i;
    memset((void*)b,sizeof(bignum_t));
    for (b[0]=a[0]+d,i=d+1;i<=b[0];i++)
        if ((b[i]+=a[i-d]*c)>=DEPTH)
            b[i+1]+=b[i]/DEPTH,b[i]%=DEPTH;
    for (;b[b[0]+1];b[0]++,b[b[0]+1]=b[b[0]]/DEPTH,b[b[0]]%=DEPTH);
    for (;!b[b[0]]&&b[0]>1;b[0]--);
}

void div(bignum_t c,bignum_t a,const bignum_t b){
    int h,l,m,i;
    memset((void*)c,sizeof(bignum_t));
    c[0]=(b[0]<a[0]+1)?(a[0]-b[0]+2):1;
    for (i=c[0];i;sub(a,b,c[i]=m,i-1),i--)
        for (h=DEPTH-1,l=0,m=(h+l+1)>>1;h>l;m=(h+l+1)>>1)
            if (comp(b,i-1,a)) h=m-1;
            else l=m;
    for (;!c[c[0]]&&c[0]>1;c[0]--);
    c[0]=c[0]>1?c[0]:1;
}

void div(bignum_t a,const int b,int& c){
    int i;
    for (c=0,i=a[0];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);
    for (;!a[a[0]]&&a[0]>1;a[0]--);
}

void sqrt(bignum_t b,bignum_t a){
    int h,i;
    memset((void*)b,sizeof(bignum_t));
    for (i=b[0]=(a[0]+1)>>1;i;sub(a,b[i]+=m,b[i]=m=(h+l+1)>>1;h>l;b[i]=m=(h+l+1)>>1)
            if (comp(b,a)) h=m-1;
            else l=m;
    for (;!b[b[0]]&&b[0]>1;b[0]--);
    for (i=1;i<=b[0];b[i++]>>=1);
}

int length(const bignum_t a){
    int t,ret;
    for (ret=(a[0]-1)*DIGIT,t=a[a[0]];t;t/=10,ret++);
    return ret>0?ret:1;
}

int digit(const bignum_t a,const int b){
    int i,ret;
    for (ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT;i;ret/=10,i--);
    return ret%10;
}

int zeronum(const bignum_t a){
    int ret,t;
    for (ret=0;!a[ret+1];ret++);
    for (t=a[ret+1],ret*=DIGIT;!(t%10);t/=10,ret++);
    return ret;
}

void comp(int* a,const int l,const int h,j,t;
    for (i=l;i<=h;i++)
        for (t=i,j=2;t>1;j++)
            while (!(t%j))
                a[j]+=d,t/=j;
}

void convert(int* a,bignum_t b){
    int i,t=1;
    memset(b,sizeof(bignum_t));
    for (b[0]=b[1]=1,i=2;i<=h;i++)
        if (a[i])
            for (j=a[i];j;t*=i,j--)
                if (t*i>DEPTH)
                    mul(b,t),t=1;
    mul(b,t);
}

void combination(bignum_t a,int m,int n){
    int* t=new int[m+1];
    memset((void*)t,sizeof(int)*(m+1));
    comp(t,n+1,1);
    comp(t,2,m-n,-1);
    convert(t,a);
    delete []t;
}

void permutation(bignum_t a,int n){
    int i,t=1;
    memset(a,sizeof(bignum_t));
    a[0]=a[1]=1;
    for (i=m-n+1;i<=m;t*=i++)
        if (t*i>DEPTH)
            mul(a,t=1;
    mul(a,t);
}

#define SGN(x) ((x)>0?1:((x)<0?-1:0))
#define ABS(x) ((x)>0?(x):-(x))

int read(bignum_t a,int &sgn,istream& is=cin){
    char str[MAX*DIGIT+2],ch,*buf;
    int i,sizeof(bignum_t));
    if (!(is>>str)) return 0;
    buf=str,sgn=1;
    if (*buf=='-') sgn=-1,buf++;
    for (a[0]=strlen(buf),j=0;j<DIGIT;j++)
            a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0';
    for (;!a[a[0]]&&a[0]>1;a[0]--);
    if (a[0]==1&&!a[1]) sgn=0;
    return 1;
}

struct bignum{
    bignum_t num;
    int sgn;
public:
inline bignum(){memset(num,sizeof(bignum_t));num[0]=1;sgn=0;}
//inline int operator!(){return num[0]==1&&!num[1];}
inline bignum& operator=(const bignum& a){memcpy(num,a.num,sizeof(bignum_t));sgn=a.sgn;return *this;}
inline bignum& operator=(const int a){memset(num,sizeof(bignum_t));num[0]=1;sgn=SGN(a);add(num,sgn*a);return *this;};
inline bignum& operator+=(const bignum& a){if(sgn==a.sgn)add(num,a.num);else if(sgn&&a.sgn){int ret=comp(num,a.num);if(ret>0)sub(num,a.num);else if(ret<0){bignum_t t;
    memcpy(t,num,sizeof(bignum_t));memcpy(num,sizeof(bignum_t));sub(num,t);sgn=a.sgn;}else memset(num,sizeof(bignum_t)),num[0]=1,sgn=0;}else if(!sgn)memcpy(num,sgn=a.sgn;return *this;}
inline bignum& operator+=(const int a){if(sgn*a>0)add(num,ABS(a));else if(sgn&&a){int ret=comp(num,ABS(a));if(ret>0)sub(num,ABS(a));else if(ret<0){bignum_t t;
    memcpy(t,sizeof(bignum_t));memset(num,sizeof(bignum_t));num[0]=1;add(num,ABS(a));sgn=-sgn;sub(num,t);}else memset(num,sgn=0;}else if(!sgn)sgn=SGN(a),add(num,ABS(a));return *this;}
inline bignum operator+(const bignum& a){bignum ret;memcpy(ret.num,sizeof(bignum_t));ret.sgn=sgn;ret+=a;return ret;}
inline bignum operator+(const int a){bignum ret;memcpy(ret.num,sizeof(bignum_t));ret.sgn=sgn;ret+=a;return ret;}
inline bignum& operator-=(const bignum& a){if(sgn*a.sgn<0)add(num,t);sgn=-sgn;}else memset(num,sgn=0;}else if(!sgn)add(num,a.num),sgn=-a.sgn;return *this;}
inline bignum& operator-=(const int a){if(sgn*a<0)add(num,ABS(a));sub(num,sgn=0;}else if(!sgn)sgn=-SGN(a),ABS(a));return *this;}
inline bignum operator-(const bignum& a){bignum ret;memcpy(ret.num,sizeof(bignum_t));ret.sgn=sgn;ret-=a;return ret;}
inline bignum operator-(const int a){bignum ret;memcpy(ret.num,sizeof(bignum_t));ret.sgn=sgn;ret-=a;return ret;}
inline bignum& operator*=(const bignum& a){bignum_t t;mul(t,a.num);memcpy(num,t,sizeof(bignum_t));sgn*=a.sgn;return *this;}
inline bignum& operator*=(const int a){mul(num,ABS(a));sgn*=SGN(a);return *this;}
inline bignum operator*(const bignum& a){bignum ret;mul(ret.num,a.num);ret.sgn=sgn*a.sgn;return ret;}
inline bignum operator*(const int a){bignum ret;memcpy(ret.num,sizeof(bignum_t));mul(ret.num,ABS(a));ret.sgn=sgn*SGN(a);return ret;}
inline bignum& operator/=(const bignum& a){bignum_t t;div(t,sizeof(bignum_t));sgn=(num[0]==1&&!num[1])?0:sgn*a.sgn;return *this;}
inline bignum& operator/=(const int a){int t;div(num,ABS(a),t);sgn=(num[0]==1&&!num[1])?0:sgn*SGN(a);return *this;}
inline bignum operator/(const bignum& a){bignum ret;bignum_t t;memcpy(t,sizeof(bignum_t));div(ret.num,a.num);ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*a.sgn;return ret;}
inline bignum operator/(const int a){bignum ret;int t;memcpy(ret.num,t);ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*SGN(a);return ret;}
inline bignum& operator%=(const bignum& a){bignum_t t;div(t,a.num);if (num[0]==1&&!num[1])sgn=0;return *this;}
inline int operator%=(const int a){int t;div(num,t);memset(num,t);return t;}
inline bignum operator%(const bignum& a){bignum ret;bignum_t t;memcpy(ret.num,sizeof(bignum_t));div(t,ret.num,a.num);ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn;return ret;}
inline int operator%(const int a){bignum ret;int t;memcpy(ret.num,t);memset(ret.num,sizeof(bignum_t));ret.num[0]=1;add(ret.num,t);return t;}
inline bignum& operator++(){*this+=1;return *this;}
inline bignum& operator--(){*this-=1;return *this;};
inline int operator>(const bignum& a){return sgn>0?(a.sgn>0?comp(num,a.num)>0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<0:0):a.sgn<0);}
inline int operator>(const int a){return sgn>0?(a>0?comp(num,a)>0:1):(sgn<0?(a<0?comp(num,-a)<0:0):a<0);}
inline int operator>=(const bignum& a){return sgn>0?(a.sgn>0?comp(num,a.num)>=0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<=0:0):a.sgn<=0);}
inline int operator>=(const int a){return sgn>0?(a>0?comp(num,a)>=0:1):(sgn<0?(a<0?comp(num,-a)<=0:0):a<=0);}
inline int operator<(const bignum& a){return sgn<0?(a.sgn<0?comp(num,a.num)>0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<0:0):a.sgn>0);}
inline int operator<(const int a){return sgn<0?(a<0?comp(num,-a)>0:1):(sgn>0?(a>0?comp(num,a)<0:0):a>0);}
inline int operator<=(const bignum& a){return sgn<0?(a.sgn<0?comp(num,a.num)>=0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<=0:0):a.sgn>=0);}
inline int operator<=(const int a){return sgn<0?(a<0?comp(num,-a)>=0:1):(sgn>0?(a>0?comp(num,a)<=0:0):a>=0);}
inline int operator==(const bignum& a){return (sgn==a.sgn)?!comp(num,a.num):0;}
inline int operator==(const int a){return (sgn*a>=0)?!comp(num,ABS(a)):0;}
inline int operator!=(const bignum& a){return (sgn==a.sgn)?comp(num,a.num):1;}
inline int operator!=(const int a){return (sgn*a>=0)?comp(num,ABS(a)):1;}
inline int operator[](const int a){return digit(num,a);}
friend inline istream& operator>>(istream& is,bignum& a){read(a.num,a.sgn,is);return is;}
friend inline ostream& operator<<(ostream& os,const bignum& a){if(a.sgn<0)os<<'-';write(a.num,os);return os;}
friend inline bignum sqrt(const bignum& a){bignum ret;bignum_t t;memcpy(t,sizeof(bignum_t));sqrt(ret.num,t);ret.sgn=ret.num[0]!=1||ret.num[1];return ret;}
friend inline bignum sqrt(const bignum& a,bignum& b){bignum ret;memcpy(b.num,b.num);ret.sgn=ret.num[0]!=1||ret.num[1];b.sgn=b.num[0]!=1||ret.num[1];return ret;}
inline int length(){return ::length(num);}
inline int zeronum(){return ::zeronum(num);}
inline bignum C(const int m,const int n){combination(num,n);sgn=1;return *this;}
inline bignum P(const int m,const int n){permutation(num,n);sgn=1;return *this;}
};
bignum s[1005],mod;
int main()
{
    int t,i;
    bignum n,m;
    s[1]=1;s[2]=1;
    for(i=3;i<=1000;i++)
        s[i]=s[i-1]+s[i-2];
    mod=258280327;
    scanf("%d",&t);
    while(t--)
    {
        cin>>n>>m;
        for(i=1;i<=1000;i++)
            if(s[i]>m+1)
                break;
        cout<<(m-s[i-2])%mod<<endl;
    }
    return 0;
}
方法(2) 利用Java 
import java.util.Scanner;
import java.math.BigInteger;
public class Main
{
    public static void main(String[] args)
    {
        int i;
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        BigInteger[] a = new BigInteger[1005];
        BigInteger ans;
        a[1]=BigInteger.valueOf(1);
        a[2]=BigInteger.valueOf(2);
        for(i=3;i<=1000;i++)
            a[i]=a[i-1].add(a[i-2]);
        while(t>0)
        {
            t--;
            int n=sc.nextInt();
            BigInteger m = sc.nextBigInteger();
            for(i=1;i<=1000;i++)
                if(m.compareTo(a[i])<0&&m.compareTo(a[i-1])>=0)
                {
                    ans=m.subtract(a[i-2]).mod(BigInteger.valueOf(258280327));
                    System.out.println(ans);
                    break;
                }
        }
    }
}
欢迎大家来提意见

菜鸟成长记

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
    相关内容
      推荐文章
        站长推荐
        热点阅读

          【免责声明】本站内容转载自互联网，其发布内容言论不代表本站观点，如果其链接、内容的侵犯您的权益，烦请提交相关链接至邮箱bqsm@foxmail.com我们将及时予以处理。

          建议您使用1920×1080分辨率、谷歌浏览器Google Chrome、Microsoft Edge以获得本站的最佳浏览效果

          Copygight © 2008-2022 https://www.lidatong.com.cn/ All Rights Reserved. 李大同