HHUACM 暑假专题 数学

A - 求递推序列的第N项

矩阵快速幂，帮助大家搭建/测试自己的模板。
简单地讲一下原理，可以看到每一项用到了前两项的值，首先构造一个二维的向量$\left(\begin{matrix}
f(i-1) \\
f(i-2) \\
\end{matrix}\right)$，如果有常数就再加一维。那么将这个向量作为自变量，下一项就是$\left(\begin{matrix}
f(i) \\
f(i-1) \\
\end{matrix}\right)$。最后稍微动一下脑子配一个$2\times2$的系数矩阵使得$Cx_{i-1}=x_{i}$：
$$\left(\begin{matrix}
A & B \\
1 & 0 \\
\end{matrix}\right)
\left(\begin{matrix}
f(i-1) \\
f(i-2) \\
\end{matrix}\right)
=\left(\begin{matrix}
f(i) \\
f(i-1) \\
\end{matrix}\right)$$
复杂度$O(M^3logN)$，其中$M$为矩阵的大小，等于$2$。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MO=7;

struct Matrix {
    int r,c;
    ll e[2][2];
    Matrix() {}
    Matrix(int _r,int _c) {
        r=_r;c=_c;
        memset(e,0,sizeof(e));
    }
    Matrix(ll x) {
        r=c=2;
        memset(e,0,sizeof(e));
        for (int i=0;i<r;i++) {
            e[i][i]=x;
        }
    }
    Matrix operator *(const Matrix &b) {
        Matrix C(r,b.c);
        for (int i=0;i<r;i++) {
            for (int j=0;j<b.c;j++) {
                for (int k=0;k<c;k++) {
                    C.e[i][j]+=e[i][k]*b.e[k][j]%MO;
                    if (C.e[i][j]>=MO) C.e[i][j]%=MO;
                }
            }
        }
        return C;
    }
};

Matrix fpow(Matrix x,ll n)
{
    Matrix res(1);
    while (n) {
        if (n&1) {
            res=res*x;
        }
        x=x*x;
        n>>=1;
    }
    return res;
}

int main()
{
    int a,b,n;
    scanf("%d%d%d",&a,&b,&n);
    if (n<=2) {
        puts("1");
    } else {
        Matrix A(2,2);
        A.e[0][0]=a;
        A.e[0][1]=b;
        A.e[1][0]=1;
        A.e[1][1]=0;
        Matrix X(2,1);
        X.e[0][0]=1;
        X.e[1][0]=1;
        A=fpow(A,n-2);
        X=A*X;
        int ans=(X.e[0][0]%MO+MO)%MO;
        printf("%d\n",ans);
    }
    return 0;
}

B - Kinds of Fuwas

题意：四个角为同一种福娃的子矩形有多少个？
题解：从样例可以看出，一行或一列的矩形都不算。从数据范围来看，直接四个循环复杂度太高了，但是每个元素的值域很小，只有五个种类，所以可以考虑枚举每个种类来做。对于每个种类，比如H，我们可以利用类似最大子矩阵的套路，枚举两行作为上下界，然后再枚举每一列，对上下都是H的列进行计数，在这之中任取两列就是符合要求的矩形，所以把答案加上$C^{2}_{m}$即可，这个组合数可以$O(1)$求得。
复杂度$(KM^2N)$，其中$K$等于$5$。

#include <bits/stdc++.h>
using namespace std;

