晚间测试4

字符串

• 显然啊，我的博客中卡特兰数的例题，太显然了，然后我在测数据的时候发现0 3还有1e6 1e6是负的，一看0 3显然情况为0，就直接输出的0，气死了。。。也不看看1e6 1e6怎么可能是0，傻了。。。
• 显然0 3数据不符合题目的(n <= m)，应该（ans + mod） % mod

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
    int k = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) k = k * 10 + ch - '0';
    return k * f;
}
const int maxn = 2e6 + 10;
const int mod = 20100403;
int jc[maxn], ny[maxn], jcny[maxn];
int C(int n, int m) { 
    return jc[n] * jcny[m] % mod * jcny[n - m] % mod; 
}
int qpow(int x, int y) {
    int ans = 1;
    for (; y; y >>= 1, x = x * x % mod) if (y & 1) ans = ans * x % mod;
    return ans;
}
signed main() {
#ifdef local
//  freopen("in", "r", stdin);
#else
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
#endif
    int n = read(), m = read();
    jc[0] = ny[0] = ny[1] = jcny[0] = jcny[1] = 1;
    for (int i = 1; i <= n + m + 1; i++) jc[i] = 1ll * jc[i - 1] * i % mod;
    for (int i = 2; i <= n + m + 1; i++) ny[i] = 1ll * (mod - mod / i) * ny[mod % i] % mod;
    for (int i = 2; i <= n + m + 1; i++) jcny[i] = 1ll * jcny[i - 1] * ny[i] % mod;
    int cur = C(n + m, m) - C(n + m, m - 1);
    printf("%lld
", (cur + mod) % mod) ;
//  printf("%lld
", cur);
    return 0;
}

哪一天她能重回我身边

不会。。。只会20分深搜

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int k = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) k = k * 10 + ch - '0';
    return k * f;
}
const int maxn = 2e5 + 10;
const int mod = 998244353;
struct node { int x, y; } a[maxn];
bool cmp(node A, node B) { return A.x < B.x; }
int vis[maxn];
int n = 0, ans = 0, minn = 0x3f3f3f3f;
void dfs(int cur, int cnt) {
    if (cur == n + 1) {
        if (cnt == minn) ans++;
        else if (cnt < minn) ans = 1, minn = cnt;
        return;
    }
    if (!vis[a[cur].x]) {
        vis[a[cur].x] = 1;
        dfs(cur + 1, cnt);
        vis[a[cur].x] = 0;
    }
    if (!vis[a[cur].y]) {
        vis[a[cur].y] = 1;
        dfs(cur + 1, cnt + 1);
        vis[a[cur].y] = 0;
    }
}
int main() {
#ifdef local
    freopen("in", "r", stdin);
#else
    freopen("back.in", "r", stdin);
    freopen("back.out", "w", stdout);
#endif
    int T = read();
    while (T--) {
        n = read();
        for (int i = 1; i <= n; i++) a[i].x = read(), a[i].y = read();
        sort(a + 1, a + n + 1, cmp);
        minn = 0x3f3f3f3f, ans = 0;
        dfs(1, 0);
        if (minn == 0x3f3f3f3f) printf("-1 -1
");
        else printf("%d %d
", minn, ans % mod);
    }
}