Dylan's Blog
0%

Posted on Edited on In

问题描述：

石头游戏在一个n行m列的方格阵上进行。每个格子对应了一个编号在0~9之间的操作序列。操作序列是一个长度不超过6且循环执行、每秒执行一个字符的字符串。它包括： 1. 数字0~9：拿0~9个石头到该格子。 2. NWSE：把这个格子内所有的石头推到相邻的格子。 3. D：拿走这个格子的石头。

石头游戏的问题是：当这个石头游戏进行了t秒之后，所有方格中最多的格子有多少个石头。

输入：

第一行三个整数n, m, t, act。 接下来n行，每行m个字符，表示每个格子对应的操作序列。 最后act行，每行一个字符串，表示从0开始的每个操作序列。

输出：

一个整数：游戏进行了t秒之后，所有方格中最多的格子有多少个石头。

思路：

这种矩阵加速递推的题重点是建模和构造矩阵。好有趣啊。。

我们可以将方格阵的两位压到一维上，那么状态矩阵$f$就是一个$1*nm$的矩阵。因为操作序列的长度不超过6，所以操作最多60次一个循环，因此我们可以对于每一次设计一个转移矩阵。然后转移矩阵$a$的构造方法是： 1. 如果位置$i,j$的操作为”WENS”，那么我们就令$a[pos(i,j)][pos(i’,j’)]=1$。其中$i’,j’$为操作的对应位置。 2. 如果位置$i,j$的操作为数字$x$，那么我们就令$a[0][pos(i,j)]=x$。 3. 另外我们要保证$a[0][0]=1$

这样我们就是把状态矩阵$f[0]$当成了石头来源，$a[0][0]=1$保证了$f[0]=1$。转移矩阵构造好以后就利用矩阵快速幂优化一下递推，这个就不多说了。主要还是构造转移矩阵，就像网络流主要是建图一样。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 100
#define LL long long
#define pos(i, j) (i-1)*m+j
using namespace std;

int n, m, t, act, len[MAXN], op[MAXN][MAXN];
LL maxn, ans[MAXN][MAXN], a[MAXN][MAXN][MAXN], b[MAXN][MAXN];
char opt[MAXN][MAXN];

void init()
{
    ans[0][0]=1;
    for(int i=0; i<=pos(n, m); i++) b[i][i]=1;
    for(int i=0; i<60; i++) a[i][0][0]=1;
}

void mul(LL x[MAXN][MAXN], LL y[MAXN][MAXN])
{
    LL c[MAXN][MAXN];
    memset(c, 0, sizeof(c));
    for(int i=0; i<=n*m; i++)
        for(int j=0; j<=n*m; j++)
            for(int k=0; k<=n*m; k++) c[i][j]+=x[i][k]*y[k][j];
    memcpy(x, c, sizeof(c));
}

void ksm(int y)
{
    while(y)
    {
        if(y&1) mul(ans, b);
        mul(b, b); y>>=1;
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &t, &act);
    init();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) scanf("%1d", &op[i][j]);
    for(int i=0; i<act; i++)
    {
        scanf("%s", opt[i]);
        len[i]=strlen(opt[i]);
    }
    for(int k=0; k<60; k++)
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                char act=opt[op[i][j]][k%len[op[i][j]]];
                if(act=='E' && j<m) a[k][pos(i, j)][pos(i, j+1)]=1;
                if(act=='N' && i>1) a[k][pos(i, j)][pos(i-1, j)]=1;
                if(act=='W' && j>1) a[k][pos(i, j)][pos(i, j-1)]=1;
                if(act=='S' && i<n) a[k][pos(i, j)][pos(i+1, j)]=1;
                if(act>='0' && act<='9')
                {
                    a[k][pos(i, j)][pos(i, j)]=1;
                    a[k][0][pos(i, j)]=act-'0';
                }
            } 
        mul(b, a[k]);
    }
    ksm(t/60);
    for(int i=0; i<t%60; i++) mul(ans, a[i]);
    for(int i=1; i<=n*m; i++) maxn=max(maxn, ans[0][i]);
    printf("%lld\n", maxn);
}

