萌新集中营第四期

题解

题目

A Eddy's AC难题 (HDU - 2200)

题意：

    中文题。

题解：

    符号说明，以C(a，b)表示从a个东西中无顺序的选择b个的方法数，以A(a，b)表示从a个东西中有顺序的选择b个的方法数，以(a<=i<=b)Σ[y]表示y从i=a到i=b的求和。
    有很多种思路：
    <1>从这n个人中选择x(2<=x<=n)个人，然后把这x个人分成AC数少和AC数多的两部分，有x-1种分法，答案就是(2<=x<=n)Σ[C(n，x)]
    <2>枚举AC数少的那个部分AC数最多的人，那么比他少的所有人可选可不选，比他多的人至少选一个，答案就是(1<=x<n)Σ[2^(x-1)*(2^(n-x)-1)]
    而组合数也有多种方法来求：
    (1)通过定义公式C(a，b)=a!/(b!*(a-b)!)，这种方法不常用，因为阶乘是非常大的，这道题就不能用这个办法。。。
    (2)由上面的公式可以看出C(a，b-1)=a!/((b-1)!*(a-b+1)!)，所以C(a，b)=C(a，b-1)*(a-b+1)/b，这种方法避免了阶乘过大的问题，对于这道题而言是可行的，不过对于有取模的情况也是比较尴尬的
    (3)从a个东西中选择b个，相当于从前a-1个直接选b个然后不选第a个，或者从前a-1个中选b-1个，再选第a个，所以C(a，b)=C(a-1，b)+C(a-1，b-1)，于是我们就可以通过打组合数表来求组合数，而且便于取模，唯一的问题就是当a、b很大的时候，时间复杂度是平方级的。。。ps:注意C(x,0)不论x取什么值，永远是1
    (4)在有取模，而且模数是大于a和b的质数的时候，通过求逆元，可以用定义公式求
    (5)还有一个神奇的东西叫Lucas
    (4)、(5)提到的两种方法，有兴趣的同学可以自行去了解。
    这里给出分别用(2)、(3)两种求组合数方法的方法<1>，还有方法<2>。
    (2)求组合数，方法<1>时间复杂度o(n^2)，空间复杂度o(1)。
    (3)求组合数，方法<1>时间复杂度o(n^2)，空间复杂度o(n^2)。
    方法<2>时间复杂度o(n)，空间复杂度o(n)。

代码：

(2)求组合数，<1>求答案：

#include<iostream>
#include<cstdio>
using namespace std;
long long c(int a,int b)
{
    long long ans=1;
    for(int i=1;i<=b;i++)
        ans=ans*(a-i+1)/i;
    return ans;
}
int main()
{
    int n;
    long long ans;
    while(~scanf("%d",&n))
    {
        ans=0;
        for(int x=2;x<=n;x++)
            ans+=c(n,x)*(x-1);
        printf("%lld\n",ans);
    }
    return 0;
}

(3)求组合数，<1>求答案：

