古代猪文

213. 古代猪文 - AcWing题库

数论好题

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
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N = 37000;
const int MOD = 999911658;
int plist[5] = {0,2,3,4679,35617};
int n,q;
int a1,a2,a3,a4;
int fac[N],a[N];
inline int gcd(int a,int b) {
    if(b == 0) return a;
    else return gcd(b,a % b);
}
inline int ksm(int base,int power,int mod) {
    int res = 1;
    while(power) {
        if(power & 1) {
            res = res * base % mod;
        }
        base = base * base % mod;
        power = power >> 1;
    }
    return res;
}
inline void init(int mod) {
    fac[0] = 1;
    for(int i = 1 ; i <= mod ; i ++)
        fac[i] = fac[i - 1] * i % mod;
}
inline int ni(int x,int mod) {//预处理阶乘的逆元
    return ksm(fac[x],mod - 2,mod);
}
inline int C(int n,int m,int mod) {
    if(m > n) return 0;
    return fac[n] * ni(m,mod) % mod * ni(n - m,mod) % mod;
}
inline int Lucas(int n,int m,int mod) {//卢卡斯定理
    if(n < m) return 0;
    if(n == 0) return 1;
    return Lucas(n / mod,m / mod,mod) * C(n % mod,m % mod,mod) % mod;
}
inline void memge(long long &a1,long long &m1,long long a2,long long m2) {//合并素数
    if(m2>m1) swap(m1,m2),swap(a1,a2);
    while(a1%m2!=a2)a1=a1+m1;
    m1 =(m2/gcd(m1,m2))*m1;
}
void CRT() {//扩展中国剩余定理
    int m1 = plist[1],a1 = a[1];
    a1 %= m1;
    for(int i = 2 ; i <= 4 ; i ++) {
        int m2 = plist[i],a2 = a[i];
        a2 %= m2;
        memge(a1,m1,a2,m2);
    }
    cout<<ksm(q,(a1 + m1) % m1,MOD + 1);
}
signed main() {
    scanf("%lld%lld",&n,&q);
    if(q % (MOD + 1) == 0) {
        cout << 0;
        return 0;
    }
    for(int i = 1 ; i <= 4 ; i ++) {
        init(plist[i]);
        for(int j = 1 ; j * j <= n ; j ++) {
            if(n % j == 0) {
                a[i] = (a[i] + Lucas(n,j,plist[i])) % plist[i];
                if(j * j != n) {
                    a[i] = (a[i] + Lucas(n,n / j,plist[i])) % plist[i];
                }
            }
        }
    }
    CRT();
    return 0;
}

数列

数列 - 题目 - Daimayuan Online Judge

思维题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int d, m;
void solve() {
    cin >> d >> m;
    int ans = 1;
    int tmp = d;
    vector<int> v;
    for(int i = 1; i <= tmp; i <<= 1) {
        v.push_back(i+1);
        tmp -= i;
    }
    if(tmp) v.push_back(tmp + 1);
    for(int i = 0; i < v.size(); i++) {
    	ans = ans * v[i] % m;
    }
    if(!ans) ans = m - 1;
    else ans--;
    cout << ans << endl;
}

多重集组合数

n种物品，第i种物品有ai个，不同种类物品可以互相区分但是相同种类无法区分。从这些物品中取出m个，求方案数。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define MAXN 1005
#define INF 0x3f3f3f3f
#define MOD 1000000
int dp[MAXN][MAXN*10];
int n,tot,s,b;
int a[MAXN];
int main()  
{
    scanf("%d %d %d %d",&n,&tot,&s,&b);
    for(int i=1;i<=tot;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        a[tmp]++;
    }
    for(int i=0;i<=n;i++)
        dp[i][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=b;j++)
            if(j-1-min(j,a[i])>=0)
                dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1-min(j,a[i])]+MOD)%MOD;
            else dp[i][j]=(dp[i][j-1]+dp[i-1][j])%MOD;             
    int ans=0; 
    for(int i=s;i<=b;i++)
        ans=(dp[n][i]+ans)%MOD;
    printf("%d\n",ans);
    return 0;
}