Posted on Edited on In

问题描述：

你需要求出$A^B$的所有约数之和。

输入：

只有两个数A，B $(1<=A,B<=5*10^7)$

输出：

一个数，约数之和($mod 9901$)

思路：

一开始不知道算术基本定理时看得比较懵逼。。。后面才发现是傻逼题。。

首先任何大于1的正整数$N$都可以分解成$ N =p_1^{c_1}p_2^{c_2}p_3^{c_3}···p_m^{c_m} $的形式，其中$c_i$为正整数，$p_1<p_2<p_3<···<p_m$且$p_i$均为质数。根据这个我们可以有个推论就是$N$的正约数之和为$ \prod_{i=1}^m (\sum_{j=0}^{c_i} p_i ^j) $。

这样就很容易得得出这题的答案:$ ans= \prod_{i=1}^m (\sum_{j=0}^{c_i*B} p_i ^j) $。这个就可以用等比数列的求和公式来求，要注意的就是除要变成乘逆元，当逆元不存在时要特判。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define MAXN 1000005
#define mod 9901
#define LL long long
using namespace std;

LL a, b, c[MAXN][2], ans=1, cnt;

void div(LL num)
{
    for(int i=2; i*i<=num; i++)
        if(num%i==0)
        {
            c[++cnt][0]=i;
            while(num%i==0) c[cnt][1]++, num/=i;
        }
    if(num!=1) c[++cnt][0]=num, c[cnt][1]=1;
}

LL ksm(LL x, LL y)
{
    LL ans=1;
    while(y)
    {
        if(y&1) ans=(x*ans)%mod;
        x=(x*x)%mod; y>>=1;
    }
    return ans;
}

LL sum(LL x, LL y)
{
    if(y==0) return 1;
    if(y&1) return (1+ksm(x, y/2+1))*sum(x, y/2)%mod;
    else return ((1+ksm(x, y/2+1))*sum(x, y/2-1)+ksm(x, y/2))%mod;
}

int main()
{
    while(scanf("%lld%lld", &a, &b)!=EOF)
    {
        div(a);
        for(int i=1; i<=cnt; i++) ans=sum(c[i][0], c[i][1]*b)*ans%mod;
        printf("%lld\n", ans);
    }
}

Posted on Edited on In

问题描述：

给你一组形如下图的方程组： EXCRT

你需要解出最小的$x$。

输入：

有多组数据，每组数据以$n$开始，表示有$n$个方程组 接下来n行分别表示$a_1$，$m_i$

输出：

输出最小的$x$

思路：

这就是扩展中国剩余定理的模板题了。如果$m_i$都两两互质，那么就是直接中国剩余定理就好了。但这里$m_i$是随机的，所以要用到一些其他的处理手法。

这里我们可以先用扩展欧几里得求出第一组方程：$x+y*m_1=a_1$。这样，我们得到了一组通解$x=x_0+t*m_1$。我们利用这组通解带入第二组方程，得到：变形为：于是我们得到了另一个线性同余方程，并且可以解出$t$的通解。利用这个通解又可以代入下一个方程。于是我们可以这样推出整个方程的解。

用数学归纳法再严谨地说一遍做法：设已经求出了$k$组方程，$ m_0= \prod_{i=1}^{k} m_i$，前$k$组方程的通解为$x=x_0+t*m_0$。那么我们可以将通解代入第$k+1$组方程中，得到 再利用扩展欧几里得解出新方程的通解。于是，我们可以利用$n$次扩展欧几里得解出计算出答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;

LL n, a[10000005], r[10000005];

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b==0)
    {
        x=1; y=0;
        return a;
    }
    LL d=exgcd(b, a%b, x, y);
    LL z=x; x=y; y=z-y*(a/b);
    return d;
}

LL solve()
{
    LL x=0, y=0, x0=0, m0=1;
    for(int i=1; i<=n; i++)
    {
        LL d=exgcd(m0, a[i], x, y);
        if((r[i]-x0)%d) return -1;
        x=(r[i]-x0)/d*x%a[i];
        x0=(x0+x*m0)%(m0/d*a[i]);
        m0=m0/d*a[i];
    }
    return (x0+m0)%m0;
}

