Rainy2k
0%

数论

Posted on Edited on In

数论相关的题目

盒子-组合数

隔板法；

子问题：给定n个物品，将它们分成m堆，保证每堆的物品个数不少于h个

则有Cn−m∗h−1m−1C_{n-m*h-1}^{m-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
#include <bits/stdc++.h>
#include<stdint.h>
using namespace std;
#define int long long
#define scan(n) scanf("%lld", &(n))
#define scann(n, m) scanf("%lld%lld", &(n), &(m))
#define scannn(a, b, c) scanf("%lld%lld%lld", &(a), &(b), &(c))
#define prin(n) printf("%lld", (n))
#define pb push_back
#define mp make_pair
#define ms(a) memset(a, 0, sizeof(a))
#define fo(i, a, b) for (int i = (a); i <= (b); i++)
#define ro(i, a, b) for (int i = (a); i >= (b); i--)
#define dbg(args...) do {cout << #args << " : "<< args << endl;} 
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+100;
const int mod=1e9+7;

int f[maxn],inv[maxn];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;;
        b/=2;
    }
    return res;
}
void init(){
    f[0]=1;
    for(int i=1;i<=maxn-1;i++)f[i]=f[i-1]*i%mod;
    inv[maxn-1]=qpow(f[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m){
    return f[n]*inv[m]%mod*inv[n-m]%mod;
}
int32_t main() {
    int f,w,h;
    cin>>f>>w>>h;
    int fm=0,fz=0;
    init();
    for(int i=1;i<=w;i++){
        fm+=(C(w-1,i-1)*C(f+1,i))%mod;
        fm%=mod;
    }
    for(int i=1;i<=w/(h+1);i++){
        fz=fz+C(w-i*h-1,i-1)*C(f+1,i)%mod;
        fz%=mod;
    }
    int ans=fz*qpow(fm,mod-2)%mod;
    cout<<ans<<endl;
    return 0;
}

组合数部分：

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=1;i<=w;i++){
        fm=fm+(C(w-1,i-1)*C(f-1,i-1))*2%mod;
        fm=fm+(C(w-1,i-1)*C(f-1,i-2))%mod;
        fm=fm+(C(w-1,i-1)*C(f-1,i))%mod;
        fm%=mod;
    }
    for(int i=1;i<=w/(h+1);i++){
        fz=fz+C(w-i*h-1,i-1)*C(f-1,i-1)*2%mod;
        fz=fz+C(w-i*h-1,i-1)*C(f-1,i-2)%mod;
        fz=fz+C(w-i*h-1,i-1)*C(f-1,i)%mod;
        fz%=mod;
    }

可以合并为：

1
2
3
4
5
6
7
8
for(int i=1;i<=w;i++){
    fm+=(C(w-1,i-1)*C(f+1,i))%mod;
    fm%=mod;
}
for(int i=1;i<=w/(h+1);i++){
    fz=fz+C(w-i*h-1,i-1)*C(f+1,i)%mod;
    fz%=mod;
}

找质数-素数筛

因为数字范围<=1e14<=1e14,所以在快速幂的过程中会爆long long，要用__int128

也可以结合费马小定理 ap−1 mod p==1a^{p-1} \ mod \ p == 1,P为质数，已知质数间隔小于200

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
#include <bits/stdc++.h>
#include<stdint.h>
using namespace std;
const int maxn=1e7;
__int128 read(){
	__int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void print(__int128 x){/*__int128输出*/
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
struct Prime{
    int prime_cnt;
    int prime[maxn+5],vis[maxn+5];
    int p[maxn+5];
    void Prime_init(){/*将合数标记为vis[i]=1*/
        prime_cnt=0;
        for(int i=2;i<=maxn;i++){
            if(!vis[i])prime[++prime[0]]=i;
            for(int j=1;j<=prime[0]&&i*prime[j]<=maxn;j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0)break;
            }   
        }
        /*prime_cnt记录素数的数量*//*p数字记录每个素数*/
        for(int i=2;i<maxn;i++)if(!vis[i])p[++prime_cnt]=i;
    }
    bool isprime(__int128 x){
        for(int i=1;i<=prime_cnt;i++){
            if(p[i]>=x)return true;
            if(x%p[i]==0)return false;
        }
        return true;
    }
}F;
__int128 qpow(__int128 a,__int128 b,__int128 mod){/*快速幂*/
    __int128 res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int32_t main() {
    int T;cin>>T;
    F.Prime_init();
    while(T--){
        __int128 a,p;p=read(),a=read();
        for(__int128 q=p-1;q>=1;q--){
            if(F.isprime(q)){
                __int128 ans=qpow(a,q,p);
                print(ans);
                printf("\n");
                break;
            }
        }
    }
    return 0;
}

矩阵快速幂

Happy Necklace

注意状态的转移，很有意思~

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
#include <bits/stdc++.h>
#include<stdint.h>
using namespace std;
#define int long long
#define scan(n) scanf("%lld", &(n))
#define ms(a) memset(a, 0, sizeof(a))
#define fo(i, a, b) for (int i = (a); i <= (b); i++)
#define ro(i, a, b) for (int i = (a); i >= (b); i--)
#define dbg(args...) do {cout << #args << " : "<< args << endl;} 
const int inf = 0x3f3f3f3f;
const int mod=1e9+7;
const int N=3;
struct matrix{
    int m[N+1][N+1];
};
matrix e,d;
matrix qpow(matrix a,int b){
    matrix ans=e;
    while(b){
        if(b&1){
            matrix x=d;
            for(int i=0;i<=N-1;i++)
                for(int j=0;j<=N-1;j++)
                    for(int k=0;k<=N-1;k++)
                        x.m[i][j]=x.m[i][j]%mod+ans.m[i][k]*a.m[k][j]%mod;
            ans=x;
        }
        matrix x=d;
        for(int i=0;i<=N-1;i++)
            for(int j=0;j<=N-1;j++)
                for(int k=0;k<=N-1;k++)
                    x.m[i][j]=x.m[i][j]%mod+a.m[i][k]*a.m[k][j]%mod;
        a=x;
        b>>=1;
    }
    return ans;
}

int32_t main(){
    int T;scan(T);
    matrix base,m;
    for(int i=0;i<=N-1;i++){
        for(int j=0;j<=N-1;j++){
            base.m[i][j]=0;
            m.m[i][j]=0;
            e.m[i][j]=0;
            d.m[i][j]=0;
        }
    }
    base.m[0][0]=1;
    base.m[1][0]=1;
    base.m[2][0]=1;
    m.m[0][0]=1;m.m[0][1]=0;m.m[0][2]=1;
    m.m[1][0]=1;m.m[1][1]=0;m.m[1][2]=0;
    m.m[2][0]=0;m.m[2][1]=1;m.m[2][2]=0;
    for(int i=0;i<=N-1;i++)e.m[i][i]=1;
    while(T--){
        int n;scan(n);
        int ans=0;
        if(n==1)ans=2;
        else if(n==2)ans=3;
        else{
            matrix temp=qpow(m,n-2);
            matrix x=d;
            for(int i=0;i<=N-1;i++)
                for(int j=0;j<=N-1;j++)
                    for(int k=0;k<=N-1;k++)
                        x.m[i][j]=x.m[i][j]%mod+temp.m[i][k]*base.m[k][j]%mod;
            temp=x;
            ans=temp.m[0][0]+temp.m[1][0]+temp.m[2][0];
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
}

Recursive sequence

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
#include <bits/stdc++.h>
#include<stdint.h>
#define int long long
#define scan(n) scanf("%lld", &(n))
#define scann(n, m) scanf("%lld%lld", &(n), &(m))
#define scannn(a, b, c) scanf("%lld%lld%lld", &(a), &(b), &(c))
#define pb push_back
#define fo(i, a, b) for (int i = (a); i <= (b); i++)
const int N=8;//N个系数，N维矩阵
using namespace std;
const int mod=2147493647;
struct matrix{int m[10][10];};
matrix ans,base,m;
int n,a,b;
matrix multi(matrix a, matrix b){
    matrix tmp;
    for(int i=1;i<=N;++i){
        for (int j=1;j<=N;++j){
            tmp.m[i][j]=0;
            for(int k=1;k<=N;++k)
                tmp.m[i][j]=(tmp.m[i][j]+(a.m[i][k]*b.m[k][j]))%mod;
        }
    }
    return tmp;
}
matrix fastm(matrix base, int n){
    matrix ans;
    memset(ans.m,0,sizeof(ans.m));
    for (int i=1;i<=N;i++)ans.m[i][i]=1;
    while(n){
        if(n&1)ans=multi(ans,base);
        base=multi(base, base);
        n>>=1;
    }
    return ans;
}
int32_t main(){
    matrix m,ans;
    memset(m.m,0,sizeof(m.m));
    m.m[1][1]=1;m.m[1][2]=2;m.m[1][4]=1;m.m[1][5]=4;m.m[1][6]=6;m.m[1][7]=4;m.m[1][8]=1;
    m.m[2][1]=1;
    m.m[3][2]=1;
    m.m[4][4]=1;m.m[4][5]=4;m.m[4][6]=6;m.m[4][7]=4;m.m[4][8]=1;
    m.m[5][5]=1;m.m[5][6]=3;m.m[5][7]=3;m.m[5][8]=1;
    m.m[6][6]=1;m.m[6][7]=2;m.m[6][8]=1;
    m.m[7][7]=1;m.m[7][8]=1;
    m.m[8][8]=1;
    int T;scan(T);
    while(T--){
        scannn(n,a,b);
        ans = fastm(m,n-3);
        int f[10],x=0;
        f[3]=a,f[2]=b,f[1]=(2*a+b+3*3*3*3),f[4]=3*3*3*3,f[5]=3*3*3,f[6]=3*3,f[7]=3,f[8]=1;
        fo(i,1,8){
            x=x%mod+((f[i]%mod)*(ans.m[1][i])%mod)%mod;
            x%=mod;
        }
        printf("%lld\n",x);
    }
    return 0;

矩阵快速幂，用于求解递推式。