[atcoder arc107]解题报告

A	Simple Math

这个式子其实很好算的嘛（
因为 $a,b,c$ 都是独立的，直接三个等差就完事了。
最后答案就是 $\frac{A(A+1)B(B+1)C(C+1)}{8}$.

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
ll mi(ll a, ll b)
{
    ll ret = 1;
    while (b)
    {
        if (b & 1)
            ret = ret * a
        a = a * a
        b >>= 1;
    }
    return ret;
}
ll A, B, C;
inline void solve()
{
    cin >> A >> B >> C;
    ll ans = A * (A + 1)
    cout << ans << endl;
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

B

Quadruple

将式子移项，变成 $a+b=K+c+d$，那么显然我们只需要看 $a+b$ 和 $c+d$ 分别有多少对就可以了。
设 $c(k)$ 表示 $i+j=k,1\le i,j \le n$ 的 $(i,j)$ 对数。不难得出 $c(k) = \min(k-1,2n-k+1)$（你要用生成函数去推导我也不拦你......）
那么答案就是 $\sum\limits_{i=\max(2,k+2)}^{\min(2n,2n+k)}c(i)\cdot c(i+k)$.

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
int n, k;
ll c[N];
void initc()
{
    for (int i = 1; i <= 2 * n; ++i)
    {
        c[i] = min(i - 1, 2 * n - i + 1);
    }
}
inline void solve()
{
    ll ans = 0;
    scanf(
    initc();
    for (int i = 2; i <= 2 * n; ++i)
        if (i > k + 1 && i - k <= 2 * n)
            ans += c[i] * c[i - k];
    cout << ans << endl;
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

C	Shuffle Permutation

首先来看一个结论：两个点之间可以交换的话，就给这两个点连一条边。$n$ 个点如果通过这些边连成一个连通块的话，那么他们可以构成任意排列，即排列数就是 $n!$。
那么这个题就很简单了：直接枚举每两行，看这两行是否可以交换，可以的话就将这两行的下标打进一个集合内，最后行的贡献就是每个集合的大小的阶乘之积。对于列也是相同的操作，最后答案就是行的贡献乘以列的贡献。
也就是说 $1\sim N^2$ 这个条件没有啥用其实（

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 55;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
int n, k;
int a[N][N];
int f[2][N];
ll vis[2][N];
int Find(int id, int x) { return f[id][x] == x ? x : f[id][x] = Find(id, f[id][x]); }
ll ans = 1, fac[N];
void Union(int id, int x, int y)
{
    int fx = Find(id, x), fy = Find(id, y);
    if (fx != fy)
        f[id][fy] = fx;
}
inline void solve()
{
    cin >> n >> k;
    fac[0] = 1;
    for (int i = 1; i <= 50; ++i)
        fac[i] = fac[i - 1] * i
    for (int i = 1; i <= n; ++i)
        f[0][i] = f[1][i] = i;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> a[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            bool flag = true;
            for (int p = 1; p <= n; ++p)
            {
                if (a[i][p] + a[j][p] > k)
                    flag = false;
            }
            if (flag)
                Union(0, i, j);
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            bool flag = true;
            for (int p = 1; p <= n; ++p)
            {
                if (a[p][i] + a[p][j] > k)
                    flag = false;
            }
            if (flag)
                Union(1, i, j);
        }
    for (int i = 1; i <= n; ++i)
    {
        vis[0][Find(0, i)]++;
        vis[1][Find(1, i)]++;
    }
    for (int i = 1; i <= n; ++i)
    {
        int f0 = Find(0, i), f1 = Find(1, i);
        if (vis[0][f0] != -1)
        {
            ans *= fac[vis[0][f0]];
            ans
            vis[0][f0] = -1;
        }
        if (vis[1][f1] != -1)
        {
            ans *= fac[vis[1][f1]];
            ans
            vis[1][f1] = -1;
        }
    }
    cout << ans << endl;
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

D	Number of Multisets

设 $dp(n,k)$ 表示要用 $n$ 个数去构成和为 $k$ 的集合个数。这里的转移其实脑洞很大......

1. 如果当前放一个 $1$ 的话，那么问题就变成了 $n-1$ 个数去构成和为 $k-1$ 的集合个数，那么 $dp(n,k)+=dp(n-1,k-1)$；
2. 如果当前不放 $1$ 的话，那么我们还是剩 $n$ 个数要去填，但是不准用 $1$。这个时候如果我们将后面的数乘以 $2$，那么问题就变成用 $n$ 个数组成和为 $2k$ 的集合个数。注意到这个时候又可以用 $1$ 了，因为这个 $1$ 是由 $\frac{1}{2}$ 来的，所以就有 $dp(n,k)+=dp(n,2k)$。

注意到第二个操作实际上不会很大（$\log n$ 的），所以总的时间复杂度不会很大。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 3050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
ll dp[N][N];
ll dfs(int n, int k)
{
    if (n <= k)
        return (n == k);
    if (n == 0 && k == 0)
        return 1;
    if (k == 0)
        return 0;
    if (~dp[n][k])
        return dp[n][k];
    ll &ret = dp[n][k];
    ret = 0;
    ret += dfs(n - 1, k - 1);
    ret += dfs(n, 2 * k);
    ret
    return ret;
}
inline void solve()
{
    memarray(dp, -1);
    int n, k;
    scanf(
    ll ans = dfs(n, k);
    cout << ans << '\n';
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

E

Mex Mat

通过打表可以发现，当 $n\ge 5$ 的时候，有一个绝妙的性质：$a(i,j)=a(i-1,j-1)$，然后直接根据这个东西来做就行......
怎么证明我还不太会（

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
int n;
inline int mex(int a, int b)
{
    int vis[3] = {0};
    vis[a] = vis[b] = 1;
    for (int i = 0; i < 3; ++i)
        if (!vis[i])
            return i;
    return -1;
}
vector<int> a[N];
ll ans[5];
void solve6()
{
    int a[10][10];
    memarray(a, 0);
    for (int i = 1; i <= n; ++i)
        scanf(
    for (int i = 2; i <= n; ++i)
        scanf(
    for (int i = 2; i <= n; ++i)
        for (int j = 2; j <= n; ++j)
            a[i][j] = mex(a[i - 1][j], a[i][j - 1]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            ans[a[i][j]]++;
    for (int i = 0; i < 3; ++i)
        printf(
}
inline void solve()
{
    scanf(
    if (n <= 6)
        return solve6(), void();
    for (int i = 1; i <= 5; ++i)
        a[i].resize(n + 5), a[i][0] = 0;
    for (int i = 1; i <= n; ++i)
        scanf(
    for (int i = 2; i <= n; ++i)
    {
        if (i > 5)
            a[i].resize(6);
        scanf(
        ans[a[i][1]]++;
        a[i][0] = 0;
    }
    for (int i = 2; i <= 5; ++i)
        for (int j = 2; j <= n; ++j)
            a[i][j] = mex(a[i - 1][j], a[i][j - 1]), ans[a[i][j]]++;
    for (int i = 6; i <= n; ++i)
        for (int j = 2; j <= 5; ++j)
            a[i][j] = mex(a[i - 1][j], a[i][j - 1]), ans[a[i][j]]++;
    for (int j = 5; j <= n; ++j)
    {
        int x = a[5][j];
        ans[x] += min(n - 5, n - j);
    }
    for (int i = 6; i <= n; ++i)
    {
        int x = a[i][5];
        ans[x] += min(n - i, n - 5);
    }
    for (int i = 0; i < 3; ++i)
        printf(
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

F	Sum of Abs

题解先留着，等脑子清醒了好好捋捋这个题，特别巧妙

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
const int MAXN = 1000, MAXM = N;
struct ISAP
{
    struct Edge
    {
        ll v, w, nxt;
    } edge[MAXM];
    ll tot, num, s, t, n;
    ll head[MAXN];
    void init()
    {
        memset(head, -1, sizeof(head));
        tot = 0;
    }
    void add_Edge(ll u, ll v, ll w)
    {
        edge[tot].v = v;
        edge[tot].w = w;
        edge[tot].nxt = head[u];
        head[u] = tot++;
        edge[tot].v = u;
        edge[tot].w = 0;
        edge[tot].nxt = head[v];
        head[v] = tot++;
    }
    ll d[MAXN], vis[MAXN], gap[MAXN];
    void bfs()
    {
        memset(d, 0, (n + 5) * sizeof(ll));
        memset(gap, 0, (n + 5) * sizeof(ll));
        memset(vis, 0, (n + 5) * sizeof(ll));
        queue<int> q;
        q.push(t);
        vis[t] = 1;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = edge[i].nxt)
            {
                int v = edge[i].v;
                if (!vis[v])
                {
                    d[v] = d[u] + 1;
                    gap[d[v]]++;
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    ll last[MAXN];
    ll dfs(int u, ll f)
    {
        if (u == t)
            return f;
        ll sap = 0;
        for (int i = last[u]; ~i; i = edge[i].nxt)
        {
            int v = edge[i].v;
            if (edge[i].w > 0 && d[u] == d[v] + 1)
            {
                last[u] = i;
                ll tmp = dfs(v, min(f - sap, edge[i].w));
                edge[i].w -= tmp;
                edge[i ^ 1].w += tmp;
                sap += tmp;
                if (sap == f)
                    return sap;
            }
        }
        if (d[s] >= num)
            return sap;
        if (!(--gap[d[u]]))
            d[s] = num;
        ++gap[++d[u]];
        last[u] = head[u];
        return sap;
    }
    ll solve(int st, int ed, int n)
    {
        ll flow = 0;
        num = n;
        s = st;
        t = ed;
        bfs();
        memcpy(last, head, sizeof(head));
        while (d[s] < num)
            flow += dfs(s, inf);
        return flow;
    }
} G;
int n, m, S, T;
int a[350], b[350];
void add_node(int u)
{
    if (b[u] <= 0)
    {
        G.add_Edge(S, u, 0);
        G.add_Edge(u + n, T, -2 * b[u]);
        G.add_Edge(u, u + n, a[u] - b[u]);
    }
    else
    {
        G.add_Edge(S, u, 2 * b[u]);
        G.add_Edge(u + n, T, 0);
        G.add_Edge(u, u + n, a[u] + b[u]);
    }
}
inline void solve()
{
    G.init();
    scanf(
    S = 2 * n + 3, T = 2 * n + 4;
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        scanf(
        G.add_Edge(v + n, u, inf);
        G.add_Edge(u + n, v, inf);
    }
    for (int i = 1; i <= n; ++i)
        add_node(i);
    ans -= G.solve(S, T, 2 * n + 5);
    printf(
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}