int main()
{
    while(scanf("%lld", &n)!=EOF)
    {
        for(int i=1; i<=n; i++) scanf("%lld%lld", &a[i], &r[i]);
        printf("%lld\n", solve());
    }
}

Posted on Edited on In

问题描述：

我们要找出一个最小的 $L$ 的只由$8$构成的数，使它是$L$的整数倍。

输入：

由多组数据，每组数据一个数 $L$，输入以$0$结束 $L$($1≤L≤2000000000$)

输出：

一个数，表示数字的长度。如果不存在则输出$0$

思路：

一道比较玄学的题。这种只由一种数字构成相关问题都是一个套路吧。

先是将$8888…8$看成$(10^k-1)/9*8$。于是 $9L|8(10^k-1)$，等价为$10^k \equiv 1 (mod \frac{9L}{gcd(8, L)})$，这是一步特别重要的转化。

然后有这样的一个模型：若正整数$a, n$互质，那么满足$a^k \equiv 1 (mod n)$ 的最小正整数$k_0$一定是$ \varphi (n)$ 的约数。

因此，$k$一定为 $\varphi ( \frac{9L}{gcd(8, L)} ) $的约数。然后我们就可以枚举约数，再使用快速幂验证就OK了。有一个细节就是 $\varphi (n)$会大于MAX_INT所以要注意要再用快速乘防止爆$long long$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include 
#include 
#include 
#include 
#define LL long long
using namespace std;

LL l, Case, fac[20000005];

LL gcd(LL x, LL y)
{
    return y==0 ? x : gcd(y, x%y);
}

LL phi(LL n)
{
    LL ans=n;
    for(LL i=2; i*i<=n; i++)
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

LL ksc(LL x, LL y, LL p)
{
    LL ans=0;
    x%=p; y%=p;
    while(y)
    {
        if(y&1) ans=(ans+x)%p;
        x=(x+x)%p; y>>=1;
    }
    return ans;
}

LL ksm(LL x, LL y, LL p)
{
    LL ans=1;
    while(y)
    {
        if(y&1) ans=ksc(ans, x, p);
        x=ksc(x, x, p); y>>=1;
    }
    return ans;
}

int main()
{
    while(scanf("%lld", &l) && l)
    {
        int flag=0, cnt=0;;
        LL t1=l*9/gcd(l, 8);
        LL t2=phi(t1);
        for(LL i=1; i*i<=t2; i++)
            if(t2%i==0) fac[++cnt]=i, fac[++cnt]=t2/i;
        sort(fac+1, fac+cnt+1);
        for(LL i=1; i<=cnt; i++)
            if(ksm(10, fac[i], t1)==1)
            {
                printf("Case %lld: %lld\n", ++Case, fac[i]);
                flag=1;
                break;
            }
        if(!flag) printf("Case %lld: 0\n", ++Case);
    }
}

Posted on Edited on In

问题描述：

给出正整数$n$和$k$，计算$G(n, k) =k \% 1 + k \% 2 + … + k \% n$的值。

输入：

输入仅一行，包含两个整数$n$, $k$ ($1<=n, k<=10^9$)

输出：

输出仅一行，即$j(n, k)$。

思路：

直接计算原式肯定是会T的。。。我们可以根据 $a \% b=a-\lfloor a/b \rfloor *b$ 将原式变形。所以答案可以在$n*k$的基础上减去上式的后一部分得到。然后我们可以发现 $\lfloor a/b \rfloor$ 的取值是一段一段的，所以可以对于每一段用等差数列求和的公式得出答案。

复杂度似乎是$O( \sqrt{n} )$的

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include 
#define LL long long
using namespace std;

LL n, k, ans;

int main()
{
    scanf("%lld%lld", &n, &k);
    ans=n*k;
    if(n>k) n=k;
    for(LL l=1, r; l<=n; l=r+1)
    {
        LL temp=k/l; r=min(k/temp, n);
        ans-=temp*(l+r)*(r-l+1)/2;
    }
    printf("%lld\n", ans);
}