A.大吉大利

题意：

给定由个数组成的，求

题解：

按位考虑，那么每一位的贡献就是在二进制下这一位在个数中出现的次数的平方乘上二进制的系数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int cnt[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0, x; i < n; i++)
    {
        scanf("%d", &x);
        for (int j = 0; j < 30; j++)
            if (x & (1 << j))
                cnt[j]++;
    }
    ll res = 0;
    for (int i = 0; i < 30; i++)
        res += 1ll * cnt[i] * cnt[i] * (1 << i);
    printf("%lld\n", res);
    return 0;
}

B.三角形周长和

题意：

给定个点，保证不存在三点共线，求所有能组成的三角形的周长和

题解：

因为是，所以直接去枚举所有边，那么每一条边显然会在其他个三角形中出现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
pll p[1005];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &p[i].first, &p[i].second);
    ll res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            ll t = abs(p[i].first - p[j].first) + abs(p[i].second - p[j].second);
            res = (res + t * (n - 2)) % mod;
        }
    printf("%lld\n", res);
    return 0;
}

C.操作集锦

题意：

给定一个长度为的字母序列，求长度为的不同子序列个数

题解：

表示前个字符形成的长度为的不同子序列个数。
那么如果我们不考虑会重复的情况，转移方程是
那么显然是多算一部分重复的，我们记录表示这个字符之前出现的位置，那么多算的这部分很容易发现就是

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
char s[maxn];
map<char, int> mp;
ll dp[maxn][maxn];

int main()
{
   int n, k;
   scanf("%d%d", &n, &k);
   memset(dp, 0, sizeof(dp));
   mp.clear();
   scanf("%s", s + 1);
   dp[0][0] = 1;
   for (int i = 1; i <= n; i++)
   {
      dp[i][0] = 1;
      for (int j = 1; j <= i; j++)
      {
         dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
         if (mp[s[i]])
            dp[i][j] = (dp[i][j] - dp[mp[s[i]] - 1][j - 1] + mod) % mod;
      }
      mp[s[i]] = i;
   }
   printf("%lld\n", (dp[n][k] + mod) % mod);
   return 0;
}

D.斩杀线计算大师

题意：

给定和，求解中的，其中

题解：

对于方程我们可以选择一维来枚举，不妨选择是这一项，然后对于去解一次就能得到答案。因为保证了有解，因此在区间中必定存在一个解。
复杂度是

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 998244353;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - (a / b) * y;
    return r;
}
ll gcd(ll a, ll b)
{
    if (a % b == 0)
        return b;
    return gcd(b, a % b);
}

int main()
{
    ll t, i, j, n, k, m = 0, a, b, c;
    cin >> a >> b >> c >> k;
    ll g = gcd(b, c);
    for (i = 0; i < k / a; i++)
    {
        if ((k - a * i) % g != 0)
            continue;
        ll x, y;
        ll cc = exgcd(b, c, x, y);
        t = (k - a * i) / cc;
        ll x1 = x * t, y1 = y * t, c1 = c / g;
        x1 = (x1 % c1 + c1) % c1;
        y1 = (k - a * i - b * x1) / c;
        if (x1 < 0 || y1 < 0)
            continue;
        cout << i << " " << x1 << " " << y1;
        break;
    }
}

E.旗鼓相当的对手（dsu on tree）

题意：

见题面

题解：