#include<iostream>
#include<cstdio>
using namespace std;
long long  c[105][105];
int main()
{
    for(int i=-0;i<=100;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
    int n;
    long long ans;
    while(~scanf("%d",&n))
    {
        ans=0;
        for(int x=2;x<=n;x++)
            ans+=c[n][x]*(x-1);
        printf("%lld\n",ans);
    }
    return 0;
}

<3>求答案：

#include<iostream>
#include<cstdio>
using namespace std;
long long mi2[105];
int main()
{
    mi2[0]=1;
    for(int i=1;i<=100;i++)
        mi2[i]=mi2[i-1]*2;
    int n;
    long long ans;
    while(~scanf("%d",&n))
    {
        ans=0;
        for(int x=1;x<n;x++)
            ans+=mi2[x-1]*(mi2[n-x]-1);
        printf("%lld\n",ans);
    }
    return 0;
}

B RPG的错排 (HDU - 2068)

题意：

    中文题。

题解：

    错排数的定义：D(n)表示把n个数进行排列，每个数都不在自己原本的位置上的方案数。
    这道题思路其实很清晰，从n个人中选择超过一半的人待在自己的位置上，剩下的人都不待在自己的位置上，于是答案就是((n+1)/2<=x<=n)ΣC(n，x)*D(n-x)。
    组合数的部分上一题讲过了，重点说一下错排数怎么求。
    如果只有1个数，错排方案为0；如果有2个数，错排方案为1。这两点都很显然。那么如果有n(n>2)个数，我们先挑1个数x放在第1个位置，显然x不会等于1，然后我们考虑第x个位置放谁，有两种情况：
    (1)第x个位置放1，那么1和x就互换了位置，剩下n-2个数就重新错排，于是这种情况的方案数就等于从n个数中选一个不为1的数和1互换位置，剩下n-2个数错排，即(n-1)*D(n-2)
    (2)第x个位置放的数不为1，那么相当于我们把x和1等价起来，把这n-1个数重新错排，这个x同样有n-1中选择，所以方案数是(n-1)*D(n-1)
    所以当n>2，D(n)=(n-1)*(D(n-2)+D(n-1))，我们又知道D(1)和D(2)的值，就可以打错排表了。
    ps：D(0)是无意义的，在这道题里面也可以认为是1，表示全对的情况。
    时间复杂度o(n^2)，空间复杂度o(n^2)。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
long long c[30][30],d[30];
int main()
{
    for(int i=0;i<=25;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
    d[0]=1;
    d[1]=0;
    d[2]=1;
    for(int i=3;i<=25;i++)
        d[i]=(d[i-2]+d[i-1])*(i-1);
    int n;
    long long ans;
    while(scanf("%d",&n),n)
    {
        ans=0;
        for(int x=(n+1)/2;x<=n;x++)
            ans+=c[n][x]*d[n-x];
        printf("%lld\n",ans);
    }
    return 0;
}

C Co-prime (HDU - 4135)

题意：

    给定A、B、N(1<=A<=B<=10^15，1<=N<=10^9)，问区间[A，B]内有多少个数跟N互质。
    T(0<T<=100)组数据。

题解：

    首先我们用前缀和的思想把区间[A，B]变成[1，B]-[1，A-1]。然后我们只需要求从1到X有多少个数和N互质。按照互质的定义，我们很容易想到求每个数和N的最大公因数，看是不是1。但是很遗憾，这题A、B、N都很大。于是我们换个角度，从N入手，我们找到N的所有质因数，然后把1到X内所有含这些质因数的数都去掉就行了。这个过程中，为了避免含有多个质因数的数被重复删去，要用到容斥原理。
    容斥的写法很多，这里给出队列的方法。
    因为15!>10^9，所以我们可以认为N的质因数不超过15个。
    时间复杂度o(T*(sqrt(N)+2^15))，空间复杂度o(2^15)。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int fac[20],nums;
int len1,len2;
long long q1[100005],q2[100005];
queue <long long> v1,v2;
void init(int x)
{
    nums=0;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            fac[nums++]=i;
            while(x%i==0) x/=i;
        }
    }
    if(x!=1)
        fac[nums++]=x;
    return;
}
long long ask(long long x)
{
    if(nums)
    {
        long long ans=x-x/fac[0];
        len1=len2=1;
        q1[0]=x;
        q2[0]=x/fac[0];
        for(int i=1;i<nums;i++)
        {
            for(int j=0;j<len1;j++)
            {
                ans-=q1[j]/fac[i];
                v2.push(q1[j]/fac[i]);
            }
            for(int j=0;j<len2;j++)
            {
                ans+=q2[j]/fac[i];
                v1.push(q2[j]/fac[i]);
            }
            while(!v1.empty())
            {
                q1[len1++]=v1.front();
                v1.pop();
            }
            while(!v2.empty())
            {
                q2[len2++]=v2.front();
                v2.pop();
            }
        }
        return ans;
    }
    else
        return x;
}
int main()
{
    int T;
    long long A,B;
    int N;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        scanf("%lld%lld%d",&A,&B,&N);
        init(N);
        printf("Case #%d: %lld\n",t,ask(B)-ask(A-1));
    }
    return 0;
}

