## 题目描述

Traveller Gregory is famous for his ability to always choose the shortest path for his journey. Ostap is a journalist who seeks for information about the recent Gregory’s trip. He managed to get the evidence that during this trip Gregory visited a number of cities. However, there is no information about the order in which they were visited, and no information about the starting city and the ending city of Gregory’s trip (the entire trip is (one of) the shortest path between these cities). Help Ostap to find any shortest path that contains all specified cities.
Country in which Gregory traveled consists of $n$ cities and $m$ undirected roads between them. For each road Ostap knows the time it takes to travel it, and the “shortest” word above is with respect to those times.
It is guaranteed that there exists some shortest path going through all specified cities.

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
int ne = 1, top, h[N], d[N], que[N], id[N], lst[N], pre[N], ans[N];
bool in[N], v[N];
struct Edge {
int u, v, w, nxt;
} e[N << 1];

void add_edge(int u, int v, int w) {
e[++ne] = (Edge){u, v, w, h[u]}, h[u] = ne;
e[++ne] = (Edge){v, u, w, h[v]}, h[v] = ne;
}

void spfa(int s) {
int qb = 0, qe = 1;
memset(d, 0x3f, sizeof d), d[s] = 0, que[0] = s, in[s] = 1;
for (; qb != qe;) {
int u = que[qb++];
in[u] = 0, qb == N && (qb = 0);
for (int i = h[u]; i; i = e[i].nxt)
if (d[e[i].v] > d[u] + e[i].w) {
d[e[i].v] = d[u] + e[i].w;
if (!in[e[i].v]) {
if (qb == qe || d[e[i].v] > d[que[qb]])
que[qe++] = e[i].v, in[e[i].v] = 1, qe == N && (qe = 0);
else
!~--qb && (qb = N - 1), que[qb] = e[i].v, in[e[i].v] = 1;
}
}
}
}

int main() {
int n, m, k, t;
scanf("%d%d", &n, &m);
for (int i = 1, u, v, w; i <= m; ++i)
scanf("%d%d%d", &u, &v, &w), add_edge(u, v, w);
scanf("%d%d", &k, &t), v[t] = 1, spfa(t);
int s = t;
for (int i = 2; i <= k; ++i)
scanf("%d", &t), v[t] = 1, d[s] < d[t] && (s = t);
spfa(s);
for (int i = 1; i <= n; ++i)
id[i] = i;
std::sort(id + 1, id + n + 1, [&](int const &i, int const &j) { return d[i] < d[j]; });
for (int i : id) {
lst[i] += v[i];
for (int j = h[i]; j; j = e[j].nxt)
if (d[e[j].v] == d[i] + e[j].w && lst[e[j].v] < lst[i])
lst[e[j].v] = lst[i], pre[e[j].v] = j;
}
for (int i = 1; i <= n; ++i)
if (lst[i] == k) {
for (int j = pre[i]; j; j = pre[e[j].u])
ans[top++] = j >> 1;
break;
}
printf("%d\n", top);
for (int i = 0; i < top; ++i)
printf("%d ", ans[i]);
puts("");
return 0;
}


## 题目描述

Chess Championship is set up in the New Basyuki City. Two national teams, of Berland and Byteland, are going to have a match there. Each team is represented by $n$ players. The championship consists of $n$ games – in each game a pair of players from different teams meets. A game victory brings $1$ point to the team and a game defeat doesn’t add or subtract points.
The championship starts with the sortition – the process that determines opponent pairs. Each player from the first team plays with exactly one player from the second team (and vice versa).
A recent research conducted by Berland scientists showed that every player of either team is characterized by a single number – the level of his chess mastership. No two people among the $2n$ players play at the same level. Funny as it is, the game winner always is the player with the higher level.
The contest organizers received information that a high-ranking Berland official Mr. B. bet $100500$ burles on the victory of his team with a $k$ points gap. Immediately an unofficial “recommendation” came from very important people to “organize” the sortition so that the Berland team gets exactly $k$ points more than the Byteland team.
Write a program that finds the number of distinct sortition results after which Berland gets exactly $k$ points more than Byteland. Two sortitions are considered distinct if there is such player, that gets different opponents by the sortitions’ results.

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 505;
static int const MOD = 1000000009;
int f[2][N][N];
std::pair<int, int> a[N << 1];

