NEFU大一暑假集训-同余

题集链接

OP

感谢学长的讲解与付出；
感谢ph和zsl两位大佬的指导与讨论；

夹点私货：
这些题涉及到的内容都已经更新到自己的笔记中：
数学（快速幂，欧拉函数，欧拉定理，扩展欧里几得算法，逆元）
树与图论（Prufer数列）
排列组合（lucas定理）

A Relatives

题目大意

对于给定n，输出小于n且与n互质的数的个数

思路

第一反应即是欧拉函数值，不过需要注意的是 φ(1)=1\varphi(1)=1 ，而按此题要求，对于1应输出0；

代码

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 <cstring>
#include <ctime>
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;

const ll N=1e7;
int p[N+7],c=0;//p[]存储第 i 个质数（from 0），c 作为末尾标记
bool n[N+7];//n[]存储整数 i 是否为质数，若标记 0 则为质数，标记 1 则为合数
void pri()
{
	n[0]=n[1]=1;//0，1 均不是质数
	for(int i=2;i<=N;i++)
	{
		if(!n[i])p[c++]=i;//若为质数，则加入 p 数组
		for(int j=0;j<c&&i*p[j]<=N;j++)
		{
			n[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
}

int main() {
    pri();
    ll g,ans;
    while(scanf("%lld",&g)&&g)
    {
        ans=g;
        if(g==1){printf("0\n");continue;}
        int sq=sqrt(g);
        for(int i=0;i<c&&p[i]<=sq;i++)
        {
            if(g%p[i]==0)
            {
                ans=ans-ans/p[i];
                while(g%p[i]==0)
                {
                    g/=p[i];
                }
            }
        }
        if(g>1)
        ans=ans-ans/g;
        printf("%lld\n",ans);
    }
    return 0;
}

B Brute-force Algorithm

题目大意

对于给定 a,b,P,n 输出func函数被执行的次数对P取模的模数；

思路

手动模拟发现，不考虑取模的情况下：
n=1,ans=a;n=2,ans=b;n=3,ans=ab;n=4,ans=ab2;n=5,ans=a2b3;n=6,ans=a3b5;n=1,ans=a;\\ n=2,ans=b;\\ n=3,ans=ab;\\ n=4,ans=ab^2;\\ n=5,ans=a^2b^3;\\ n=6,ans=a^3b^5;
假设n=in=i时，a和b的幂次分别为Ai,BiA_i,B_i，我们可以发现有Ai=Ai−1+Ai−2,Bi=Bi−1+Bi−2A_i=A_{i-1}+A_{i-2},B_i=B_{i-1}+B_{i-2} ，同时有A1=1,B1=0,A2=0,B2=1A_1=1,B_1=0,A_2=0,B_2=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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <algorithm>
#include <iostream>
#include <set>
#include <math.h>
#include <string.h>
using namespace std;
using ll = long long;

ll x, y, gn, m, phim;

ll qm(ll a, ll b)
{
    ll ans = 1 % m;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % m;
        a = a * a % m;
    }
    return ans;
}

struct mtx
{
    ll a[2][2];
};

mtx mul(mtx A, mtx B)
{
    mtx C;
    memset(C.a, 0, sizeof(C.a));
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
            {
                C.a[i][j] += A.a[i][k] * B.a[k][j];
                if(C.a[i][j]>phim)C.a[i][j] %= phim,C.a[i][j] += phim;
            }
    return C;
}

mtx mqm(mtx A, ll b)
{
    mtx ans;
    memset(ans.a, 0, sizeof(ans.a));
    for (int i = 0; i < 2; i++)
        ans.a[i][i] = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = mul(ans, A);
        A = mul(A, A);
    }
    return ans;
}

const ll N = 1000;
int p[N + 7], c = 0; //p[]存储第 i 个质数（from 0），c 作为末尾标记
bool n[N + 7];       //n[]存储整数 i 是否为质数，若标记 0 则为质数，标记 1 则为合数
void pri()
{
    n[0] = n[1] = 1; //0，1 均不是质数
    for (int i = 2; i <= N; i++)
    {
        if (!n[i])
            p[c++] = i; //若为质数，则加入 p 数组
        for (int j = 0; j < c && i * p[j] <= N; j++)
        {
            n[i * p[j]] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
}

ll gphi(ll g)
{
    ll ans = g;
    if (g == 1)
        return 0;
    int sq = sqrt(g);
    for (int i = 0; i < c && p[i] <= sq; i++)
    {
        if (g % p[i] == 0)
        {
            ans = ans - ans / p[i];
            while (g % p[i] == 0)
            {
                g /= p[i];
            }
        }
    }
    if (g > 1)
        ans = ans - ans / g;
    return ans;
}

int main()
{
    pri();
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        scanf("%lld%lld%lld%lld", &x, &y, &m, &gn);
        if (m == 1)
        {
            printf("Case #%d: %lld\n", i, 0);
            continue;
        }
        else if (gn == 1)
        {
            printf("Case #%d: %lld\n", i, x%m);
            continue;
        }
        phim = gphi(m);
        mtx k = {{{0, 1}, {1, 1}}};
        k = mqm(k, (gn - 2));
        //printf("%lld ",phim);
        //printf("%lld %lld ",k.a[1][0],k.a[1][1]);
        ll ans = qm(x, k.a[1][0]) * qm(y, k.a[1][1]) % m;
        //
        printf("Case #%d: %lld\n", i, ans);
    }
}

C Sum

题目大意

设 S(k)S(k) 为将N拆分为k份的方案数，对于给定N，求∑i=1nS(i)\sum_{i=1}^nS(i) 对1e9+7取模的值；

思路

由插板法可知 S(k)=Cn−1k−1S(k)=C_{n-1}^{k-1} ，故 ∑i=1nS(i)=2n−1\sum_{i=1}^nS(i)=2^{n-1}；
接下来对2进行降幂即可；

代码

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
#include <algorithm>
#include <iostream>
#include <set>
#include <math.h>
#include <string.h>
using namespace std;
using ll = long long;

const ll m=1e9+7;

ll qm(ll a, ll b)
{
    ll ans = 1 % m;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % m;
        a = a * a % m;
    }
    return ans;
}

int main()
{
    string g;
    ll mi=0;
    while(cin>>g)
    {
        mi=0;
        for(int i=0;g[i];i++)
        {
            mi*=10;
            mi+=g[i]-'0';
            mi%=m-1;
        }
        mi-=1;
        if(mi<0)mi+=m-1;
        //printf("%lld ",mi);
        printf("%lld\n",qm(2,mi));
    }
}

D 同余方程

思路

实际上即是求a对b的逆元，题目保证有解即逆元存在；

由于未保证b为质数，qm(a,b-2)的方法便无法使用，我们可以用扩展欧几里得算法求解；

代码

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
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <set>
#include <math.h>
#include <string.h>
using namespace std;
using ll = long long;

const ll m=1e9+7;

ll qm(ll a, ll b)
{
    ll ans = 1 % m;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % m;
        a = a * a % m;
    }
    return ans;
}