D sum (HDU - 5776)

题意：

    给定一个n(1<=n<=100000)个数的数列，第i个数为xi(1<=xi<=100)，问是否存在某一段数字的和能被m(1<=m<=5000)整除。
    T(1<=T<=10)组数据。

题解：

    用前缀和的思想，我们很容易想到把一段数的和转化为两个前缀的差。然而枚举这两个前缀是n^2的复杂度，再考虑到多组，时间复杂度boom！
    这题求的是有没有和能被m整除，那么我们把每个数变化成它除以m的余数，能被m整除就意味着余数是0，也就是两个前缀的差是0，换句话说就是两个前缀相等。
    所以我们只需要看有没有多于1个前缀除以m的余数相同，或者有没有某个前缀除以m的余数直接是0，就可以得到答案了。
    ps:根据抽屉原理可以得出当n>=m的时候，一定存在能被m整除的一段数的和，然并卵。。。
    时间复杂度o(T*n)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int life[5005];
int main()
{
    int t,n,m,now,nowsum;
    bool flag=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        nowsum=0;
        memset(life,0,sizeof(life));
        flag=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&now);
            nowsum=(nowsum+now)%m;
            if(nowsum==0 || life[nowsum])
                flag=1;
            life[nowsum]++;
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

E GCD & LCM (ZOJ - 1577)

题意：

    p和q为两个正整数，给出p和q的最大公因数x(2<=x<=100000)和最小公倍数y(2<=y<=100000)，问p和q有多少种可能的组合。
    多组数据。

题解：

    可以把p表示为a*gcd(p，q)，q表示为b*gcd(p，q)，且gcd(a，b)=1。又因为lcm(p，q)=p*q/gcd(p，q)=a*b*gcd(p，q)，所以a*b=lcm(p，q)/gcd(p，q)，。
    得到a*b了之后，求a和b有多少种组合就简单了因为a*b=lcm(p，q)/gcd(p，q)，所以a*b<=100000/2，我们可以枚举能整除a*b的a，来看b和a是不是互质。
    另一种思路是将a*b进行质因数分解，因为a和b互质，所以每种质因数只能属于a或者b，于是答案就是2^质因数个数。
    枚举a的方法时间复杂度o(y/x)，空间复杂度o(1)。
    质因数分解的方法时间复杂度o(sqrt(y/x))，空间复杂度o(1)。

代码：

枚举a：

#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int a,int b)
{
    if(a%b==0)
        return b;
    else
        return gcd(b,a%b);
}
int ok(int x)
{
    int ans=0;
    for(int i=1;i<=x;i++)
    {
        if(x%i==0 && gcd(i,x/i)==1)
            ans++;
    }
    return ans;
}
int main()
{
    int x,y;
    while(~scanf("%d%d",&x,&y))
    {
        if(y%x==0)
            printf("%d\n",ok(y/x));
        else
            printf("0\n");
    }
    return 0;
}

质因数分解：

#include<iostream>
#include<cstdio>
using namespace std;
int ok(int x)
{
    int ans=1,nums=0;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            nums++;
            while(x%i==0) x/=i;
        }
    }
    if(x!=1)
        nums++;
    while(nums--) ans=ans*2;
    return ans;
}
int main()
{
    int x,y;
    while(~scanf("%d%d",&x,&y))
    {
        if(y%x==0)
            printf("%d\n",ok(y/x));
        else
            printf("0\n");
    }
    return 0;
}

F The Factor (HDU - 5428)

题意：

    给出一个有n(1<=n<=100)个数的序列，第i个数为ai(1<=ai<=2*10^9)，问这些数的乘积里面最小的因数个数超过2的数是多少，如果不存在输出-1。
    T(1<=T<=15)组数据。