int main() {
int n, k;
scanf("%d%d", &n, &k);
if ((n & 1) != (k & 1))
return puts("0"), 0;
for (int i = 0; i < n; ++i)
scanf("%d", &a[i].first);
for (int i = n; i < n << 1; ++i)
scanf("%d", &a[i].first), a[i].second = 1;
std::sort(a, a + (n << 1));
int cur = 0, s[2] = {0, 0};
f[0][0][0] = 1;
for (int i = 0; i < n << 1; ++i, cur ^= 1) {
for (int j = 0; j <= n; ++j)
for (int k = 0; j + k <= n; ++k)
if (f[cur][j][k]) {
(f[!cur][j][k] += f[cur][j][k]) %= MOD;
int c[2] = {s[0] - j - k, s[1] - j - k};
(f[!cur][j + !a[i].second][k + a[i].second] += 1ll * f[cur][j][k] * c[!a[i].second] % MOD) %= MOD;
f[cur][j][k] = 0;
}
++s[a[i].second];
}
printf("%d\n", f[cur][n + k >> 1][n - k >> 1]);
return 0;
}


## 题目描述

Gena and Petya love playing the following game with each other. There are $n$ piles of stones, the $i$-th pile contains $a_i$ stones. The players move in turns, Gena moves first. A player moves by choosing any non-empty pile and taking an arbitrary positive number of stones from it. If the move is impossible (that is, all piles are empty), then the game finishes and the current player is considered a loser.
Gena and Petya are the world famous experts in unusual games. We will assume that they play optimally.
Recently Petya started to notice that Gena wins too often. Petya decided that the problem is the unjust rules as Gena always gets to move first! To even their chances, Petya decided to cheat and take and hide some stones before the game begins. Since Petya does not want Gena to suspect anything, he will take the same number of stones $x$ from each pile. This number $x$ can be an arbitrary non-negative integer, strictly less that the minimum of $a_i$ values.
Your task is to find the number of distinct numbers $x$ such that Petya will win the game.

## 算法分析

Nim游戏后手胜利的条件是所有数的异或和为$0$。

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 200005;
static int const M = 65;
int a[N], cnt[M], f[M][N], s[2][N];

signed main() {
int n;
scanf("%lld", &n);
for (int i = 0; i < n; ++i) {
scanf("%lld", a + i);
for (int j = 0; j < M; ++j)
cnt[j] += a[i] >> j & 1;
}
f[0][0] = 1;
for (int i = 0; i < M - 1; ++i) {
int c0 = n - cnt[i], c1 = cnt[i], c = 0;
for (int j = 0; j <= n; ++j) {
if (j)
if (a[j - 1] >> i & 1)
++c0, --c1;
else
--c0, ++c1, ++c;
if (!(c0 & 1))
f[i + 1][c + c0] += f[i][j];
if (!(c1 & 1))
f[i + 1][c] += f[i][j];
}
*s[0] = *s[1] = 0;
for (int j = 0; j < n; ++j)
s[a[j] >> i & 1][++*s[a[j] >> i & 1]] = a[j];
for (int j = 1; j <= *s[0]; ++j)
a[j - 1] = s[0][j];
for (int j = 1; j <= *s[1]; ++j)
a[*s[0] + j - 1] = s[1][j];
}
int sum = 0;
for (int i = 1; i < n; ++i)
sum ^= a[i] - a[0];
printf("%lld\n", f[M - 1][0] - (sum == 0));
return 0;
}


## 题目描述