因为是查询节点不同子树中距离为的点对，因此我们只需要用一个数组来记录某个点的深度值，那么每次询问相当于查询所有深度为的其他子树的节点产生的贡献。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, k, a[maxn];
struct E
{
   int to, next;
} Edge[maxn << 1];
int tot, head[maxn];
void init()
{
   memset(head, -1, sizeof(head));
   tot = 0;
}
void addedge(int u, int v)
{
   Edge[tot].to = v;
   Edge[tot].next = head[u];
   head[u] = tot++;
}
int siz[maxn], son[maxn], dep[maxn], fa[maxn];
void dfs(int u, int f)
{
   fa[u] = f;
   siz[u] = 1;
   dep[u] = dep[f] + 1;
   son[u] = 0;
   for (int i = head[u]; ~i; i = Edge[i].next)
   {
      int v = Edge[i].to;
      if (v == f)
         continue;
      dfs(v, u);
      siz[u] += siz[v];
      if (siz[v] > siz[son[u]])
         son[u] = v;
   }
}
ll ans[maxn], sum[maxn], num[maxn]; //ans是答案数组
int flag;                           //flag用于标记重儿子
void cal(int u, int val)
{
   num[dep[u]] += val;
   sum[dep[u]] += a[u] * val;
   for (int i = head[u]; ~i; i = Edge[i].next)
   {
      int v = Edge[i].to;
      if (v == fa[u] || v == flag)
         continue;
      cal(v, val);
   }
}
void query(int u, int lca)
{
   int d = k + dep[lca] * 2 - dep[u];
   if (d > 0)
   {
      ans[lca] += sum[d];
      ans[lca] += num[d] * a[u];
   }
   for (int i = head[u]; ~i; i = Edge[i].next)
   {
      int v = Edge[i].to;
      if (v == fa[u])
         continue;
      query(v, lca);
   }
}
//dsu on tree板子
void dfs(int u, int f, bool keep)
{
   //第一步，搞轻儿子及其子树算答案删贡献
   for (int i = head[u]; ~i; i = Edge[i].next)
   {
      int v = Edge[i].to;
      if (v == f || v == son[u])
         continue;
      dfs(v, u, false);
   }
   //第二步，搞重儿子及其子树算答案不删贡献
   if (son[u])
   {
      dfs(son[u], u, true);
      flag = son[u];
   }
   //第三步，暴力统计u及其所有轻儿子的贡献合并道刚算出的重儿子信息里
   for (int i = head[u]; ~i; i = Edge[i].next)
   {
      int v = Edge[i].to;
      if (v == f || v == flag)
         continue;
      query(v, u);
      cal(v, 1);
   }
   num[dep[u]] += 1;
   sum[dep[u]] += a[u];
   flag = 0;
   //把需要删除贡献的删一删
   if (!keep)
      cal(u, -1);
}
int main()
{
   init();
   scanf("%d%d", &n, &k);
   for (int i = 1; i <= n; i++)
      scanf("%d", &a[i]);
   for (int i = 1, u, v; i < n; i++)
   {
      scanf("%d%d", &u, &v);
      addedge(u, v);
      addedge(v, u);
   }
   dfs(1, 0);
   dfs(1, 0, 0);
   for (int i = 1; i <= n; i++)
      printf("%lld ", ans[i]);
   puts("");
   return 0;
}

F.几何带师（二维偏序+树状数组+几何）

题意：

给定线段和个点，求由个点两两组成的条直线中有多少条直线是和线段相交

题解：

我们已经两个定点，现在我们需要判断直线是否和线段相交。现在我们考虑一下在同侧的情况。那么必定存在在或者在中。
我们就假设在中好了，设和分别表示和的角度。设和分别表示和。那么在中当且仅当且。不难发现这是一个二维偏序，我们对其中一维排序然后用统计即可。
当满足异侧的时候，则是两个外角满足大小关系，画图可以很容易发现。
代码看懂了不想写了，就直接贴过来了

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<utility>
#define lowbit(x) ((x) & (-(x)))

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e5;
const double pi = acos(-1.0);
const double eps = 1e-9;

int read_int() {
    char c;
    int ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}

struct point {

    point() {}
    point(ll _x, ll _y) {
        x = _x, y = _y;
    }

    bool operator == (const point& rhs)const {
        return x == rhs.x && y == rhs.y;
    }

    bool operator < (const point& rhs)const {
        return x < rhs.x || x == rhs.x && y < rhs.y;
    }

    point operator + (const point& rhs)const {
        return point(x + rhs.x, y + rhs.y);
    }

    point operator - (const point& rhs)const {
        return point(x - rhs.x, y - rhs.y);
    }