题解：

    因为一个数的因数肯定包含1和本身，所以只要这个数由两个非1的正整数相乘得到，那么他肯定包括至少3个因数。于是我们只要将这个序列的每个数都进行质因数分解，从中找两个最小的因数乘起来就是答案。如果没有两个非1因数的话，那么就输出-1。
    ps：注意两个大质数相乘有可能会超过int的上限。
    时间复杂度o(T*n*sqrt(a))，空间复杂度o(sqrt(a)+n)。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int ans1,ans2;
void update(int x)
{
    if(x<ans1)
    {
        ans2=ans1;
        ans1=x;
    }
    else
    {
        if(x<ans2)
            ans2=x;
    }
}
void go(int x)
{
    int nums;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            update(i);
            x/=i;
            if(x%i==0)
                update(i);
            while(x%i==0)
                x/=i;
        }
    }
    if(x!=1)
        update(x);
    return ;
}
int main()
{
    int t,n,now;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        ans1=ans2=2000000005;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&now);
            go(now);
        }
        if(ans2>2000000000)
            printf("-1\n");
        else
            printf("%lld\n",1LL*ans1*ans2);
    }
    return 0;
}

G The Euler function (HDU - 2824)

题意：

    欧拉函数phi(n)表示小于n并且和n互质的数的个数，给出a和b(2<a<b<3000000)，求(a<=x<=b)Σphi(x)。

题解：

    一如既往的前缀和思想，把区间和转化为两个前缀的差。
    欧拉函数的公式为phi(n)=n*(fac[1]-1)/fac[1]*(fac[2]-1)/fac[2]*...(fac[x]-1)/fac[x]，其中fac[i]表示n的第i个质因数。
    很容易想到打素数表，然后暴力求欧拉函数的每一项再求前缀和。其实我们可以把这两者结合起来，在打素数表的过程中就顺便把求欧拉函数的事干了。
    ps：这题非常恶心，空间只能开的下一个long long数组，多开一个int就会mle。
    时间复杂度o(3000000)，空间复杂度o(3000000)。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
long long phi[3000005];
int main()
{
    for(int i=2;i<=3000000;i++)
        phi[i]=i;
    for(int i=2;i<=3000000;i++)
    {
        if(phi[i]==i)
        {
            for(int j=i;j<=3000000;j+=i)
                phi[j]=phi[j]/i*(i-1);
        }
    }
    for(int i=2;i<=3000000;i++)
        phi[i]+=phi[i-1];
    int a,b;
    long long sum=0;
    while(~scanf("%d%d",&a,&b))
        printf("%lld\n",phi[b]-phi[a-1]);
    return 0;
}

H Raising Modulo Numbers (POJ - 1995)

题意：

    有A和B两个数列，各有H(1<=H<=45000)个数，求[(1<=i<=H)ΣAi^Bi]mod M(1<=M<=45000)的值。
    Z组数据。

题解：

    很暴力，其实就是求(1<=i<=H)Σ[Ai^Bi mod M]。但是Ai^Bi mod M的复杂度为Bi，再乘上一个H，就会Boom！
    所以我们要用快速幂来求Ai^Bi mod M。
    ps：因为M^2在int范围内，所以不需要担心爆int的问题。
    复杂度o(Z*H*log(Bi))，空间复杂度o(1)。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int pows(int x,int y,int m)
{
    int ans=1;
    while(y)
    {
        if(y%2)
            ans=(ans*x)%m;
        x=(x*x)%m;
        y/=2;
    }
    return ans;
}
int main()
{
    int z;
    int a,b,ans,h,m;
    scanf("%d",&z);
    while(z--)
    {
        scanf("%d%d",&m,&h);
        ans=0;
        for(int i=0;i<h;i++)
        {
            scanf("%d%d",&a,&b);
            ans=(ans+pows(a%m,b,m))%m;
        }
        printf("%d\n",ans);
    }
    return 0;
}

I Jzzhu and Sequences (CodeForces - 450B)

题意：

    当i>=2数列f满足f[i]=f[i-1]+f[i+1]，且f[1]=x、f[2]=y(|x|，|y|<=10^9)，求f[n] mod 1000000007(1<=n<=2*10^9)。