Kyoya Ootori wants to take the train to get to school. There are $n$ train stations and $m$ one-way train lines going between various stations. Kyoya is currently at train station $1$, and the school is at station $n$. To take a train, he must pay for a ticket, and the train also takes a certain amount of time. However, the trains are not perfect and take random amounts of time to arrive at their destination. If Kyoya arrives at school strictly after $t$ time units, he will have to pay a fine of $x$.
Each train line is described by a ticket price, and a probability distribution on the time the train takes. More formally, train line $i$ has ticket cost $c_i$, and a probability distribution $p_{i, k}$ which denotes the probability that this train will take $k$ time units for all $1 \le k \le t$. Amounts of time that each of the trains used by Kyouya takes are mutually independent random values (moreover, if Kyoya travels along the same train more than once, it is possible for the train to take different amounts of time and those amounts are also independent one from another).
Kyoya wants to get to school by spending the least amount of money in expectation (for the ticket price plus possible fine for being late). Of course, Kyoya has an optimal plan for how to get to school, and every time he arrives at a train station, he may recalculate his plan based on how much time he has remaining. What is the expected cost that Kyoya will pay to get to school if he moves optimally?

## 算法分析

$$f_{i, j}= \begin{cases} \min(c_e+\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k} \mid e \in [1, m] \land a_e=i), & i \lt n \land j \le t \\ d_{i, n}+x , & i \lt n \land j \gt t \\ 0, & i=n \land j \le t \\ x, & i=n \land j \gt t \end{cases}$$

$$S_{e, j}=\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k}$$

$$f_{i, j}=\min(c_e+S_{e, j} \mid e \in [1, m] \land a_e=i)$$

## 代码

/*
*/

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 55;
static int const M = 105;
static int const T = 100000;
static double const PI = acos(-1);
int rev[T];

class Point {
public:
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
std::pair<double, double> pair() {
return std::make_pair(x, y);
}
friend Point operator+(Point const &a, Point const &b) {
return Point(a.x + b.x, a.y + b.y);
}
friend Point operator-(Point const &a, Point const &b) {
return Point(a.x - b.x, a.y - b.y);
}
friend Point operator*(Point const &a, Point const &b) {
return Point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
Point operator/(double const &n) {
return Point(x / n, y / n);
}
} wn[T], A[T], B[T];

int init(int n) {
int m = n, l = 0;
for (n = 1; n <= m; n <<= 1, ++l)
;
for (int i = 1; i < n; ++i)
rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
for (int i = 0; i < n >> 1; ++i)
wn[i] = Point(cos(2 * PI / n * i), sin(2 * PI / n * i));
return n;
}

void fft(Point *a, int n, int inv = 0) {
for (int i = 0; i < n; ++i)
if (i < rev[i])
std::swap(a[i], a[rev[i]]);
for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < n; j += i << 1)
for (int k = 0; k < i; ++k) {
Point x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
a[j + k] = x + y, a[j + k + i] = x - y;
}
if (inv) {
std::reverse(a + 1, a + n);
for (int i = 0; i < n; ++i)
a[i] = a[i] / n;
}
}

int n, m, t, x, mp[N][N];
double p[M][T], s[M][T], f[N][T];
struct Line {
int a, b, c;
} li[M];

void update(int l, int r) {
int mid = l + r >> 1, len = init(r - l + r - mid - 2);
for (int i = 1; i <= m; ++i) {
for (int j = 0; j < len; ++j)
A[j] = B[j] = 0;
for (int j = mid + 1; j <= r; ++j)
A[j - mid - 1] = f[li[i].b][r - j + mid + 1];
for (int j = 1; j <= r - l; ++j)
B[j - 1] = p[i][j];
fft(A, len), fft(B, len);
for (int j = 0; j < len; ++j)
A[j] = A[j] * B[j];
fft(A, len, 1);
for (int j = l; j <= mid; ++j)
s[i][j] += A[r - j - 1].x;
}
}