ll exgcd(ll a,ll b,ll &x,ll &y)
{
   if(!b)
   {
      x=1,y=0;
      return a;
   }
   ll ans=exgcd(b,a%b,x,y);
   ll y1=y,x1=x;
   x=y1;
   y=x1-a/b*y1;
   return ans;
}

int main()
{
    ll a,b;
    cin>>a>>b;
    ll x,y;
    exgcd(a,b,x,y);
    printf("%lld",(x%b+b)%b);//防负
}

E SHUFFLE 洗牌

思路

简单模拟可以发现，洗牌是会循环进行的，即顺序牌洗若干次之后便会回到顺序，首先的处理我们可以将洗牌次数对循环长度取模；

分析易知对于原来第 i 位的牌，洗过一次后即为第 2*i+((i<=n>>1)?0:-(n+1))位；

如果洗牌次数对循环长度（m）取模后还剩n次，即可认为洗完n次后第L位的牌，再洗m-n次即可回到本身位置；

由此我们可以找出洗n次后第L位的牌是几号牌了；

代码

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
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <set>
#include <math.h>
#include <string.h>
using namespace std;
using ll = long long;

int main()
{
    ll n,m,l;
    cin>>n>>m>>l;
    int ccl=0;
    ll i=1;
    do
    {
        ccl++;
        i=2*i+((i<=n>>1)?0:-(n+1));
    } while (i!=1);
    m%=ccl;
    m=ccl-m;
    i=l;
    for(int j=1;j<=m;j++)
    {
        i=2*i+((i<=n>>1)?0:-(n+1));
    }
    cout<<i;
}

F 树的计数

思路

此题是Prufer数列的一个结论
在这里插入图片描述
在实际解决中，还需要特判不成树的数据；

代码

（我认为的）正解代码：
预处理组合数的值，由于总答案小于1e17，所以每个组合数不会超过1e17，而且组合数的范围一定小于 C150150C_{150}^{150} ；

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
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <set>
#include <math.h>
#include <string.h>
using namespace std;
using ll = long long;