题解：

    看到f[i]=f[i-1]+f[i+1]可能会让人懵逼，不过移项一下其实就是f[i+1]=f[i]-f[i-1]，所以f[i]=f[i-1]-f[i-2]。这其实就是一个变形的斐波那契数列。因为n很大所以顺序递推是行不通的，于是我们考虑使用矩阵快速幂。用一个矩阵表示线性变换，然后用快速幂的思路求矩阵的幂，最后把首项进行这个幂代表的线性变换，就是答案了。
    ps：MOD*MOD会爆int，所以要用long long，还有就是可能会出现负数，注意过程中的取模。思考一下我向量的初值的含义和线性变换矩阵的含义。顺便学习一下封装一个类的思想~
    时间复杂度o(log(n))，空间复杂度o(1)。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define MOD 1000000007
struct Mat
{
    long long num[2][2];
    friend Mat operator *(Mat x1,Mat x2)
    {
        Mat ans;
        ans.num[0][0]=((x1.num[0][0]*x2.num[0][0]+x1.num[0][1]*x2.num[1][0])%MOD+MOD)%MOD;
        ans.num[0][1]=((x1.num[0][0]*x2.num[0][1]+x1.num[0][1]*x2.num[1][1])%MOD+MOD)%MOD;
        ans.num[1][0]=((x1.num[1][0]*x2.num[0][0]+x1.num[1][1]*x2.num[1][0])%MOD+MOD)%MOD;
        ans.num[1][1]=((x1.num[1][0]*x2.num[0][1]+x1.num[1][1]*x2.num[1][1])%MOD+MOD)%MOD;
        return ans;
    }
}E;
Mat pows(Mat X,int nums)
{
    Mat nowans=E;
    while(nums)
    {
        if(nums%2)
            nowans=X*nowans;
        X=X*X;
        nums/=2;
    }
    return nowans;
}
int main()
{
    E.num[0][0]=1;
    E.num[0][1]=0;
    E.num[1][0]=0;
    E.num[1][1]=1;
    Mat A,B;
    A.num[0][0]=0;
    A.num[0][1]=1;
    A.num[1][0]=-1;
    A.num[1][1]=1;
    int vec[2];
    int n;
    scanf("%d%d",&vec[0],&vec[1]);
    scanf("%d",&n);
    B=pows(A,n-1);
    vec[0]=((vec[0]*B.num[0][0]+vec[1]*B.num[0][1])%MOD+MOD)%MOD;
    printf("%d\n",vec[0]);
    return 0;
}

J How many ways?? (HDU - 2157)

题意：

    中文题。

题解：

    很容易想到的其实是dp解法，不过这里提供一个用矩阵乘法来写的思路，其实原理也是dp，你们思考一下。主要是理解一下转移矩阵怎么定出来的~
    ps：这题的数据，直接暴力乘就好，不用快速幂。。。
    时间复杂度o(T*n^2*k)，空间复杂度o(n^2)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MOD 1000
int n;
struct Vec
{
    int num[25];
    void init()
    {
        memset(num,0,sizeof(num));
    }
    friend int operator *(Vec x1,Vec x2)
    {
        int ans=0;
        for(int i=0;i<n;i++)
            ans=(ans+x1.num[i]*x2.num[i])%MOD;
        return ans;
    }
};
Vec A[25];
Vec pows(Vec x)
{
    Vec nowans;
    for(int i=0;i<n;i++)
        nowans.num[i]=A[i]*x;
    return nowans;
}
int main()
{
    int m,s,t,T;
    int a,b,k;
    Vec ans;
    while(scanf("%d%d",&n,&m),n||m)
    {
        for(int i=0;i<n;i++)
            A[i].init();
        while(m--)
        {
            scanf("%d%d",&s,&t);
            A[t].num[s]=1;
        }
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d%d",&a,&b,&k);
            ans.init();
            ans.num[a]=1;
            for(int i=0;i<k;i++)
                ans=pows(ans);
            printf("%d\n",ans.num[b]);
        }
    }
    return 0;
}