void solve(int l, int r) {
if (l == r) {
for (int i = 1; i <= m; ++i)
f[li[i].a][l] = std::min(f[li[i].a][l], s[i][l] + li[i].c);
return;
}
int mid = l + r >> 1;
solve(mid + 1, r), update(l, r), solve(l, mid);
}

int main() {
scanf("%d%d%d%d", &n, &m, &t, &x);
memset(mp, 0x3f, sizeof mp);
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &li[i].a, &li[i].b, &li[i].c);
mp[li[i].a][li[i].b] = std::min(mp[li[i].a][li[i].b], li[i].c);
for (int j = 1; j <= t; ++j)
scanf("%lf", &p[i][j]), p[i][j] /= 100000;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
mp[j][k] = std::min(mp[j][k], mp[j][i] + mp[i][k]);
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= t << 1; ++j)
if (i == n)
if (j <= t)
f[i][j] = 0;
else
f[i][j] = x;
else
if (j <= t)
f[i][j] = 1e9;
else
f[i][j] = x + mp[i][n];
update(0, t << 1), solve(0, t), printf("%.8lf\n", f[1][0]);
return 0;
}


## 题目描述

It’s summer vocation now. After tedious milking, cows are tired and wish to take a holiday. So Farmer Carolina considers having a picnic beside the river. But there is a problem, not all the cows consider it’s a good idea! Some cows like to swim in West Lake, some prefer to have a dinner in Shangri-la, and others want to do something different. But in order to manage expediently, Carolina coerces all cows to have a picnic!
Farmer Carolina takes her $N$ cows to the destination, but she finds every cow’s degree of interest in this activity is so different that they all loss their interests. So she has to group them to different teams to make sure that every cow can go to a satisfied team. Considering about the security, she demands that there must be no less than $T$ cows in every team. As every cow has its own interest degree of this picnic, we measure this interest degree’s unit as “Moo~“. Cows in the same team should reduce their Moo~ to the one who has the lowest Moo~ in this team – It’s not a democratical action! So Carolina wishes to minimize the TOTAL reduced Moo~s and groups $N$ cows into several teams.
For example, Carolina has $7$ cows to picnic and their Moo~ are ‘$8 \; 5 \; 6 \; 2 \; 1 \; 7 \; 6$’ and at least $3$ cows in every team. So the best solution is that cow No. $2, 4, 5$ in a team (reduce $((2-1)+(5-1))$ Moo~) and cow No. $1, 3, 6, 7$ in a team (reduce $((7-6)+(8-6))$ Moo~), the answer is $8$.

## 算法分析

$$f_i=\min(f_j+(s_i-s_j)-(i-j)b_j \mid i-j \ge T)$$

\begin{align} f_j+(s_i-s_j)-(i-j)b_j &\le f_k+(s_i-s_k)-(i-k)b_k \\ (f_j-s_j+j \cdot b_j)-(f_k-s_k+k \cdot b_k) &\le i(b_j-b_k) \end{align}
$i$单调递增，因此可以斜率优化。但要注意两点：当$i-j \lt T$时$f_j$不能转移到$f_i$；当$i \lt T$时$f_i$没有意义。

## 代码

