国庆集训 1109-1110（未完成）

取模模板

inline ll M(ll a){
    return a%mod;}
inline ll mul(ll a, ll b){
    return M(a*b);}
inline ll add(ll a, ll b){
    return M(a+b);}
inline ll sub(ll a, ll b){
    return M(a-b+mod);}
inline ll P(ll x, ll y) {
    ll c=1;while(y){
    if(y&1) c=mul(c,x);y>>=1;x=mul(x,x);}return c;} 

自定义函数（要比min、max来得快一些）

inline ll Min(int a, int b){
    return a<b ? a : b;}
inline ll Max(ll a, ll b){
    return a<b ? b : a;}

快读略

组合数

inline ll C(int x, int y){
    return mul(mul(fac[x],inv[y]),inv[x - y]);}
inline void prep() {
    fac[0] = 1;for (int i = 1; i <= N-1; i++)fac[i] = mul(fac[i-1],i);inv[N-1] = P(fac[N-1], mod-2);for (int i = N - 2; i >= 0; i--)inv[i] = mul(inv[i+1],(i + 1));
}

排名rank

#include<bits/stdc++.h>
using namespace std;int n, m, minn, ans;
int main() {
    n = dread(); m = dread();for(int i = 1, p; i <= n; i++) {
    p = dread();ans  = Min(ans+p-1,  m-1);minn = Min(minn+m-p, m-1);}printf("%d\n%d\n", m-minn, ans+1);return 0;
}

交换swap

#include <bits/stdc++.h>
#define ll long longusing namespace std;
const int N = 300010;
int n, a[N], b[N], flag;inline bool check(int l, int r) {
    int lx = 0, rx = 0;for (int i = l; i <= r; i++) {
    if (a[i]<l || a[i]>r) return 1;if (a[i] < i) if(a[i] < lx) return 1;else lx = a[i];if (a[i] > i) if(a[i] < rx) return 1;else rx = a[i];}return 0;
}
int main() {
    while (scanf("%d", &n) != EOF) {
    for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]); b[i] = a[i]==i ? 0 : 1;} flag = 0;for(int i = 3; i <= n; i++)if(b[i-2] && b[i-1] && b[i]) {
     puts("No"); flag = 1; break; }if(flag) continue;for(int i = 1; i <= n; i++) {
    if(!b[i]) continue;int j = i;while(b[j] != b[j+1] && j < n) j++;if(check(i, j))  {
     puts("No"); flag = 1; break; }i = j;}if (!flag) puts("Yes");}return 0;
}

祖先color

这里

骰子dice

出题人题解

机房大佬版（容斥+隔板）（代码是按这个思路写的）

网上找的纯隔板法

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4010;
const int mod = 998244353;
ll n, k, cnt, fac[N], inv[N], ans;
取模模板+组合数处理
int main() {
    prep();//处理阶乘及其逆元scanf("%lld%lld", &k, &n);for (int i = 2; i <= k<<1; i++) {
    ans = 0; cnt = i;if (i > k+1) cnt = (k<<1)+2-i;//有多少对可以组成ifor (int j = 0; j <= min(cnt>>1, n>>1); j++)if (j&1) ans = sub(ans,mul(C(cnt>>1, j), C(n-(j<<1)+k-1, k-1)));else     ans = add(ans,mul(C(cnt>>1, j), C(n-(j<<1)+k-1, k-1)));//分类讨论是容斥printf("%d\n", ans);}return 0;
}

序列seq

#include<bits/stdc++.h>
#define ll long long
using namespace std;ll mod, n, k, m;
ll C[305][305], f[305][305], fac[305], inv[305], sum[305][305];
取模模板inline void init() {
     n = dread(); k = dread(); m = dread(); mod = m; 
}void prep() {
     C[0][0] = 1;for (int i = 1; i <= n + 1; ++i) {
    C[i][0] = 1;for (int j = 1; j <= i; ++j)C[i][j] = add(C[i-1][j], C[i-1][j-1]);}
}//如果通过逆元处理组合数，取模情况下会为0， 且逆元无法判断inline void work() {
    for(int i = 0; i <= k; i++) f[1][i] = 1;for(int i = k; i; i--) sum[1][i] = add(sum[1][i+1],f[1][i]);for(int i = 2; i <= n+1; i++) {
    for(int j = 0; j <= k; j++) for(int s = 1; s < i; s++)f[i][j] = add(f[i][j], mul(f[i-s][j], mul(sum[s][j+1], C[i-2][s-1])));for(int j = k; j; j--)sum[i][j] = add(sum[i][j+1], f[i][j]);}
}inline void outo() {
    printf("%lld\n", f[n+1][0]);
}
int main() {
    init();prep();work();outo();return 0;
}

商店定价price

45分超时DP版

#include<bits/stdc++.h>
using namespace std;inline int dread() {
    int 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<<1)+(x<<3)+(ch^48); ch=getchar();}return x*f;
}const int N = 3e5+10;
int n, L[N], R[N], a[N];inline int Min(int a, int b){
    return a<b ? a : b;}
inline int Max(int a, int b){
    return a<b ? b : a;}inline void init() {
    n = dread();for(int i = 1; i <= n; i++)L[i] = dread(), R[i] = dread();
}inline void work() {
    for(int i = 1; i <= n; i++) a[i] = 2e9+10;a[0] = 0; a[1] = L[1];for(int i = 2; i <= n; i++) for(int j = i; j >= 1; j--) if(R[i] > a[j-1]) a[j] = Min(a[j], Max(a[j-1]+1, L[i]));
}inline void outo() {
    for(int i = n; i >= 1; i--)if(a[i] != 2e9+10) {
    printf("%d\n", i);return;}
}
int main() {
    init();work();outo();return 0;
}