T1.Crazy

题意：求 $\sum\limits_{i=1}^{n}{Fib[i]^2}$ 其中 Fib[i] 表示斐波那契数列第 i 项，Fib[1]=Fib[2]=1;(n<=1e15)
分析：通过猜想与验证，我们发现 $\sum\limits_{i=1}^{n}{Fib[i]^2}=Fib[n]\times Fib[n+1]$
证明：显然这个结论对于 n=1 是成立的。我们假设这个结论是正确的，那么有

$\sum\limits_{i=1}^{n}{Fib[i]^2}=\sum\limits_{i=1}^{n-1}{Fib[i]^2}+Fib[n]^2=Fib[n-1]Fib[n]+Fib[n]^2=Fib[n]Fib[n+1]$
然后我们可以用矩阵快速幂来求 Fib[i]

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define MD 1000000007

typedef long long ll;

typedef struct _matrix
{
    ll x[3][3];
}matrix;

inline matrix mul(matrix a,matrix b)
{
    matrix c;
    c.x[1][1]=((a.x[1][1]*b.x[1][1])%MD+(a.x[2][1]*b.x[1][2]%MD))%MD;
    c.x[1][2]=((a.x[1][2]*b.x[1][1])%MD+(a.x[2][2]*b.x[1][2]%MD))%MD;
    c.x[2][1]=((a.x[1][1]*b.x[2][1])%MD+(a.x[2][1]*b.x[2][2]%MD))%MD;
    c.x[2][2]=((a.x[1][2]*b.x[2][1])%MD+(a.x[2][2]*b.x[2][2]%MD))%MD;
    return c;
}

inline matrix setmat(ll a,ll b,ll c,ll d)
{
    matrix mat;
    mat.x[1][1]=a,mat.x[1][2]=b,mat.x[2][1]=c,mat.x[2][2]=d;
    return mat;
}

inline matrix ksm(matrix a,ll t)
{
    matrix ans;
    ans=setmat(1,0,0,1);
    while(t)
    {
        if(t&1)ans=mul(a,ans);
        a=mul(a,a);
        t>>=1;
    }
    return ans;
}

inline ll getfib(ll num)
{
    if(num==1||num==2)return 1;
    matrix but;
    but=setmat(1,1,1,0);
    but=ksm(but,num-2);
    return ((but.x[1][1]+but.x[1][2])%MD);
}

int main()
{
    freopen("crazy.in","r",stdin);
    freopen("crazy.out","w",stdout);
    ll n;
    scanf("%lld",&n);
    cout<<(getfib(n)*getfib(n+1))%MD<<endl;
    return 0;
}

T2.lucky
题意：对于区间 [L,R] 内求有多少个数是 LN 的倍数且不是任何一个 BN 的倍数 (BN 个数<=15,1<=L,R<=1e15)
分析：容斥搞一搞，但要注意 $\prod BN$ 越界后直接返回

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

ll L,R,ln,n,un[20];
ll ans;

void input()
{
    scanf("%lld%lld%lld%lld",&ln,&n,&L,&R);
    for(ll i=1;i<=n;i++)scanf("%lld",&un[i]);
}

ll gcd(ll a,ll b)
{
    return (b==0?a:gcd(b,a%b));
}

void sch(ll now,ll pos,ll num)
{
    if(now<=0)return;
    if(pos==n+1)
    {
        if(num%2==1)ans+=((R/now)-((L-1)/now));
        else ans-=((R/now)-((L-1)/now));
        return ;
    }
    sch(now/gcd(now,un[pos])*un[pos],pos+1,num+1);
    sch(now,pos+1,num);
}

int main()
{
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    input();
    sch(ln,1,1);
    cout<<ans<<endl;
    return 0;
}

T3.feed
题意：用两个给定大小的勺子把无限多的粥转移到无限大的碗里或转移出去，每次勺子必须装满。求碗里能否有 X 单位的粥。
分析：扩展欧几里得。
我们需要知道对于 ax+by=c 的通解表达式，并且将表达式表示成坐标系中的直线，求两条直线纵坐标绝对值的和的最小值。

#include <iostream>
#include <cstring>
#include <cstdio>

#define mabs(a) ((a)>0?(a):-(a))

using namespace std;

typedef long long ll;

ll exgcd(ll x,ll y,ll &a,ll &b)
{
    if(y==0)
    {
        a=1;
        b=0;
        return x;
    }
    ll ret,tmp;
    ret=exgcd(y,x%y,a,b);
    a=a-b*(x/y);
    swap(a,b);
    return ret;
}

ll sa,sb,targ;

void work()
{
    ll a,b,g,a0,b0,da,db;
    g=exgcd(sa,sb,a0,b0);
    if(targ%g){cout<<"BeiJu!"<<endl;return;}
    a0*=targ/g;
    b0*=targ/g;

    da=mabs(sb/g);
    db=-mabs(sa/g);

    ll dt1,dt2;
    dt1=-(a0/da);
    dt2=-(b0/db);

    ll mans=9999999999;

    for(ll i=dt1-1;i<=dt1+1;i++)mans=min(mans,mabs(db*i+b0)+mabs(da*i+a0));
    for(ll i=dt2-1;i<=dt2+1;i++)mans=min(mans,mabs(db*i+b0)+mabs(da*i+a0));

    cout<<mans<<endl;
}

int main()
{
    freopen("feed.in","r",stdin);
    freopen("feed.out","w",stdout);
    cin>>sa>>sb;
    while(cin>>targ)work();
    return 0;
}

【考试总结】math5 -boshi

于2017年8月9日由boshi发布

T1.Crazy

0 条评论

发表回复取消回复

【考试总结】math5 -boshi

于2017年8月9日由boshi发布

T1.Crazy

0 条评论

发表回复 取消回复

发表回复取消回复