/*
* You attempt things that you do not even plan because of your extreme
* stupidity.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 400005;
int a[N], f[N], s[N], b[N], que[N];

int dety(int i, int j) {
return f[j] - s[j] + b[j] * j - (f[i] - s[i] + b[i] * i);
}

int detx(int i, int j) { return b[j] - b[i]; }

signed main() {
for (int n, k; ~scanf("%lld%lld", &n, &k);) {
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + a[i], b[i - 1] = a[i];
int qb = 0, qe = 1;
que[0] = 0;
for (int i = 1; i <= n; ++i) {
for (; qb + 1 < qe &&
dety(que[qb], que[qb + 1]) <= i * detx(que[qb], que[qb + 1]);
++qb)
;
f[i] = f[que[qb]] + s[i] - s[que[qb]] - b[que[qb]] * (i - que[qb]);
if (i - k + 1 >= k) {
for (;
qb + 1 < qe &&
dety(que[qe - 2], que[qe - 1]) * detx(que[qe - 1], i - k + 1) >=
dety(que[qe - 1], i - k + 1) * detx(que[qe - 2], que[qe - 1]);
--qe)
;
que[qe++] = i - k + 1;
}
}
printf("%lld\n", f[n]);
}
return 0;
}


## 题目描述

Zero has an old printer that doesn’t work well sometimes. As it is antique, he still like to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero use a cost to evaluate this degree.
One day Zero want to print an article which has $N$ words, and each word $i$ has a cost $C_i$ to be printed. Also, Zero know that print $k$ words in one line will cost
$$\left(\sum_{i=1}^k C_i\right)^2+M$$
$M$ is a const number.
Now Zero want to know the minimum cost in order to arrange the article perfectly.

## 算法分析

$$f_i=\min(f_j+(s_i-s_j)^2+M)$$

$$f_j+(s_i-s_j)^2+M \le f_k+(s_i-s_k)^2+M$$

\begin{align} f_j-2s_is_j+s_j^2 &\le f_k-2s_is_k+s_k^2 \\ f_j+s_j^2-(f_k+s_k^2) &\le 2s_i(s_j-s_k) \\ {f_j+s_j^2-(f_k+s_k^2) \over 2s_j-2s_k} &\le s_i \end{align}

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 500005;
int a[N], s[N], f[N], que[N];

int detx(int i, int j) { return s[j] - s[i] << 1; }

int dety(int i, int j) { return f[j] + s[j] * s[j] - f[i] - s[i] * s[i]; }

int main() {
for (int n, m; ~scanf("%d%d", &n, &m);) {
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + a[i];
int qb = 0, qe = 1;
for (int i = 1; i <= n; ++i) {
for (; qb + 1 < qe &&
dety(que[qb], que[qb + 1]) <= s[i] * detx(que[qb], que[qb + 1]);
++qb)
;
f[i] = f[que[qb]] + (s[i] - s[que[qb]]) * (s[i] - s[que[qb]]) + m;
for (; qb + 1 < qe &&
dety(que[qe - 2], que[qe - 1]) * detx(que[qe - 1], i) >=
dety(que[qe - 1], i) * detx(que[qe - 2], que[qe - 1]);
--qe)
;
que[qe++] = i;
}
printf("%d\n", f[n]);
}
return 0;
}


## 题目描述

Our child likes computer science very much, especially he likes binary trees.
Consider the sequence of $n$ distinct positive integers: $c_1, c_2, \ldots, c_n$. The child calls a vertex-weighted rooted binary tree good if and only if for every vertex $v$, the weight of $v$ is in the set ${c_1, c_2, \ldots, c_n}$. Also our child thinks that the weight of a vertex-weighted tree is the sum of all vertices’ weights.
Given an integer $m$, can you for all $s \; (1 \le s \le m)$ calculate the number of good vertex-weighted rooted binary trees with weight $s$? Please, check the samples for better understanding what trees are considered different.
We only want to know the answer modulo $998244353$ ($7 \times 17 \times 2^{23}+1$, a prime number).

## 算法分析

$$f(x)=\sum_{w \in {c_1, c_2, \ldots, c_n}} \sum_{i=0}^{x-w} f(i)f(x-w-i)$$

$$F(x)=C(x)F(x)^2+1$$

$$F(x)={1 \pm \sqrt{1-4C(x)} \over 2C(x)}={2 \over 1 \pm \sqrt{1-4C(x)}}$$

• 多项式求逆：
求$GF \equiv 1 \pmod {x^n}$。

假设已知$G_0F \equiv 1 \pmod {x^{\lceil n/2 \rceil}}$
$G-G_0 \equiv 0 \pmod {x^{\lceil n/2 \rceil}}$
$G^2-2GG_0+G_0^2 \equiv 0 \pmod {x^n}$
$G-2G_0+G_0^2F \equiv 0 \pmod {x^n}$
$G \equiv 2G_0-G_0^2F \pmod {x^n}$

• 多项式开根：
求$G^2 \equiv F \pmod {x^n}$。

假设已知$G_0^2 \equiv F \pmod {x^{\lceil n/2 \rceil}}$
$(G_0^2-F)^2 \equiv 0 \pmod {x^n}$
$(G_0^2+F)^2 \equiv 4G_0^2F \pmod {x^n}$
$\left({G_0^2+F \over 2G_0}\right)^2 \equiv F \pmod {x^n}$
$G \equiv {G_0+G_0^{-1}F \over 2} \pmod {x^n}$

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static const int N = 500000;
static const int MOD = 998244353;
static const int G = 3;
static const int INV2 = 499122177;
int n, m, c[N], C[N], rev[N], wn[N], tmp[N], tmp2[N], tmp3[N];

int power(int a, int b) {
int ret = 1;
for (a %= MOD, b %= MOD - 1; b; b >>= 1)
b & 1 && (ret = 1ll * ret * a % MOD), a = 1ll * a * a % MOD;
return ret;
}

void init(int &n) {
int m = n << 1, l = 0;
for (n = 1; n < m; n <<= 1, ++l)
;
for (int i = 1; i < n; ++i)
rev[i] = rev[i >> 1] >> 1 | (i & 1) << (l - 1);
}

void ntt(int *a, int n, bool inv) {
for (int i = 0; i < n; ++i)
if (i < rev[i])
std::swap(a[i], a[rev[i]]);
wn[0] = 1, wn[1] = power(G, (MOD - 1) / n);
for (int i = 2; i < n >> 1; ++i)
wn[i] = 1ll * wn[i - 1] * wn[1] % MOD;
for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < n; j += i << 1)
for (int k = 0; k < i; ++k) {
int x = a[j + k], y = 1ll * wn[n / (i << 1) * k] * a[j + k + i] % MOD;
a[j + k] = (x + y) % MOD, a[j + k + i] = (MOD + x - y) % MOD;
}
if (inv) {
for (int i = 1; i < n >> 1; ++i)
std::swap(a[i], a[n - i]);
int rec = power(n, MOD - 2);
for (int i = 0; i < n; ++i)
a[i] = 1ll * a[i] * rec % MOD;
}
}

void get_inv(int *f, int *g, int n) {
if (n == 1)
return void(g[0] = power(f[0], MOD - 2));
int rec = n;
get_inv(f, g, (n + 1) >> 1), init(n);
for (int i = (rec + 1) >> 1; i < n; ++i)
g[i] = 0;
for (int i = 0; i < rec; ++i)
tmp[i] = f[i];
for (int i = rec; i < n; ++i)
tmp[i] = 0;
ntt(g, n, 0), ntt(tmp, n, 0);
for (int i = 0; i < n; ++i)
g[i] = 1ll * g[i] * (MOD + 2 - 1ll * g[i] * tmp[i] % MOD) % MOD;
ntt(g, n, 1);
for (int i = rec; i < n; ++i)
g[i] = 0;
}

void get_sqrt(int *f, int *g, int n) {
if (n == 1)
return void(g[0] = 1);
int rec = n;
get_sqrt(f, g, (n + 1) >> 1);
for (int i = 0; i<(n + 1)>> 1; ++i)
tmp2[i] = g[i];
for (int i = (n + 1) >> 1; i < n; ++i)
tmp2[i] = 0;
get_inv(tmp2, tmp3, n), init(n);
for (int i = (rec + 1) >> 1; i < n; ++i)
g[i] = 0;
for (int i = 0; i < rec; ++i)
tmp2[i] = f[i];
for (int i = rec; i < n; ++i)
tmp2[i] = 0;
ntt(tmp2, n, 0), ntt(tmp3, n, 0);
for (int i = 0; i < n; ++i)
tmp3[i] = 1ll * tmp3[i] * tmp2[i] % MOD;
ntt(tmp3, n, 1);
for (int i = 0; i < rec; ++i)
g[i] = 1ll * (g[i] + tmp3[i]) * INV2 % MOD;
for (int i = rec; i < n; ++i)
g[i] = 0;
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
scanf("%d", &c[i]);
for (int i = 0; i < n; ++i)
if (c[i] <= m)
++C[c[i]];
for (int i = 1; i <= m; ++i)
C[i] = (MOD - (C[i] << 2)) % MOD;
C[0] = 1;
get_sqrt(C, c, m + 1), ++c[0], get_inv(c, C, m + 1);
for (int i = 1; i <= m; ++i)
printf("%d\n", (C[i] << 1) % MOD);
return 0;
}


## 题意概述

$$\sum_{i=1}^N M_iT_i=0 \; (L_i \le T_i \le R_i)$$

## 代码

#include <cstdio>
#include <cstring>

int min(int a, int b) {
return a < b ? a : b;
}

static const int N = 205;
int p[N], m[N], u[N], l[N];
int f[N << 10], q1[N << 10], q2[N << 10];

int main() {
int n;
while (~ scanf("%d", &n)) {
int v = 0, w = 0;
for (int i = 0; i < n; ++ i) {
scanf("%d%d%d%d", &p[i], &m[i], &l[i], &u[i]);
if (l[i]) u[i] -= l[i], v -= l[i] * m[i], w -= l[i] * p[i];
}
memset(f, -0x3f, sizeof f), f[0] = 0;
for (int i = 0; i < n; ++ i) {
u[i] = min(u[i], v / m[i]);
for (int d = 0; d < m[i]; ++ d) {
int l = 1, r = 0;
for (int j = 0; j <= (v - d) / m[i]; ++ j) {
int val = f[j * m[i] + d] - j * p[i];
while (l <= r && q1[r] < val) -- r;
q2[++ r] = j, q1[r] = val;
if (j - q2[l] > u[i]) ++ l;
f[j * m[i] + d] = q1[l] + j * p[i];
}
}
}
printf("%d\n", f[v] - w);
}
return 0;
}


## 题目描述

There is a rectangular area containing $n \times m$ cells. Two cells are marked with “2”, and another two with “3”. Some cells are occupied by obstacles. You should connect the two “2”s and also the two “3”s with non-intersecting lines. Lines can run only vertically or horizontally connecting centers of cells without obstacles.
Lines cannot run on a cell with an obstacle. Only one line can run on a cell at most once. Hence, a line cannot intersect with the other line, nor with itself. Under these constraints, the total length of the two lines should be minimized. The length of a line is defined as the number of cell borders it passes. In particular, a line connecting cells sharing their border has length $1$.
Fig. 1(a) shows an example setting. Fig. 1(b) shows two lines satisfying the constraints above with minimum total length $18$.

## 代码

#include <cstdio>
#include <cstring>

void minify(short &a, short b) {
a > b && (a = b);
}

static const int N = 11;
int rec[1 << 20];
short mp[N][N], f[2][N][1 << 20]; // 0 for no wire, 2 for wire 2, 3 for wire 3

int modify(int s, int p, int v) {
return (s & ((1 << (p << 1)) - 1)) | (((s >> ((p + 1) << 1) << 2) + v) << (p << 1));
}

int query(int s, int p) {
return s >> (p << 1) & 3;
}

int main() {
int n, m, top = 0;
for (int i = 0; i < 1 << 20; ++ i) {
for (int j = 0; j < N; ++ j) if (query(i, j) == 1) goto illegal;
rec[top ++] = i; illegal: ;
}
while (scanf("%d%d", &n, &m), n) {
for (int i = 0; i < n; ++ i)
for (int j = 0; j < m; ++ j) scanf("%hd", &mp[i][j]);
int cur = 0; memset(f, 0x3f, sizeof f), f[cur][0][0] = 0;
for (int i = 0; i < n; ++ i, cur ^= 1) {
for (int j = 0; j < m; ++ j)
for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _])
if (f[cur][j][k] < 10000) {
int p = query(k, j), q = query(k, j + 1);
if (mp[i][j] == 0) {
if (! p && ! q)
minify(f[cur][j + 1][k], f[cur][j][k]),
minify(f[cur][j + 1][modify(modify(k, j, 2), j + 1, 2)], f[cur][j][k] + 1),
minify(f[cur][j + 1][modify(modify(k, j, 3), j + 1, 3)], f[cur][j][k] + 1);
else if (! p ^ ! q)
minify(f[cur][j + 1][modify(modify(k, j, p + q), j + 1, 0)], f[cur][j][k] + 1),
minify(f[cur][j + 1][modify(modify(k, j, 0), j + 1, p + q)], f[cur][j][k] + 1);
else if (p && p == q)
minify(f[cur][j + 1][modify(modify(k, j, 0), j + 1, 0)], f[cur][j][k] + 1);
} else if (mp[i][j] == 1) {
if (! p && ! q) minify(f[cur][j + 1][k], f[cur][j][k]);
} else {
if (! p && ! q)
minify(f[cur][j + 1][modify(k, j, mp[i][j])], f[cur][j][k] + 1),
minify(f[cur][j + 1][modify(k, j + 1, mp[i][j])], f[cur][j][k] + 1);
else if (p == mp[i][j] && ! q)
minify(f[cur][j + 1][modify(k, j, 0)], f[cur][j][k] + 1);
else if (! p && q == mp[i][j])
minify(f[cur][j + 1][modify(k, j + 1, 0)], f[cur][j][k] + 1);
}
}
for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _])
if (! query(k, m)) minify(f[cur ^ 1][0][k << 2 & (1 << ((m + 1) << 1)) - 1], f[cur][m][k]);
for (int j = 0; j <= m; ++ j)
for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _]) f[cur][j][k] = 16000;
}
printf("%d\n", f[cur][0][0] < 10000 ? f[cur][0][0] - 2 : 0);
}
return 0;
}


## 题目描述

The Queen of Byteland is very loved by her people. In order to show her their love, the Bytelanders have decided to conquer a new country which will be named according to the queen’s name. This new country contains $N$ towns. The towns are connected by bidirectional roads and there is exactly ONE path between any two towns, walking on the country’s roads. For each town, the profit it brings to the owner is known. Although the Bytelanders love their queen very much, they don’t want to conquer all the $N$ towns for her. They will be satisfied with a non-empty subset of these towns, with the following $2$ properties: there exists a path from every town in the subset to every other town in the subset walking only through towns in the subset and the profit of the subset is maximum. The profit of a subset of the $N$ towns is equal to the sum of the profits of the towns which belong to the subset. Your task is to find the maximum profit the Bytelanders may get.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

namespace std {
template <typename T> void maxify(T &a, T b) { b > a && (a = b); }
template <typename T> void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 16010;
int n, nume, h[N], w[N], f[2][N];
struct Edge {
int v, nxt;
} e[N << 1];
void add_edge(int u, int v) {
e[++ nume] = (Edge) { v, h[u] }, h[u] = nume;
e[++ nume] = (Edge) { u, h[v] }, h[v] = nume;
}
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > w[i];
for (int i = 1; i < n; ++ i) {
int u, v; io > u > v, add_edge(u, v);
}
}
void init() { memset(f, -0x3f, sizeof f); }
void dfs(int t, int fa) {
f[0][t] = w[t];
for (int i = h[t]; i; i = e[i].nxt)
if (e[i].v != fa) {
dfs(e[i].v, t);
maxify(f[1][t], max(f[0][e[i].v], f[1][e[i].v]));
f[0][t] += max(f[0][e[i].v], 0);
}
}
void process() { dfs(1, 0), io < max(f[0][1], f[1][1]) < '\n'; }

public:
void solve() { input(), init(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}