    ll dot(const point& rhs)const {
        return 1ll * x * rhs.x + 1ll * y * rhs.y;
    }

    ll det(const point& rhs)const {
        return 1ll * x * rhs.y - 1ll * y * rhs.x;
    }

    int x, y;
};

struct node {
    node() {}
    node(int _x, int _y, int _add) {
        x = _x, y = _y, add = _add;
    }

    bool operator < (const node& rhs)const {
        return x == rhs.x ? y < rhs.y : x < rhs.x;
    }
    int x, y, add;
}E[maxn + 5];

double dist(const point& a, const point& b) {
    return sqrt((a - b).dot(a - b));
}

int c[2 * maxn + 5], n;
point arr[maxn + 5], A, B;
double angel[maxn + 5][2], pos[2 * maxn + 5];
pii id[maxn + 5];
ll res;

void add(int x, int val) {
    for (int i = x; i <= 2 * maxn; i += lowbit(i))c[i] += val;
}

int sum(int x) {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))ans += c[i];
    return ans;
}

double GetAngel(double a, double b, double c) {
    return acos((b * b + c * c - a * a) / (2 * b * c));
}

ll solve1(const point& A, const point& B) {
    memset(c, 0, sizeof(c));
    int m = 0, cnt = 0;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if ((B - A).det(arr[i] - A) > 0) {
            m += 1;
            point P = arr[i];
            double disPA = dist(P, A);
            double disPB = dist(P, B);
            double disAB = dist(A, B);
            angel[m][0] = GetAngel(disPB, disPA, disAB);
            angel[m][1] = pi - GetAngel(disPA, disPB, disAB);
            pos[++cnt] = angel[m][0], pos[++cnt] = angel[m][1];
        }
    }
    sort(pos + 1, pos + 1 + cnt);
    for (int i = 1; i <= m; ++i) {
        id[i].first = lower_bound(pos + 1, pos + 1 + cnt, angel[i][0]) - pos;
        id[i].second = lower_bound(pos + 1, pos + 1 + cnt, angel[i][1]) - pos;
    }
    sort(id + 1, id + 1 + m);
    for (int i = 1; i <= m; ++i) {
        ans += sum(2 * maxn) - sum(id[i].second);
        add(id[i].second, 1);
    }
    return ans;
}

ll solve2(const point& A, const point& B) {
    memset(c, 0, sizeof(c));
    int cnt = 0;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        point P = arr[i];
        double disPA = dist(P, A);
        double disPB = dist(P, B);
        double disAB = dist(A, B);
        angel[i][0] = GetAngel(disPB, disPA, disAB);
        angel[i][1] = GetAngel(disPA, disPB, disAB);
        if ((B - A).det(arr[i] - A) > 0) {
            angel[i][0] = pi - angel[i][0];
            angel[i][1] = pi - angel[i][1];
        }
        pos[++cnt] = angel[i][0], pos[++cnt] = angel[i][1];
    }
    sort(pos + 1, pos + 1 + cnt);
    for (int i = 1; i <= n; ++i) {
        E[i].x = lower_bound(pos + 1, pos + 1 + cnt, angel[i][0]) - pos;
        E[i].y = lower_bound(pos + 1, pos + 1 + cnt, angel[i][1]) - pos;
        if ((B - A).det(arr[i] - A) > 0)E[i].add = 0;
        else E[i].add = 1;
    }
    sort(E + 1, E + 1 + n);
    for (int i = 1; i <= n; ++i) {
        if (E[i].add == 0)ans += sum(E[i].y - 1);
        if (E[i].add == 1)add(E[i].y, 1);
    }
    return ans;
}

int main()
{
    n = read_int();
    A.x = read_int(), A.y = read_int(), B.x = read_int(), B.y = read_int();
    for (int i = 1; i <= n; ++i)arr[i].x = read_int(), arr[i].y = read_int();
    res = solve1(A, B) + solve1(B, A) + solve2(A, B);
    printf("%lld\n", res);
    return 0;
}

官方题解