//const ll M=100000000000000013;
ll c[152][152];
int n;
 void pre(){
	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]+c[i-1][j-1];
	}
}
ll lefts[152],d[152];
int main()
{
    cin>>n;
    pre();
    ll sum=0,ans=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&d[i]);
        sum+=d[i];
        if((!d[i]&&n!=1)||d[i]<0){printf("0");return 0;}
        else if(!d[i]&&n==1){printf("1");return 0;}
        lefts[i]=lefts[i-1]+d[i]-1;
        ans*=c[n-2-lefts[i-1]][d[i]-1];
    }
    if(sum==2*n-2)printf("%lld",ans);
    else printf("0");
    return 0;
}

在vj上AC，但是在洛谷上被一组样例卡的代码：（目前不知道原因）
如果保证答案小于1e17，是不是可以等价于答案可以对1e17+3（大于1e17的最小质数）取模？

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
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <set>
#include <math.h>
#include <string.h>
using namespace std;
using ll = long long;

const ll M=100000000000000003;

ll qm(ll a, ll b)
{
    ll ans = 1 % M;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % M;
        a = a * a % M;
    }
    return ans;
} 
ll comp(ll a,ll b,ll m){
    if(a<b) return 0;
    if(a==b) return 1;
    if(b>a-b) b=a-b;
    ll ans=1,ca=1,cb=1;
    for(int i=0;i<b;i++){
        ca=ca*(a-i)%m;
        cb=cb*(b-i)%m;
    }
    ans=ca*qm(cb,m-2)%m;
    return ans;
}
/*
ll lucas(ll a,ll b,ll m){
    ll ans=1;
    while(a&&b){
        ans=(ans*comp(a%m,b%m,m))%m;
        a/=m;
        b/=m;
    }
    return ans;
}
*/
ll lefts[152],d[152];
int main()
{
    int n;
    cin>>n;
    ll sum=0,ans=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&d[i]);
        sum+=d[i];
        if(!d[i]&&n!=1){printf("0");return 0;}
        lefts[i]=lefts[i-1]+d[i]-1;
        ans*=comp(n-2-lefts[i-1],d[i]-1,M);
        ans%=M;
    }
    if(sum==2*n-2)printf("%lld",ans);
    else printf("0");
}

G AquaMoon and Chess

题目大意

给定格子总数和占用情况，棋子可以以类似于跳棋的规则移动，求含初始状态一共可能存在多少种可能情况（对 998,244,353998,244,353 求余）；

思路

简单模拟后发现此问题与组合数有关，具体规律并不好描述，详见代码；

（目前还没证明）答案可以用以下规律抽象表示：
假设每个独立的占用区间长度为 lil_i，格子中共有zz个0，（满足格子总数=z+∑i=1nliz+\sum_{i=1}^{n}l_i），答案为 Cz+∑i=1n⌊li2⌋zC_{z+\sum_{i=1}^{n}\lfloor \frac {l_i} 2\rfloor}^z；

代码

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
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <set>
#include <math.h>
#include <string.h>
using namespace std;
using ll = long long;

const ll M=998244353;

ll qm(ll a, ll b)
{
    ll ans = 1 % M;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % M;
        a = a * a % M;
    }
    return ans;
} 
ll comp(ll a,ll b,ll m){
    if(a<b) return 0;
    if(a==b) return 1;
    if(b>a-b) b=a-b;
    ll ans=1,ca=1,cb=1;
    for(int i=0;i<b;i++){
        ca=ca*(a-i)%m;
        cb=cb*(b-i)%m;
    }
    ans=ca*qm(cb,m-2)%m;
    return ans;
}

ll lucas(ll a,ll b,ll m){
    ll ans=1;
    while(a&&b){
        ans=(ans*comp(a%m,b%m,m))%m;
        a/=m;
        b/=m;
    }
    return ans;
}

int main()
{
    int t,lo;
    cin>>t;
    string g;
    while(t--)
    {
        scanf("%d",&lo);
        cin>>g;
        ll n=0,m=0,l=-1,i;
        for(i=0;i<lo;i++)
        {
            if(g[i]=='0')
            {
                m++,n++;
                n+=(i-l-1)>>1;
                l=i;
            }
        }
        n+=(i-l-1)>>1;
        printf("%lld\n",lucas(n,m,M));
    }
}

ED

做这个题中大量用到自己以前准备的板子，同时也发现了网上扒下来的板子存在的很多问题和错误，大家注意辨别~

算法竞赛 > 比赛与题集
NEFU大一暑假集训-同余
https://tanyuu.github.io/2021.07-12/NEFU大一暑假集训-同余/
作者
F Juny
发布于
2021年8月5日
许可协议