const char PP[9]="BJHYN";
const int N=256;
char mp[N][N];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i=0;i<n;i++) {
            scanf("%s",mp[i]);
        }
        long long ans=0;
        for (int p=0;p<5;p++) {
            for (int i=0;i<n;i++) {
                for (int j=i+1;j<n;j++) {
                    int t=0;
                    for (int k=0;k<m;k++) {
                        if (mp[i][k]==PP[p]&&mp[j][k]==PP[p]) ++t;
                    }
                    ans+=t*(t-1)/2;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C - GCD is Funny

题意：
在黑板上写有$n$个数，每次删掉$a,b,c$三个数并把$d$写两遍，$d$可以是$(a,b),(a,c),(b,c)$。在$n-2$次操作后会留下两个相同的数，输出这个数的所有可能情况。

题解：
这个题很难~~虽然出在某一场BC的A题~~。
首先要思考一下脱离具体过程，这个数到底是什么。题中的过程以下简称为“擦黑板”。

如果已经存在两个相同的数$x$，再取一个数$y$进行一次擦黑板，那么可以令$d=(x,x)=x$，剩下的数为$x,x$。可以发现$y$没有产生影响，两个$x$直接“吃掉”了$y$；
由1，我们可以单独考虑每一个$size\ge 3$的子集，它的结果一定是两个相同的数，其他的数直接吃掉就好。为了保证枚举的不重不漏，该子集内应该有尽量多的数参与$gcd$运算（注意，参与擦黑板$\neq$参与$gcd$运算），也就是$size-1$个数。因为第一次擦黑板一定有一个数无法参与$gcd$运算，而从第二次开始，有前一次得到的两个数$x$，再取一个数$y$进行一次擦黑板，那么可以令$d=(x,y)$，$y$一定能参与$gcd$运算。

综上，最后留在黑板上的数其实是任意一个$2\le size \le n-1$的子集的所有数的$gcd$。

接着再思考一下怎么巧妙地求出这些数，因为暴力枚举子集肯定是不行的。
首先注意到$a_i$的值域只有$1000$，而且$gcd$运算只会变小，所以这实际上也是答案的值域。
其次$gcd$有一个更强的性质，两个不一样的数取$gcd$，最大也只能是大数的一半。（为什么？）
所以我们写一个比较暴力的方法也能保证复杂度，最后要注意的一点就是不要取到全集，具体可以看代码。
复杂度$O(n^2+nV\cdot min(log(V),n-3))$，$V$为$a_i$的值域。

#include <bits/stdc++.h>
using namespace std;

const int MAX=1000;
int a[510];
bool b[MAX+5];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        int n;
        scanf("%d",&n);
        for (int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
        }
        memset(b,0,sizeof(b));
        for (int i=1;i<=n;i++) {
            for (int j=i+1;j<=n;j++) {
                b[__gcd(a[i],a[j])]=true;
            }
        }
        int num=2;
        bool flag=true;
        while (++num<n && flag) {
            flag=false;
            for (int i=1;i<=MAX;i++) {
                if (b[i]) {
                    for (int j=1;j<=n;j++) {
                        int y=__gcd(i,a[j]);
                        if (!b[y]) {
                            b[y]=true;
                            flag=true;
                        }
                    }
                }
            }
        }
        bool fi=true;
        for (int i=1;i<=1000;i++) {
            if (b[i]) {
                if (fi) {
                    printf("%d",i);
                    fi=false;
                } else {
                    printf(" %d",i);
                }
            }
        }
        puts("");
    }
    return 0;
}

D - Ant

题意：蚂蚁在一个长方体表面从起点爬到对角点的最短长度设为$L$，问所有最长边是$n$的长方体的$L^2$之和。
题解：出这题主要是想让大家牢记三个求和公式。
$$ \sum_{i=1}^{n}{i} = \frac{n(n+1)}{2} \\
\sum_{i=1}^{n}{i^2} = \frac{n(n+1)(2n+1)}{6} \\
\sum_{i=1}^{n}{i^3} = (\sum_{i=1}^{n}{i})^2 = \frac{n^2(n+1)^2}{4} $$
在表面上的路径实际上就是三种展开，所以$L^2=\min\{(x+y)^2+n^2,(n+x)^2+y^2,(n+y)^2+x^2\}$，因为在这个式子中$x+y+n$为定值，那么自然是两个数越接近越小，又有$x,y\le n$，所以$L^2=(x+y)^2+n^2$。
$$\begin{equation}\begin{split}
Ans &= \sum_{x=1}^{n}{\sum_{y=1}^{x}{(x+y)^2+n^2}} \\
&= \sum_{x=1}^{n}{x^3+n^2x+x^2(x+1)+\frac{x(x+1)(2x+1)}{6}} \\
&= \sum_{x=1}^{n}{\frac{7}{3}x^3+\frac{3}{2}x^2+(\frac{1}{6}+n^2)x} \\
&= \frac{7}{3}\frac{n^2(n+1)^2}{4}+\frac{3}{2}\frac{n(n+1)(2n+1)}{6}+(\frac{1}{6}+n^2)\frac{n(n+1)}{2} \\
&= \frac{1}{12}(13n^4+26n^3+17n^2+4n)
\end{split}\end{equation}$$
然后就是求个逆元乘一乘模一模就行了。
复杂度$O(1)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MO=1000000007;

ll fpow(ll x,ll n)
{
    ll res=1;
    for (;n;n>>=1,x=x*x%MO) {
        if (n&1) res=res*x%MO;
    }
    return res;
}

int main()
{
    ll INV12=fpow(12,MO-2);
    int T;
    scanf("%d",&T);
    while (T--) {
        ll n;
        scanf("%lld",&n);
        n%=MO;
        printf("%lld\n",n*(4+n*(17+n*(26+n*13%MO)%MO)%MO)%MO*INV12%MO);
    }
    return 0;
}

E - RPG的错排

首先预处理错排数和组合数，然后枚举一下猜错了多少人。
单组复杂度$O(n)$。
错排数的通项和递推式请参阅其他资料。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=26;
ll cp[N],C[N][N];

int main()
{
    cp[0]=1;
    for (int i=2;i<N/2;i++) {
        cp[i]=(cp[i-2]+cp[i-1])*(i-1);
    }
    for (int i=0;i<N;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;
    while (scanf("%d",&n)!=EOF&&n) {
        ll ans=0;
        for (int i=0;i<=n/2;i++) {
            ans+=C[n][i]*cp[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

F - Dertouzos

题意：$n$的真因子是不为$n$的因子。给出$n$和$d$，问有多少小于$n$的数的最大真因子是$d$。
题解：即$pd=m\lt n$，显然有

$p \le \frac{n-1}{d}$；
$p$必须为质数；(如若不然，则$p$有真因子$q$，$qd$是比$d$更大的$m$的真因子。)
$p \le c$，其中$c$为$d$的最小质因子。(如若不然，则$\frac{d}{c}\times p$是比$d$更大的$m$的真因子。)

由2，我们先做一遍筛法以及前缀和。再算出1的界，最后用筛出来的质数去算3的界。

注意点：用筛出来的质数去算3的界会有$O(\sqrt{d})$的复杂度，当$d$一直很大($\approx 10^{9}$)时会超时，而此时1的界必然比较小，应该在超过已有的界时及时退出。

#include <bits/stdc++.h>
using namespace std;

const int MAX=100010;
int tot=0,prime[100000];
bool isprime[MAX];
int sum[MAX];

void init()
{
    memset(isprime,1,sizeof(isprime));
    isprime[1]=false;
    for(int i=2; i<MAX; i++) {
        if(isprime[i])prime[++tot]=i;
        for(int j=1; j<=tot&&i*prime[j]<MAX; j++) {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0)break;
        }
    }
    for (int i=2;i<MAX;i++) {
        sum[i]=sum[i-1]+isprime[i];
    }
}

int T,n,d;
int getmaxp()
{
    for (int i=1;i<=tot;i++) {
        if (prime[i]>(n-1)/d) return prime[i-1];
        if (d%prime[i]==0) return prime[i];
        if (prime[i]*prime[i]>d) return min(d,(n-1)/d);
    }
    return -1;
}

int main()
{
    init();
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&d);
        printf("%d\n",sum[getmaxp()]);
    }
    return 0;
}

ps. 其实有一个更显然的做法，直接依次枚举质数即可。

G - One Person Game

抽象一下，有方程$ax+by+cz=B-A$成立，其中$c=a+b$，求$|x|+|y|+|z|$的最小值。
有个结论不太会证，简单来说，$x,y,z$均不为$0$时不会比有一个为$0$时更好。（把$a+b$变成$c$或者把$c$拆掉）
那么其实就是求满足$ax+by=C$的$|x|+|y|$的最小值，然后修改系数求三遍比较一下。
当$x,y$异号时，显然是让$x,y$都尽量接近0；当$x,y$同号时，因为系数都是正的，其实也是在$x$最接近$0$或者$y$最接近$0$的时候取到极值。
综上，我们只要分别考虑$x$最接近$0$和$y$最接近$0$的情况，各有两个。又因为C/C++的整除符号在被除数是负数时不是向下取整，我们可以更暴力地每次考虑三种情况。
复杂度$O(logV)$，$V$为$a,b$的值域大小。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF=1LL<<60;

long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
    if(a==0&&b==0) return -1;//无最大公约数
    if(b==0) {
        x=1;
        y=0;
        return a;
    }
    long long d=extend_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

ll calc(ll x,ll y)
{
    return abs(x)+abs(y);
}

ll solve(ll a,ll b,ll c)
{
    ll x,y,t;
    ll g=extend_gcd(a,b,x,y);
    if (c%g) return INF;
    a/=g;b/=g;c/=g;
    x*=c;y*=c;
    t=x/b;x-=b*t;y+=a*t;
    ll res=calc(x,y);
    res=min(res,calc(x-b,y+a));
    res=min(res,calc(x+b,y-a));
    t=y/a;x+=b*t;y-=a*t;
    res=min(res,calc(x,y));
    res=min(res,calc(x+b,y-a));
    res=min(res,calc(x-b,y+a));
    return res;
}

int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        ll A,B,a,b;
        scanf("%lld%lld%lld%lld",&A,&B,&a,&b);
        ll ans=solve(a,b,B-A);
        ans=min(ans,solve(a,a+b,B-A));
        ans=min(ans,solve(b,a+b,B-A));
        if (ans==INF) puts("-1");
        else printf("%lld\n",ans);
    }
    return 0;
}

—— Summon, Light!

HHUACM 暑假专题数学