https://ac.nowcoder.com/acm/contest/317/H

C++版本一

std

题解：

 

#include<cstdio>
#include<cstring>
#define int long long 
#define LL int
const int MAXN = 2e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, mod, prime[MAXN], vis[MAXN], tot, mn[MAXN], num[MAXN], K;
void GetPhi(int N) {
    vis[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++tot] = i, mn[i] = tot;
        for(int j = 1; j <= tot && (i * prime[j] <= N); j++) {
            vis[i * prime[j]] = 1; mn[i * prime[j]] = j;
            if(!(i % prime[j])) break;
        }
    }
}
void insert(int x, int opt) {
    while(x != 1) num[mn[x]] += opt, x = x / prime[mn[x]];
}
int fastpow(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = (1ll * base * a) % mod;
        a = (1ll * a * a) % mod; p >>= 1;
    }
    return base;
}
int FindAns() {
    LL ans = 1;
    for(int i = 1; i <= tot; i++) 
        if(num[i]) 
            ans = (1ll * ans * fastpow(prime[i], num[i])) % mod;	
    return ans;
}
signed main() {
    N = read();  K = read(); mod = read();
    GetPhi(2 * N);
    for(int i = N + 1; i <= 2 * N; i++) insert(i, 1);
    for(int i = 1; i <= N; i++) insert(i, -1);
    LL ans1 = FindAns();
    memset(num, 0, sizeof(num));
    
    for(int i = N + K + 1; i <= 2 * N; i++) insert(i, 1);
    for(int i = 1; i <= N - K; i++) insert(i, -1);

    LL ans2 = FindAns();
    printf("%lld", (ans1 - ans2 + mod) % mod);

    return 0;
}