Hi, dear contestants!↵
↵
With the end of Codeforces Round #431 ([Div. 1](http://codeforces.me/contest/848) and [Div. 2](http://codeforces.me/contest/849)), some might be complaining behind the screen that problems are too tricky or hard, or have been struggling with some supposedly solvable problem... Yes, this time problems seem hard, but anyways, I hope they provided you with something, say rating, fun, ideas, or experience. I don't want to see anyone losing confidence because of failure (bad luck) in a single contest — please, don't do so.↵
↵
Here are the hints, tutorials and codes for the problems. Feel free to discuss about problems in the comments, and point out if something is incorrect or unclear. Thank you!↵
↵
### [problem:849A]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
What will the whole array satisfy? Is that a sufficient condition?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:849A]↵
</spoiler>↵
↵
<spoiler summary="Model solution">↵
~~~↵
#include <cstdio>↵
static const int MAXN = 102;↵
↵
int n;↵
int a[MAXN];↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);↵
↵
puts((n % 2 == 1) && (a[0] % 2 == 1) && (a[n - 1] % 2 == 1) ? "Yes" : "No");↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:849B]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
First way: consider the first three points. What cases are there?↵
↵
Second way: consider the first point. Either it's on a single line alone, or the line that passes through it passes through another point. Iterate over this point.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:849B]↵
</spoiler>↵
↵
<spoiler summary="Tommyr7's solution (first idea)">↵
~~~↵
#include <bits/stdc++.h>↵
#define eps 1e-7↵
using namespace std;↵
int read()↵
{↵
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*10+ch-'0';ch=getchar();}↵
return x*f;↵
}↵
int n,a[1007];↵
bool vis[1007];↵
bool check(double k,int b)↵
{↵
memset(vis,false,sizeof(vis));↵
int cnt=0;↵
for (int i=1;i<=n;i++)↵
{↵
if (a[i]-b==1LL*k*(i-1)) ↵
{↵
vis[i]=true;↵
++cnt;↵
}↵
}↵
if (cnt==n) return false;↵
if (cnt==n-1) return true;↵
int pos1=0;↵
for (int i=1;i<=n;i++)↵
if (!vis[i]&&pos1==0) pos1=i;↵
for (int i=pos1+1;i<=n;i++)↵
if (!vis[i])↵
{↵
if (fabs((double)(a[i]-a[pos1])/(i-pos1)-k)>eps) return false;↵
}↵
return true;↵
}↵
int main()↵
{↵
n=read();↵
for (int i=1;i<=n;i++)↵
a[i]=read();↵
bool ans=false;↵
ans|=check(1.0*(a[2]-a[1]),a[1]);↵
ans|=check(0.5*(a[3]-a[1]),a[1]);↵
ans|=check(1.0*(a[3]-a[2]),a[2]*2-a[3]);↵
if (ans) printf("Yes\n"); else printf("No\n");↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
<spoiler summary="Model solution (second idea)">↵
~~~↵
#include <cstdio>↵
#include <algorithm>↵
static const int MAXN = 1004;↵
↵
int n;↵
int y[MAXN];↵
↵
bool on_first[MAXN];↵
↵
bool check()↵
{↵
for (int i = 1; i < n; ++i) {↵
for (int j = 0; j < n; ++j) {↵
if ((long long)i * (y[j] - y[0]) == (long long)j * (y[i] - y[0]))↵
on_first[j] = true;↵
else on_first[j] = false;↵
}↵
int start_idx = -1;↵
bool valid = true;↵
for (int j = 0; j < n; ++j) if (!on_first[j]) {↵
if (start_idx == -1) {↵
start_idx = j;↵
} else if ((long long)i * (y[j] - y[start_idx]) != (long long)(j - start_idx) * (y[i] - y[0])) {↵
valid = false; break;↵
}↵
}↵
if (valid && start_idx != -1) return true;↵
}↵
return false;↵
}↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d", &y[i]);↵
↵
bool ans = false;↵
ans |= check();↵
std::reverse(y, y + n);↵
ans |= check();↵
↵
puts(ans ? "Yes" : "No");↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:848A]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
For a given string, how to calculate the cost?↵
↵
<spoiler summary="More">↵
For each letter, count how many times it appears in the original string.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:848A]↵
</spoiler>↵
↵
<spoiler summary="Kalinin's solution">↵
~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
using ld = long double;↵
using D = double;↵
using uint = unsigned int;↵
template<typename T>↵
using pair2 = pair<T, T>;↵
↵
#ifdef WIN32↵
#define LLD "%I64d"↵
#else↵
#define LLD "%lld"↵
#endif↵
↵
#define pb push_back↵
#define mp make_pair↵
#define all(x) (x).begin(),(x).end()↵
#define fi first↵
#define se second↵
↵
int main()↵
{↵
int k;↵
scanf("%d", &k);↵
for (int i = 0; i < 26; i++)↵
{↵
int cnt = 1;↵
while ((cnt + 1) * cnt / 2 <= k) cnt++;↵
k -= cnt * (cnt - 1) / 2;↵
for (int j = 0; j < cnt; j++) printf("%c", 'a' + i);↵
}↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
<spoiler summary="Model solution with knapsack (!)">↵
~~~↵
#include <cstdio>↵
#include <vector>↵
static const int MAXK = 100002;↵
static const int INF = 0x3fffffff;↵
↵
int f[MAXK];↵
int pred[MAXK];↵
↵
int main()↵
{↵
f[0] = 0;↵
for (int i = 1; i < MAXK; ++i) f[i] = INF;↵
for (int i = 0; i < MAXK; ++i) pred[i] = -1;↵
↵
for (int i = 0; i < MAXK; ++i) if (f[i] != INF) {↵
for (int j = 2; i + j * (j - 1) / 2 < MAXK; ++j)↵
if (f[i + j * (j - 1) / 2] > f[i] + 1) {↵
f[i + j * (j - 1) / 2] = f[i] + 1;↵
pred[i + j * (j - 1) / 2] = j;↵
}↵
} else printf("Assertion failed at %d\n", i);↵
↵
int k;↵
scanf("%d", &k);↵
if (k == 0) { puts("a"); return 0; }↵
std::vector<int> v;↵
for (; k > 0; k -= pred[k] * (pred[k] - 1) / 2) {↵
v.push_back(pred[k]);↵
}↵
for (int i = 0; i < v.size(); ++i) {↵
for (int j = 0; j < v[i]; ++j) putchar('a' + i);↵
}↵
putchar('\n');↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:848B]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
When do dancers collide? What changes and what keeps the same?↵
↵
<spoiler summary="Next">↵
Group dancers by $p - t$. What happens next?↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:848B]↵
</spoiler>↵
↵
<spoiler summary="Model solution">↵
~~~↵
#include <cstdio>↵
#include <algorithm>↵
#include <vector>↵
static const int MAXN = 100004;↵
static const int MAXW = 100003;↵
static const int MAXT = 100002;↵
↵
int n, w, h;↵
int g[MAXN], p[MAXN], t[MAXN];↵
↵
std::vector<int> s[MAXW + MAXT];↵
int ans_x[MAXN], ans_y[MAXN];↵
↵
int main()↵
{↵
scanf("%d%d%d", &n, &w, &h);↵
for (int i = 0; i < n; ++i) {↵
scanf("%d%d%d", &g[i], &p[i], &t[i]);↵
s[p[i] - t[i] + MAXT].push_back(i);↵
}↵
↵
std::vector<int> xs, ys;↵
for (int i = 0; i < MAXW + MAXT; ++i) if (!s[i].empty()) {↵
for (int u : s[i]) {↵
if (g[u] == 1) xs.push_back(p[u]);↵
else ys.push_back(p[u]);↵
}↵
std::sort(xs.begin(), xs.end());↵
std::sort(ys.begin(), ys.end());↵
std::sort(s[i].begin(), s[i].end(), [] (int u, int v) {↵
if (g[u] != g[v]) return (g[u] == 2);↵
else return (g[u] == 2 ? p[u] > p[v] : p[u] < p[v]);↵
});↵
for (int j = 0; j < xs.size(); ++j) {↵
ans_x[s[i][j]] = xs[j];↵
ans_y[s[i][j]] = h;↵
}↵
for (int j = 0; j < ys.size(); ++j) {↵
ans_x[s[i][j + xs.size()]] = w;↵
ans_y[s[i][j + xs.size()]] = ys[ys.size() - j - 1];↵
}↵
xs.clear();↵
ys.clear();↵
}↵
↵
for (int i = 0; i < n; ++i) printf("%d %d\n", ans_x[i], ans_y[i]);↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:848C]↵
↵
by [user:adedalic,2017-09-01]↵
↵
<spoiler summary="Hint">↵
Difference between last occurrence and first occurrence equals the sum of differences between pairs of adjacent occurrences. Handle this with some segment tree, or even non-standard size block decomposition, say sizes of $O(n^{2/3})$.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:848C]↵
</spoiler>↵
↵
<spoiler summary="Model solution">↵
~~~↵
#include <bits/stdc++.h>↵
↵
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)↵
#define forn(i, n) fore(i, 0, n)↵
↵
#define all(a) (a).begin(), (a).end()↵
#define sqr(a) ((a) * (a))↵
#define sz(a) int(a.size())↵
#define mp make_pair↵
#define pb push_back↵
↵
#define x first↵
#define y second↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
mt19937 myRand(time(NULL));↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵
↵
const int N = 100 * 1000 + 555;↵
↵
int n, m, aa[N], a[N];↵
int qt[N], qx[N], qy[N];↵
↵
inline bool read() {↵
if(!(cin >> n >> m))↵
return false;↵
↵
forn(i, n)↵
assert(scanf("%d", &aa[i]) == 1);↵
↵
forn(i, m) {↵
assert(scanf("%d%d%d", &qt[i], &qx[i], &qy[i]) == 3);↵
qx[i]--;↵
}↵
↵
return true;↵
}↵
↵
vector<int> vars[4 * N];↵
vector<li> f[4 * N];↵
li sumAll[4 * N];↵
↵
inline void addValF(int k, int pos, int val) {↵
sumAll[k] += val;↵
for(; pos < sz(f[k]); pos |= pos + 1)↵
f[k][pos] += val;↵
}↵
↵
inline li sum(int k, int pos) {↵
li ans = 0;↵
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)↵
ans += f[k][pos];↵
↵
return ans;↵
}↵
↵
inline li getSumF(int k, int pos) {↵
return sumAll[k] - sum(k, pos - 1);↵
}↵
↵
li getSumST(int v, int l, int r, int lf, int rg, int val) {↵
if(l >= r || lf >= rg)↵
return 0;↵
↵
if(l == lf && r == rg) {↵
int pos = int(lower_bound(all(vars[v]), val) - vars[v].begin());↵
return getSumF(v, pos);↵
}↵
↵
int mid = (l + r) >> 1;↵
↵
li ans = 0;↵
if(lf < mid)↵
ans += getSumST(2 * v + 1, l, mid, lf, min(mid, rg), val);↵
if(rg > mid)↵
ans += getSumST(2 * v + 2, mid, r, max(lf, mid), rg, val);↵
↵
return ans;↵
}↵
↵
void addValST(int k, int v, int l, int r, int pos, int pos2, int val) {↵
if(l >= r)↵
return;↵
↵
if(!k)↵
vars[v].pb(pos2);↵
else {↵
int cpos = int(lower_bound(all(vars[v]), pos2) - vars[v].begin());↵
addValF(v, cpos, val);↵
}↵
↵
if(l + 1 == r) {↵
assert(l == pos);↵
return;↵
}↵
↵
int mid = (l + r) >> 1;↵
↵
if(pos < mid)↵
addValST(k, 2 * v + 1, l, mid, pos, pos2, val);↵
else↵
addValST(k, 2 * v + 2, mid, r, pos, pos2, val);↵
}↵
↵
int pr[N];↵
set<int> ids[N];↵
↵
void build(int k, int v, int l, int r) {↵
fore(i, l, r)↵
if(!k)↵
vars[v].pb(pr[i]);↵
else {↵
int pos = int(lower_bound(all(vars[v]), pr[i]) - vars[v].begin());↵
addValF(v, pos, i - pr[i]);↵
}↵
↵
if(l + 1 == r)↵
return;↵
↵
int mid = (l + r) >> 1;↵
↵
build(k, 2 * v + 1, l, mid);↵
build(k, 2 * v + 2, mid, r);↵
}↵
↵
inline void eraseSets(int k, int pos) {↵
addValST(k, 0, 0, n, pos, pr[pos], -(pos - pr[pos]));↵
ids[ a[pos] ].erase(pos);↵
↵
auto it2 = ids[ a[pos] ].lower_bound(pos);↵
↵
if(it2 != ids[ a[pos] ].end()) {↵
int np = *it2;↵
assert(a[np] == a[pos]);↵
assert(pr[np] == pos);↵
↵
addValST(k, 0, 0, n, np, pr[np], -(np - pr[np]));↵
↵
pr[np] = pr[pos];↵
addValST(k, 0, 0, n, np, pr[np], +(np - pr[np]));↵
}↵
↵
a[pos] = -1;↵
pr[pos] = -1;↵
}↵
↵
inline void insertSets(int k, int pos, int nval) {↵
auto it2 = ids[nval].lower_bound(pos);↵
assert(it2 == ids[nval].end() || *it2 > pos);↵
↵
if(it2 != ids[nval].end()) {↵
int np = *it2;↵
assert(a[np] == nval);↵
↵
addValST(k, 0, 0, n, np, pr[np], -(np - pr[np]));↵
↵
pr[np] = pos;↵
addValST(k, 0, 0, n, np, pr[np], +(np - pr[np]));↵
}↵
↵
pr[pos] = -1;↵
if(it2 != ids[nval].begin()) {↵
auto it1 = it2; it1--;↵
assert(*it1 < pos);↵
↵
pr[pos] = *it1;↵
}↵
addValST(k, 0, 0, n, pos, pr[pos], +(pos - pr[pos]));↵
↵
ids[nval].insert(pos);↵
a[pos] = nval;↵
}↵
↵
inline void precalc() {↵
forn(v, 4 * N) {↵
sort(all(vars[v]));↵
vars[v].erase(unique(all(vars[v])), vars[v].end());↵
↵
f[v].assign(sz(vars[v]), 0);↵
sumAll[v] = 0;↵
}↵
}↵
↵
inline void solve() {↵
forn(k, 2) {↵
if(k) precalc();↵
↵
forn(i, N)↵
ids[i].clear();↵
forn(i, n)↵
a[i] = aa[i];↵
↵
vector<int> ls(n + 1, -1);↵
forn(i, n) {↵
pr[i] = ls[ a[i] ];↵
ls[ a[i] ] = i;↵
↵
ids[ a[i] ].insert(i);↵
}↵
↵
build(k, 0, 0, n);↵
↵
// cerr << k << " " << clock() << endl;↵
↵
forn(q, m) {↵
if(qt[q] == 1) {↵
eraseSets(k, qx[q]);↵
insertSets(k, qx[q], qy[q]);↵
} else↵
if(k) printf("%I64d\n", getSumST(0, 0, n, qx[q], qy[q], qx[q]));↵
}↵
↵
// cerr << k << " " << clock() << endl;↵
}↵
}↵
↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
while(read()) {↵
solve(); ↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() - t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:848D]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
Use DP. $f[i][j]$ keeps the number of subgraphs with $i$ operations and a minimum cut of $j$. The transition may be in a knapsack-like manner. Add more functions (say another $g[i][j]$) if needed to make it faster.↵
↵
There are more than one way to do DP, you can also read about other nice solutions [here](http://codeforces.me/blog/entry/54214?#comment-383006) and [here](http://codeforces.me/blog/entry/54214?#comment-383035).↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:848D]↵
</spoiler>↵
↵
<spoiler summary="Model solution">↵
~~~↵
#include <cstdio>↵
#include <cstring>↵
typedef long long int64;↵
static const int MAXN = 53;↵
static const int MODULUS = 1e9 + 7;↵
#define _ % MODULUS↵
#define __ %= MODULUS↵
↵
int n, m;↵
// f[# of operations][mincut] -- total number of graphs↵
// g[# of operations][mincut] -- number of ordered pairs of two graphs↵
int64 f[MAXN][MAXN] = {{ 0 }}, g[MAXN][MAXN] = {{ 0 }};↵
int64 h[MAXN][MAXN];↵
↵
inline int64 qpow(int64 base, int exp) {↵
int64 ans = 1;↵
for (; exp; exp >>= 1, (base *= base)__) if (exp & 1) (ans *= base)__;↵
return ans;↵
}↵
int64 inv[MAXN];↵
↵
int main()↵
{↵
for (int i = 0; i < MAXN; ++i) inv[i] = qpow(i, MODULUS - 2);↵
↵
scanf("%d%d", &n, &m);↵
↵
f[0][1] = 1;↵
for (int i = 1; i <= n; ++i) {↵
for (int j = 1; j <= i + 1; ++j) {↵
// Calculate g[i][*]↵
// pair(i)(j) = graph(p)(r) in series with graph(q)(s)↵
// where p+q == i-1, min(r, s) == j↵
for (int p = 0; p <= i - 1; ++p) {↵
int q = i - 1 - p;↵
for (int r = j; r <= p + 1; ++r)↵
(g[i][j] += (int64)f[p][r] * f[q][j])__;↵
for (int s = j + 1; s <= q + 1; ++s)↵
(g[i][j] += (int64)f[p][j] * f[q][s])__;↵
}↵
// Update all f with g[i][*]↵
// Iterate over the number of times pair(i)(j) is appended in parallel, let it be t↵
// h is used as a temporary array↵
memset(h, 0, sizeof h);↵
for (int p = 0; p <= n; ++p)↵
for (int q = 1; q <= p + 1; ++q) {↵
int64 comb = 1;↵
for (int t = 1; p + t * i <= n; ++t) {↵
comb = comb * (g[i][j] + t - 1)_ * inv[t]_;↵
(h[p + t * i][q + t * j] += f[p][q] * comb)__;↵
}↵
}↵
for (int p = 0; p <= n; ++p)↵
for (int q = 1; q <= p + 1; ++q)↵
(f[p][q] += h[p][q])__;↵
}↵
}↵
↵
printf("%lld\n", f[n][m]);↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:848E]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
Break the circle down into semicircles. Then there will be 1D/1D recurrences over several functions.↵
↵
<spoiler summary="Last insight">↵
Use FFT in a divide-and-conquer manner to optimize it.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:848E]↵
</spoiler>↵
↵
<spoiler summary="O(n^2) solution">↵
~~~↵
#include <cstdio>↵
typedef long long int64;↵
static const int MAXN = 50004;↵
static const int MODULUS = 998244353;↵
#define _ % MODULUS↵
#define __ %= MODULUS↵
↵
int n;↵
int64 g[MAXN];↵
int64 f0[MAXN], f1[MAXN], f2[MAXN];↵
↵
int main()↵
{↵
scanf("%d", &n);↵
↵
g[0] = 1;↵
g[2] = 1;↵
for (int i = 4; i <= n; i += 2) g[i] = (g[i - 4] + g[i - 2])_;↵
↵
f0[0] = 0;↵
f1[0] = 1;↵
f2[0] = 4;↵
for (int i = 1; i <= n; ++i) {↵
f0[i] = g[i] * i _ * i _;↵
for (int j = 1; j <= i - 2; ++j) {↵
f0[i] += g[j] * j _ * j _ * f0[i - j - 1]_;↵
f0[i] += g[j - 1] * j _ * j _ * f1[i - j - 2]_;↵
}↵
f1[i] = g[i] * (i + 1)_ * (i + 1)_ + f0[i - 1];↵
for (int j = 1; j <= i - 2; ++j) {↵
f1[i] += g[j] * (j + 1)_ * (j + 1)_ * f0[i - j - 1]_;↵
f1[i] += g[j - 1] * (j + 1)_ * (j + 1)_ * f1[i - j - 2]_;↵
}↵
f0[i]__; f1[i]__;↵
}↵
for (int i = 1; i <= n; ++i) {↵
f2[i] = g[i] * (i + 2)_ * (i + 2)_ + f1[i - 1];↵
for (int j = 1; j <= i - 1; ++j) {↵
f2[i] += g[j] * (j + 1)_ * (j + 1)_ * f1[i - j - 1]_;↵
f2[i] += g[j - 1] * (j + 1)_ * (j + 1)_ * f2[i - j - 2]_;↵
}↵
f2[i]__;↵
}↵
↵
int64 ans = 0;↵
↵
ans += (g[n - 1] + g[n - 3]) * (n - 1)_ * (n - 1)_ * n _;↵
for (int i = 2; i <= n - 2; ++i) {↵
ans += g[i - 1] * (i - 1)_ * (i - 1)_ * f0[n - i - 1]_ * i _;↵
ans += g[i - 2] * (i - 1)_ * (i - 1)_ * f1[n - i - 2]_ * 2 * i _;↵
if (i >= 3 && i <= n - 3)↵
ans += g[i - 3] * (i - 1)_ * (i - 1)_ * f2[n - i - 3]_ * i _;↵
}↵
↵
printf("%lld\n", ans _);↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
<spoiler summary="Model solution">↵
~~~↵
#include <cstdio>↵
#include <cstring>↵
typedef long long int64;↵
static const int LOGN = 18;↵
static const int MAXN = 1 << LOGN;↵
static const int MODULUS = 998244353;↵
static const int PRIMITIVE = 2192;↵
#define _ % MODULUS↵
#define __ %= MODULUS↵
template <typename T> inline void swap(T &a, T &b) { static T t; t = a; a = b; b = t; }↵
↵
int n;↵
int64 g[MAXN];↵
int64 g0[MAXN], g1[MAXN], g2[MAXN];↵
int64 f0[MAXN], f1[MAXN], f2[MAXN];↵
↵
int64 q0[MAXN], q1[MAXN];↵
int64 t1[MAXN], t2[MAXN], t3[MAXN], t4[MAXN];↵
↵
inline int qpow(int64 base, int exp)↵
{↵
int64 ans = 1;↵
for (; exp; exp >>= 1) { if (exp & 1) (ans *= base)__; (base *= base)__; }↵
return ans;↵
}↵
↵
int bitrev[LOGN][MAXN];↵
int root[2][LOGN];↵
inline void fft(int n, int64 *a, int direction)↵
{↵
int s = __builtin_ctz(n);↵
int64 u, v, r, w;↵
for (int i = 0; i < n; ++i) if (i < bitrev[s][i]) swap(a[i], a[bitrev[s][i]]);↵
for (int i = 1; i <= n; i <<= 1)↵
for (int j = 0; j < n; j += i) {↵
r = root[direction == -1][__builtin_ctz(i)];↵
w = 1;↵
for (int k = j; k < j + (i >> 1); ++k) {↵
u = a[k];↵
v = (a[k + (i >> 1)] * w)_;↵
a[k] = (u + v)_;↵
a[k + (i >> 1)] = (u - v + MODULUS)_;↵
w = (w * r)_;↵
}↵
}↵
}↵
↵
inline void convolve(int n, int64 *a, int64 *b, int64 *c)↵
{↵
static int64 a1[MAXN], b1[MAXN];↵
memcpy(a1, a, n * 2 * sizeof(int64));↵
memcpy(b1, b, n * 2 * sizeof(int64));↵
memset(a + n, 0, n * sizeof(int64));↵
memset(b + n, 0, n * sizeof(int64));↵
fft(n * 2, a, +1);↵
fft(n * 2, b, +1);↵
int64 q = qpow(n * 2, MODULUS - 2);↵
for (int i = 0; i < n * 2; ++i) c[i] = a[i] * b[i]_;↵
fft(n * 2, c, -1);↵
for (int i = 0; i < n; ++i) c[i] = c[i] * q _;↵
memcpy(a, a1, n * 2 * sizeof(int64));↵
memcpy(b, b1, n * 2 * sizeof(int64));↵
}↵
↵
// Calcukates f0 and f1.↵
void solve_1(int l, int r)↵
{↵
if (l == r) {↵
(f0[l] += g0[l])__;↵
(f1[l] += g1[l])__;↵
return;↵
}↵
↵
int m = (l + r) >> 1;↵
↵
solve_1(l, m);↵
↵
int len = 1;↵
while (len < r - l + 1) len <<= 1;↵
for (int i = 0; i < len; ++i) q0[i] = (i + l <= m ? f0[i + l] : 0);↵
for (int i = 0; i < len; ++i) q1[i] = (i + l <= m ? f1[i + l] : 0);↵
for (int i = len; i < len * 2; ++i) q0[i] = q1[i] = 0;↵
convolve(len, g0, q0, t1);↵
convolve(len, g1, q0, t2);↵
convolve(len, g1, q1, t3);↵
convolve(len, g2, q1, t4);↵
↵
for (int i = 0; i < len; ++i) {↵
if (i + l >= m + 1 - 1 && i + l <= r - 1) {↵
(f0[i + l + 1] += t1[i])__;↵
(f1[i + l + 1] += t2[i])__;↵
}↵
if (i + l >= m + 1 - 3 && i + l <= r - 3) {↵
(f0[i + l + 3] += t3[i])__;↵
(f1[i + l + 3] += t4[i])__;↵
}↵
}↵
↵
solve_1(m + 1, r);↵
}↵
↵
// Calculates f2.↵
void solve_2(int l, int r)↵
{↵
if (l == r) {↵
(f2[l] += (g2[l] + (l >= 1 ? t1[l - 1] : 0)))__;↵
return;↵
}↵
↵
int m = (l + r) >> 1;↵
↵
solve_2(l, m);↵
↵
int len = 1;↵
while (len < r - l + 1) len <<= 1;↵
for (int i = 0; i < len; ++i) q0[i] = (i + l <= m ? f2[i + l] : 0);↵
for (int i = len; i < len * 2; ++i) q0[i] = 0;↵
convolve(len, g2, q0, t2);↵
↵
for (int i = 0; i < len; ++i) {↵
if (i + l >= m + 1 - 3 && i + l <= r - 3) {↵
(f2[i + l + 3] += t2[i])__;↵
}↵
}↵
↵
solve_2(m + 1, r);↵
}↵
↵
int main()↵
{↵
for (int s = 0; s < LOGN; ++s)↵
for (int i = 0; i < (1 << s); ++i)↵
bitrev[s][i] = (bitrev[s][i >> 1] >> 1) | ((i & 1) << (s - 1));↵
for (int i = 0; i < LOGN; ++i) {↵
root[0][i] = qpow(PRIMITIVE, MAXN >> i);↵
root[1][i] = qpow(PRIMITIVE, MAXN - (MAXN >> i));↵
}↵
↵
scanf("%d", &n);↵
↵
g[0] = 1;↵
g[2] = 1;↵
for (int i = 4; i <= n; i += 2) g[i] = (g[i - 4] + g[i - 2])_;↵
for (int i = 0; i <= n; ++i) {↵
g0[i] = g[i] * i _ * i _;↵
g1[i] = g[i] * (i + 1)_ * (i + 1)_;↵
g2[i] = g[i] * (i + 2)_ * (i + 2)_;↵
}↵
↵
solve_1(0, n);↵
↵
int len = 1;↵
while (len < n) len <<= 1;↵
convolve(len, g1, f1, t1);↵
solve_2(0, n);↵
↵
int64 ans = 0;↵
↵
ans += (g[n - 1] + g[n - 3]) * (n - 1)_ * (n - 1)_ * n _;↵
for (int i = 2; i <= n - 2; ++i) {↵
ans += g0[i - 1] * f0[n - i - 1]_ * i _;↵
ans += g1[i - 2] * f1[n - i - 2]_ * 2 * i _;↵
if (i >= 3 && i <= n - 3)↵
ans += g2[i - 3] * f2[n - i - 3]_ * i _;↵
}↵
↵
printf("%lld\n", ans _);↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
## Behind the scene and random things (read if tired of problemsolving)↵
↵
<spoiler summary="Expand">↵
↵
Perhaps some may have noticed that at the end of [editorial of #418](http://codeforces.me/blog/entry/52449) it's written that↵
↵
> Probably it will be for Ha...↵
↵
Yes, I had had ideas for the last four problems for Div. 2 by that time. Then I came up with Div. 2 A when lying on bed one night, seems I underestimated its trickiness :/↵
↵
(1 September 2017 is also when the story of **Ha**rry Potter ends, so to me seems like a great coincidence?)↵
↵
After my unsuccessful performance at the National Olympiad (that's another thing to talk about), on that evening when everything seemed dull, I changed Div. 1 E to what it looks like now — it used to be Div. 1 C or so. "I'm poor at problemsolving. This is the hardest I can come up with," I thought, "and if it doesn't qualify then I'd better give up on holding a round with Div. 1."↵
↵
Then in early August I created the proposal with all problems. After it was reviewed, some of them were changed, moved or replaced, and I ended up having no Div. 1 D. I had an idea and put it to Div. 1 D, but we had difficulty distinguishing different complexities, so it was set aside and replaced with the problem from [user:adedalic,2017-09-02]. Schoolwork kept disrupting me from working on preparation, but I managed to allocate time to do it all for my own problems (except tutorials, :P). [user:adedalic,2017-09-02]'s problem is prepared by him and [user:KAN,2017-09-02], thank you!↵
↵
Then two hours before the contest, it was suggested that swapping Div. 1 C and Div. 1 D would be good. I had't had enough time to test the new problem myself, but I thought the second division may prefer data structures to multidimensional DP and agreed. Then Div. 1 contestants jump from A to C and had unfavourable luck... My sympathy, hope you have enjoyed the problems themselves.↵
↵
These are random fragments of the story behind this round. It wouldn't have been possible without you, dear contestants and members of the community. My deep gratitude!↵
↵
Also, the problems feature songs created by songwriters and the voice of Hatsune Miku. Let it be happy or sad, separation or reunion, the problems are all inspired by the songs at the very beginning (not necessarily contents though, for example 2A and 1E are just related to the songs in title). Here's the list if you're interested.↵
↵
* [_ODDS&ENDS_](http://vocadb.net/S/15662) by ryo↵
* [_Tell Your World_](http://vocadb.net/S/8395) by kz↵
* [_from Y to Y_](http://vocadb.net/S/4230) by OneRoom↵
* [_Rooter's Song_](http://vocadb.net/S/71159) by DECO*27↵
* [_Sayonara Souvenir_](http://vocadb.net/S/110348) (Goodbye Souvenir) by Toa↵
* [_shake it!_](http://vocadb.net/S/11593) by emon(Tes.)↵
* [_Hanairo Biyori_](http://vocadb.net/S/39300) (Flower Colored Weather) by Natsume Chiaki↵
↵
</spoiler>↵
↵
Thank you for reading. Next round? Perhaps something more traditional, who knows? Believe me, I'll try harder if this happens.↵
↵
Cheers! \\(^ ^)/↵
↵
<hr>↵
↵
**UPD** Packages for problems are uploaded. They are in Polygon format and contain everything including statements, tests & generators, validators & checkers, and solutions. You can download them from [Google Drive](https://drive.google.com/drive/folders/0B5z87ZbXNZyEcXBtSVhWbDJEN00?usp=sharing) or [Baidu Drive](https://pan.baidu.com/s/1eSJ68gE).
↵
With the end of Codeforces Round #431 ([Div. 1](http://codeforces.me/contest/848) and [Div. 2](http://codeforces.me/contest/849)), some might be complaining behind the screen that problems are too tricky or hard, or have been struggling with some supposedly solvable problem... Yes, this time problems seem hard, but anyways, I hope they provided you with something, say rating, fun, ideas, or experience. I don't want to see anyone losing confidence because of failure (bad luck) in a single contest — please, don't do so.↵
↵
Here are the hints, tutorials and codes for the problems. Feel free to discuss about problems in the comments, and point out if something is incorrect or unclear. Thank you!↵
↵
### [problem:849A]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
What will the whole array satisfy? Is that a sufficient condition?↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:849A]↵
</spoiler>↵
↵
<spoiler summary="Model solution">↵
~~~↵
#include <cstdio>↵
static const int MAXN = 102;↵
↵
int n;↵
int a[MAXN];↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);↵
↵
puts((n % 2 == 1) && (a[0] % 2 == 1) && (a[n - 1] % 2 == 1) ? "Yes" : "No");↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:849B]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
First way: consider the first three points. What cases are there?↵
↵
Second way: consider the first point. Either it's on a single line alone, or the line that passes through it passes through another point. Iterate over this point.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:849B]↵
</spoiler>↵
↵
<spoiler summary="Tommyr7's solution (first idea)">↵
~~~↵
#include <bits/stdc++.h>↵
#define eps 1e-7↵
using namespace std;↵
int read()↵
{↵
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*10+ch-'0';ch=getchar();}↵
return x*f;↵
}↵
int n,a[1007];↵
bool vis[1007];↵
bool check(double k,int b)↵
{↵
memset(vis,false,sizeof(vis));↵
int cnt=0;↵
for (int i=1;i<=n;i++)↵
{↵
if (a[i]-b==1LL*k*(i-1)) ↵
{↵
vis[i]=true;↵
++cnt;↵
}↵
}↵
if (cnt==n) return false;↵
if (cnt==n-1) return true;↵
int pos1=0;↵
for (int i=1;i<=n;i++)↵
if (!vis[i]&&pos1==0) pos1=i;↵
for (int i=pos1+1;i<=n;i++)↵
if (!vis[i])↵
{↵
if (fabs((double)(a[i]-a[pos1])/(i-pos1)-k)>eps) return false;↵
}↵
return true;↵
}↵
int main()↵
{↵
n=read();↵
for (int i=1;i<=n;i++)↵
a[i]=read();↵
bool ans=false;↵
ans|=check(1.0*(a[2]-a[1]),a[1]);↵
ans|=check(0.5*(a[3]-a[1]),a[1]);↵
ans|=check(1.0*(a[3]-a[2]),a[2]*2-a[3]);↵
if (ans) printf("Yes\n"); else printf("No\n");↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
<spoiler summary="Model solution (second idea)">↵
~~~↵
#include <cstdio>↵
#include <algorithm>↵
static const int MAXN = 1004;↵
↵
int n;↵
int y[MAXN];↵
↵
bool on_first[MAXN];↵
↵
bool check()↵
{↵
for (int i = 1; i < n; ++i) {↵
for (int j = 0; j < n; ++j) {↵
if ((long long)i * (y[j] - y[0]) == (long long)j * (y[i] - y[0]))↵
on_first[j] = true;↵
else on_first[j] = false;↵
}↵
int start_idx = -1;↵
bool valid = true;↵
for (int j = 0; j < n; ++j) if (!on_first[j]) {↵
if (start_idx == -1) {↵
start_idx = j;↵
} else if ((long long)i * (y[j] - y[start_idx]) != (long long)(j - start_idx) * (y[i] - y[0])) {↵
valid = false; break;↵
}↵
}↵
if (valid && start_idx != -1) return true;↵
}↵
return false;↵
}↵
↵
int main()↵
{↵
scanf("%d", &n);↵
for (int i = 0; i < n; ++i) scanf("%d", &y[i]);↵
↵
bool ans = false;↵
ans |= check();↵
std::reverse(y, y + n);↵
ans |= check();↵
↵
puts(ans ? "Yes" : "No");↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:848A]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
For a given string, how to calculate the cost?↵
↵
<spoiler summary="More">↵
For each letter, count how many times it appears in the original string.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:848A]↵
</spoiler>↵
↵
<spoiler summary="Kalinin's solution">↵
~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
using ll = long long;↵
using ld = long double;↵
using D = double;↵
using uint = unsigned int;↵
template<typename T>↵
using pair2 = pair<T, T>;↵
↵
#ifdef WIN32↵
#define LLD "%I64d"↵
#else↵
#define LLD "%lld"↵
#endif↵
↵
#define pb push_back↵
#define mp make_pair↵
#define all(x) (x).begin(),(x).end()↵
#define fi first↵
#define se second↵
↵
int main()↵
{↵
int k;↵
scanf("%d", &k);↵
for (int i = 0; i < 26; i++)↵
{↵
int cnt = 1;↵
while ((cnt + 1) * cnt / 2 <= k) cnt++;↵
k -= cnt * (cnt - 1) / 2;↵
for (int j = 0; j < cnt; j++) printf("%c", 'a' + i);↵
}↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
<spoiler summary="Model solution with knapsack (!)">↵
~~~↵
#include <cstdio>↵
#include <vector>↵
static const int MAXK = 100002;↵
static const int INF = 0x3fffffff;↵
↵
int f[MAXK];↵
int pred[MAXK];↵
↵
int main()↵
{↵
f[0] = 0;↵
for (int i = 1; i < MAXK; ++i) f[i] = INF;↵
for (int i = 0; i < MAXK; ++i) pred[i] = -1;↵
↵
for (int i = 0; i < MAXK; ++i) if (f[i] != INF) {↵
for (int j = 2; i + j * (j - 1) / 2 < MAXK; ++j)↵
if (f[i + j * (j - 1) / 2] > f[i] + 1) {↵
f[i + j * (j - 1) / 2] = f[i] + 1;↵
pred[i + j * (j - 1) / 2] = j;↵
}↵
} else printf("Assertion failed at %d\n", i);↵
↵
int k;↵
scanf("%d", &k);↵
if (k == 0) { puts("a"); return 0; }↵
std::vector<int> v;↵
for (; k > 0; k -= pred[k] * (pred[k] - 1) / 2) {↵
v.push_back(pred[k]);↵
}↵
for (int i = 0; i < v.size(); ++i) {↵
for (int j = 0; j < v[i]; ++j) putchar('a' + i);↵
}↵
putchar('\n');↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:848B]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
When do dancers collide? What changes and what keeps the same?↵
↵
<spoiler summary="Next">↵
Group dancers by $p - t$. What happens next?↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:848B]↵
</spoiler>↵
↵
<spoiler summary="Model solution">↵
~~~↵
#include <cstdio>↵
#include <algorithm>↵
#include <vector>↵
static const int MAXN = 100004;↵
static const int MAXW = 100003;↵
static const int MAXT = 100002;↵
↵
int n, w, h;↵
int g[MAXN], p[MAXN], t[MAXN];↵
↵
std::vector<int> s[MAXW + MAXT];↵
int ans_x[MAXN], ans_y[MAXN];↵
↵
int main()↵
{↵
scanf("%d%d%d", &n, &w, &h);↵
for (int i = 0; i < n; ++i) {↵
scanf("%d%d%d", &g[i], &p[i], &t[i]);↵
s[p[i] - t[i] + MAXT].push_back(i);↵
}↵
↵
std::vector<int> xs, ys;↵
for (int i = 0; i < MAXW + MAXT; ++i) if (!s[i].empty()) {↵
for (int u : s[i]) {↵
if (g[u] == 1) xs.push_back(p[u]);↵
else ys.push_back(p[u]);↵
}↵
std::sort(xs.begin(), xs.end());↵
std::sort(ys.begin(), ys.end());↵
std::sort(s[i].begin(), s[i].end(), [] (int u, int v) {↵
if (g[u] != g[v]) return (g[u] == 2);↵
else return (g[u] == 2 ? p[u] > p[v] : p[u] < p[v]);↵
});↵
for (int j = 0; j < xs.size(); ++j) {↵
ans_x[s[i][j]] = xs[j];↵
ans_y[s[i][j]] = h;↵
}↵
for (int j = 0; j < ys.size(); ++j) {↵
ans_x[s[i][j + xs.size()]] = w;↵
ans_y[s[i][j + xs.size()]] = ys[ys.size() - j - 1];↵
}↵
xs.clear();↵
ys.clear();↵
}↵
↵
for (int i = 0; i < n; ++i) printf("%d %d\n", ans_x[i], ans_y[i]);↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:848C]↵
↵
by [user:adedalic,2017-09-01]↵
↵
<spoiler summary="Hint">↵
Difference between last occurrence and first occurrence equals the sum of differences between pairs of adjacent occurrences. Handle this with some segment tree, or even non-standard size block decomposition, say sizes of $O(n^{2/3})$.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:848C]↵
</spoiler>↵
↵
<spoiler summary="Model solution">↵
~~~↵
#include <bits/stdc++.h>↵
↵
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)↵
#define forn(i, n) fore(i, 0, n)↵
↵
#define all(a) (a).begin(), (a).end()↵
#define sqr(a) ((a) * (a))↵
#define sz(a) int(a.size())↵
#define mp make_pair↵
#define pb push_back↵
↵
#define x first↵
#define y second↵
↵
using namespace std;↵
↵
template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {↵
return out << "(" << p.first << ", " << p.second << ")";↵
}↵
↵
template<class A> ostream& operator << (ostream &out, const vector<A> &v) {↵
out << "[";↵
forn(i, sz(v)) {↵
if(i > 0)↵
out << " ";↵
out << v[i];↵
}↵
return out << "]";↵
}↵
↵
mt19937 myRand(time(NULL));↵
↵
typedef long long li;↵
typedef long double ld;↵
typedef pair<int, int> pt;↵
↵
inline int gett() {↵
return clock() * 1000 / CLOCKS_PER_SEC;↵
}↵
↵
const ld EPS = 1e-9;↵
const int INF = int(1e9);↵
const li INF64 = li(INF) * INF;↵
const ld PI = 3.1415926535897932384626433832795;↵
↵
const int N = 100 * 1000 + 555;↵
↵
int n, m, aa[N], a[N];↵
int qt[N], qx[N], qy[N];↵
↵
inline bool read() {↵
if(!(cin >> n >> m))↵
return false;↵
↵
forn(i, n)↵
assert(scanf("%d", &aa[i]) == 1);↵
↵
forn(i, m) {↵
assert(scanf("%d%d%d", &qt[i], &qx[i], &qy[i]) == 3);↵
qx[i]--;↵
}↵
↵
return true;↵
}↵
↵
vector<int> vars[4 * N];↵
vector<li> f[4 * N];↵
li sumAll[4 * N];↵
↵
inline void addValF(int k, int pos, int val) {↵
sumAll[k] += val;↵
for(; pos < sz(f[k]); pos |= pos + 1)↵
f[k][pos] += val;↵
}↵
↵
inline li sum(int k, int pos) {↵
li ans = 0;↵
for(; pos >= 0; pos = (pos & (pos + 1)) - 1)↵
ans += f[k][pos];↵
↵
return ans;↵
}↵
↵
inline li getSumF(int k, int pos) {↵
return sumAll[k] - sum(k, pos - 1);↵
}↵
↵
li getSumST(int v, int l, int r, int lf, int rg, int val) {↵
if(l >= r || lf >= rg)↵
return 0;↵
↵
if(l == lf && r == rg) {↵
int pos = int(lower_bound(all(vars[v]), val) - vars[v].begin());↵
return getSumF(v, pos);↵
}↵
↵
int mid = (l + r) >> 1;↵
↵
li ans = 0;↵
if(lf < mid)↵
ans += getSumST(2 * v + 1, l, mid, lf, min(mid, rg), val);↵
if(rg > mid)↵
ans += getSumST(2 * v + 2, mid, r, max(lf, mid), rg, val);↵
↵
return ans;↵
}↵
↵
void addValST(int k, int v, int l, int r, int pos, int pos2, int val) {↵
if(l >= r)↵
return;↵
↵
if(!k)↵
vars[v].pb(pos2);↵
else {↵
int cpos = int(lower_bound(all(vars[v]), pos2) - vars[v].begin());↵
addValF(v, cpos, val);↵
}↵
↵
if(l + 1 == r) {↵
assert(l == pos);↵
return;↵
}↵
↵
int mid = (l + r) >> 1;↵
↵
if(pos < mid)↵
addValST(k, 2 * v + 1, l, mid, pos, pos2, val);↵
else↵
addValST(k, 2 * v + 2, mid, r, pos, pos2, val);↵
}↵
↵
int pr[N];↵
set<int> ids[N];↵
↵
void build(int k, int v, int l, int r) {↵
fore(i, l, r)↵
if(!k)↵
vars[v].pb(pr[i]);↵
else {↵
int pos = int(lower_bound(all(vars[v]), pr[i]) - vars[v].begin());↵
addValF(v, pos, i - pr[i]);↵
}↵
↵
if(l + 1 == r)↵
return;↵
↵
int mid = (l + r) >> 1;↵
↵
build(k, 2 * v + 1, l, mid);↵
build(k, 2 * v + 2, mid, r);↵
}↵
↵
inline void eraseSets(int k, int pos) {↵
addValST(k, 0, 0, n, pos, pr[pos], -(pos - pr[pos]));↵
ids[ a[pos] ].erase(pos);↵
↵
auto it2 = ids[ a[pos] ].lower_bound(pos);↵
↵
if(it2 != ids[ a[pos] ].end()) {↵
int np = *it2;↵
assert(a[np] == a[pos]);↵
assert(pr[np] == pos);↵
↵
addValST(k, 0, 0, n, np, pr[np], -(np - pr[np]));↵
↵
pr[np] = pr[pos];↵
addValST(k, 0, 0, n, np, pr[np], +(np - pr[np]));↵
}↵
↵
a[pos] = -1;↵
pr[pos] = -1;↵
}↵
↵
inline void insertSets(int k, int pos, int nval) {↵
auto it2 = ids[nval].lower_bound(pos);↵
assert(it2 == ids[nval].end() || *it2 > pos);↵
↵
if(it2 != ids[nval].end()) {↵
int np = *it2;↵
assert(a[np] == nval);↵
↵
addValST(k, 0, 0, n, np, pr[np], -(np - pr[np]));↵
↵
pr[np] = pos;↵
addValST(k, 0, 0, n, np, pr[np], +(np - pr[np]));↵
}↵
↵
pr[pos] = -1;↵
if(it2 != ids[nval].begin()) {↵
auto it1 = it2; it1--;↵
assert(*it1 < pos);↵
↵
pr[pos] = *it1;↵
}↵
addValST(k, 0, 0, n, pos, pr[pos], +(pos - pr[pos]));↵
↵
ids[nval].insert(pos);↵
a[pos] = nval;↵
}↵
↵
inline void precalc() {↵
forn(v, 4 * N) {↵
sort(all(vars[v]));↵
vars[v].erase(unique(all(vars[v])), vars[v].end());↵
↵
f[v].assign(sz(vars[v]), 0);↵
sumAll[v] = 0;↵
}↵
}↵
↵
inline void solve() {↵
forn(k, 2) {↵
if(k) precalc();↵
↵
forn(i, N)↵
ids[i].clear();↵
forn(i, n)↵
a[i] = aa[i];↵
↵
vector<int> ls(n + 1, -1);↵
forn(i, n) {↵
pr[i] = ls[ a[i] ];↵
ls[ a[i] ] = i;↵
↵
ids[ a[i] ].insert(i);↵
}↵
↵
build(k, 0, 0, n);↵
↵
// cerr << k << " " << clock() << endl;↵
↵
forn(q, m) {↵
if(qt[q] == 1) {↵
eraseSets(k, qx[q]);↵
insertSets(k, qx[q], qy[q]);↵
} else↵
if(k) printf("%I64d\n", getSumST(0, 0, n, qx[q], qy[q], qx[q]));↵
}↵
↵
// cerr << k << " " << clock() << endl;↵
}↵
}↵
↵
int main(){↵
#ifdef _DEBUG↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
↵
int t = gett();↵
#endif↵
↵
srand(time(NULL));↵
cout << fixed << setprecision(10);↵
↵
while(read()) {↵
solve(); ↵
↵
#ifdef _DEBUG↵
cerr << "TIME = " << gett() - t << endl;↵
t = gett();↵
#endif↵
}↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:848D]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
Use DP. $f[i][j]$ keeps the number of subgraphs with $i$ operations and a minimum cut of $j$. The transition may be in a knapsack-like manner. Add more functions (say another $g[i][j]$) if needed to make it faster.↵
↵
There are more than one way to do DP, you can also read about other nice solutions [here](http://codeforces.me/blog/entry/54214?#comment-383006) and [here](http://codeforces.me/blog/entry/54214?#comment-383035).↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:848D]↵
</spoiler>↵
↵
<spoiler summary="Model solution">↵
~~~↵
#include <cstdio>↵
#include <cstring>↵
typedef long long int64;↵
static const int MAXN = 53;↵
static const int MODULUS = 1e9 + 7;↵
#define _ % MODULUS↵
#define __ %= MODULUS↵
↵
int n, m;↵
// f[# of operations][mincut] -- total number of graphs↵
// g[# of operations][mincut] -- number of ordered pairs of two graphs↵
int64 f[MAXN][MAXN] = {{ 0 }}, g[MAXN][MAXN] = {{ 0 }};↵
int64 h[MAXN][MAXN];↵
↵
inline int64 qpow(int64 base, int exp) {↵
int64 ans = 1;↵
for (; exp; exp >>= 1, (base *= base)__) if (exp & 1) (ans *= base)__;↵
return ans;↵
}↵
int64 inv[MAXN];↵
↵
int main()↵
{↵
for (int i = 0; i < MAXN; ++i) inv[i] = qpow(i, MODULUS - 2);↵
↵
scanf("%d%d", &n, &m);↵
↵
f[0][1] = 1;↵
for (int i = 1; i <= n; ++i) {↵
for (int j = 1; j <= i + 1; ++j) {↵
// Calculate g[i][*]↵
// pair(i)(j) = graph(p)(r) in series with graph(q)(s)↵
// where p+q == i-1, min(r, s) == j↵
for (int p = 0; p <= i - 1; ++p) {↵
int q = i - 1 - p;↵
for (int r = j; r <= p + 1; ++r)↵
(g[i][j] += (int64)f[p][r] * f[q][j])__;↵
for (int s = j + 1; s <= q + 1; ++s)↵
(g[i][j] += (int64)f[p][j] * f[q][s])__;↵
}↵
// Update all f with g[i][*]↵
// Iterate over the number of times pair(i)(j) is appended in parallel, let it be t↵
// h is used as a temporary array↵
memset(h, 0, sizeof h);↵
for (int p = 0; p <= n; ++p)↵
for (int q = 1; q <= p + 1; ++q) {↵
int64 comb = 1;↵
for (int t = 1; p + t * i <= n; ++t) {↵
comb = comb * (g[i][j] + t - 1)_ * inv[t]_;↵
(h[p + t * i][q + t * j] += f[p][q] * comb)__;↵
}↵
}↵
for (int p = 0; p <= n; ++p)↵
for (int q = 1; q <= p + 1; ++q)↵
(f[p][q] += h[p][q])__;↵
}↵
}↵
↵
printf("%lld\n", f[n][m]);↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
↵
### [problem:848E]↵
↵
by [user:cyand1317,2017-09-01]↵
↵
<spoiler summary="Hint">↵
Break the circle down into semicircles. Then there will be 1D/1D recurrences over several functions.↵
↵
<spoiler summary="Last insight">↵
Use FFT in a divide-and-conquer manner to optimize it.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:848E]↵
</spoiler>↵
↵
<spoiler summary="O(n^2) solution">↵
~~~↵
#include <cstdio>↵
typedef long long int64;↵
static const int MAXN = 50004;↵
static const int MODULUS = 998244353;↵
#define _ % MODULUS↵
#define __ %= MODULUS↵
↵
int n;↵
int64 g[MAXN];↵
int64 f0[MAXN], f1[MAXN], f2[MAXN];↵
↵
int main()↵
{↵
scanf("%d", &n);↵
↵
g[0] = 1;↵
g[2] = 1;↵
for (int i = 4; i <= n; i += 2) g[i] = (g[i - 4] + g[i - 2])_;↵
↵
f0[0] = 0;↵
f1[0] = 1;↵
f2[0] = 4;↵
for (int i = 1; i <= n; ++i) {↵
f0[i] = g[i] * i _ * i _;↵
for (int j = 1; j <= i - 2; ++j) {↵
f0[i] += g[j] * j _ * j _ * f0[i - j - 1]_;↵
f0[i] += g[j - 1] * j _ * j _ * f1[i - j - 2]_;↵
}↵
f1[i] = g[i] * (i + 1)_ * (i + 1)_ + f0[i - 1];↵
for (int j = 1; j <= i - 2; ++j) {↵
f1[i] += g[j] * (j + 1)_ * (j + 1)_ * f0[i - j - 1]_;↵
f1[i] += g[j - 1] * (j + 1)_ * (j + 1)_ * f1[i - j - 2]_;↵
}↵
f0[i]__; f1[i]__;↵
}↵
for (int i = 1; i <= n; ++i) {↵
f2[i] = g[i] * (i + 2)_ * (i + 2)_ + f1[i - 1];↵
for (int j = 1; j <= i - 1; ++j) {↵
f2[i] += g[j] * (j + 1)_ * (j + 1)_ * f1[i - j - 1]_;↵
f2[i] += g[j - 1] * (j + 1)_ * (j + 1)_ * f2[i - j - 2]_;↵
}↵
f2[i]__;↵
}↵
↵
int64 ans = 0;↵
↵
ans += (g[n - 1] + g[n - 3]) * (n - 1)_ * (n - 1)_ * n _;↵
for (int i = 2; i <= n - 2; ++i) {↵
ans += g[i - 1] * (i - 1)_ * (i - 1)_ * f0[n - i - 1]_ * i _;↵
ans += g[i - 2] * (i - 1)_ * (i - 1)_ * f1[n - i - 2]_ * 2 * i _;↵
if (i >= 3 && i <= n - 3)↵
ans += g[i - 3] * (i - 1)_ * (i - 1)_ * f2[n - i - 3]_ * i _;↵
}↵
↵
printf("%lld\n", ans _);↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
<spoiler summary="Model solution">↵
~~~↵
#include <cstdio>↵
#include <cstring>↵
typedef long long int64;↵
static const int LOGN = 18;↵
static const int MAXN = 1 << LOGN;↵
static const int MODULUS = 998244353;↵
static const int PRIMITIVE = 2192;↵
#define _ % MODULUS↵
#define __ %= MODULUS↵
template <typename T> inline void swap(T &a, T &b) { static T t; t = a; a = b; b = t; }↵
↵
int n;↵
int64 g[MAXN];↵
int64 g0[MAXN], g1[MAXN], g2[MAXN];↵
int64 f0[MAXN], f1[MAXN], f2[MAXN];↵
↵
int64 q0[MAXN], q1[MAXN];↵
int64 t1[MAXN], t2[MAXN], t3[MAXN], t4[MAXN];↵
↵
inline int qpow(int64 base, int exp)↵
{↵
int64 ans = 1;↵
for (; exp; exp >>= 1) { if (exp & 1) (ans *= base)__; (base *= base)__; }↵
return ans;↵
}↵
↵
int bitrev[LOGN][MAXN];↵
int root[2][LOGN];↵
inline void fft(int n, int64 *a, int direction)↵
{↵
int s = __builtin_ctz(n);↵
int64 u, v, r, w;↵
for (int i = 0; i < n; ++i) if (i < bitrev[s][i]) swap(a[i], a[bitrev[s][i]]);↵
for (int i = 1; i <= n; i <<= 1)↵
for (int j = 0; j < n; j += i) {↵
r = root[direction == -1][__builtin_ctz(i)];↵
w = 1;↵
for (int k = j; k < j + (i >> 1); ++k) {↵
u = a[k];↵
v = (a[k + (i >> 1)] * w)_;↵
a[k] = (u + v)_;↵
a[k + (i >> 1)] = (u - v + MODULUS)_;↵
w = (w * r)_;↵
}↵
}↵
}↵
↵
inline void convolve(int n, int64 *a, int64 *b, int64 *c)↵
{↵
static int64 a1[MAXN], b1[MAXN];↵
memcpy(a1, a, n * 2 * sizeof(int64));↵
memcpy(b1, b, n * 2 * sizeof(int64));↵
memset(a + n, 0, n * sizeof(int64));↵
memset(b + n, 0, n * sizeof(int64));↵
fft(n * 2, a, +1);↵
fft(n * 2, b, +1);↵
int64 q = qpow(n * 2, MODULUS - 2);↵
for (int i = 0; i < n * 2; ++i) c[i] = a[i] * b[i]_;↵
fft(n * 2, c, -1);↵
for (int i = 0; i < n; ++i) c[i] = c[i] * q _;↵
memcpy(a, a1, n * 2 * sizeof(int64));↵
memcpy(b, b1, n * 2 * sizeof(int64));↵
}↵
↵
// Calcukates f0 and f1.↵
void solve_1(int l, int r)↵
{↵
if (l == r) {↵
(f0[l] += g0[l])__;↵
(f1[l] += g1[l])__;↵
return;↵
}↵
↵
int m = (l + r) >> 1;↵
↵
solve_1(l, m);↵
↵
int len = 1;↵
while (len < r - l + 1) len <<= 1;↵
for (int i = 0; i < len; ++i) q0[i] = (i + l <= m ? f0[i + l] : 0);↵
for (int i = 0; i < len; ++i) q1[i] = (i + l <= m ? f1[i + l] : 0);↵
for (int i = len; i < len * 2; ++i) q0[i] = q1[i] = 0;↵
convolve(len, g0, q0, t1);↵
convolve(len, g1, q0, t2);↵
convolve(len, g1, q1, t3);↵
convolve(len, g2, q1, t4);↵
↵
for (int i = 0; i < len; ++i) {↵
if (i + l >= m + 1 - 1 && i + l <= r - 1) {↵
(f0[i + l + 1] += t1[i])__;↵
(f1[i + l + 1] += t2[i])__;↵
}↵
if (i + l >= m + 1 - 3 && i + l <= r - 3) {↵
(f0[i + l + 3] += t3[i])__;↵
(f1[i + l + 3] += t4[i])__;↵
}↵
}↵
↵
solve_1(m + 1, r);↵
}↵
↵
// Calculates f2.↵
void solve_2(int l, int r)↵
{↵
if (l == r) {↵
(f2[l] += (g2[l] + (l >= 1 ? t1[l - 1] : 0)))__;↵
return;↵
}↵
↵
int m = (l + r) >> 1;↵
↵
solve_2(l, m);↵
↵
int len = 1;↵
while (len < r - l + 1) len <<= 1;↵
for (int i = 0; i < len; ++i) q0[i] = (i + l <= m ? f2[i + l] : 0);↵
for (int i = len; i < len * 2; ++i) q0[i] = 0;↵
convolve(len, g2, q0, t2);↵
↵
for (int i = 0; i < len; ++i) {↵
if (i + l >= m + 1 - 3 && i + l <= r - 3) {↵
(f2[i + l + 3] += t2[i])__;↵
}↵
}↵
↵
solve_2(m + 1, r);↵
}↵
↵
int main()↵
{↵
for (int s = 0; s < LOGN; ++s)↵
for (int i = 0; i < (1 << s); ++i)↵
bitrev[s][i] = (bitrev[s][i >> 1] >> 1) | ((i & 1) << (s - 1));↵
for (int i = 0; i < LOGN; ++i) {↵
root[0][i] = qpow(PRIMITIVE, MAXN >> i);↵
root[1][i] = qpow(PRIMITIVE, MAXN - (MAXN >> i));↵
}↵
↵
scanf("%d", &n);↵
↵
g[0] = 1;↵
g[2] = 1;↵
for (int i = 4; i <= n; i += 2) g[i] = (g[i - 4] + g[i - 2])_;↵
for (int i = 0; i <= n; ++i) {↵
g0[i] = g[i] * i _ * i _;↵
g1[i] = g[i] * (i + 1)_ * (i + 1)_;↵
g2[i] = g[i] * (i + 2)_ * (i + 2)_;↵
}↵
↵
solve_1(0, n);↵
↵
int len = 1;↵
while (len < n) len <<= 1;↵
convolve(len, g1, f1, t1);↵
solve_2(0, n);↵
↵
int64 ans = 0;↵
↵
ans += (g[n - 1] + g[n - 3]) * (n - 1)_ * (n - 1)_ * n _;↵
for (int i = 2; i <= n - 2; ++i) {↵
ans += g0[i - 1] * f0[n - i - 1]_ * i _;↵
ans += g1[i - 2] * f1[n - i - 2]_ * 2 * i _;↵
if (i >= 3 && i <= n - 3)↵
ans += g2[i - 3] * f2[n - i - 3]_ * i _;↵
}↵
↵
printf("%lld\n", ans _);↵
↵
return 0;↵
}↵
~~~↵
</spoiler>↵
↵
## Behind the scene and random things (read if tired of problemsolving)↵
↵
<spoiler summary="Expand">↵
↵
Perhaps some may have noticed that at the end of [editorial of #418](http://codeforces.me/blog/entry/52449) it's written that↵
↵
> Probably it will be for Ha...↵
↵
Yes, I had had ideas for the last four problems for Div. 2 by that time. Then I came up with Div. 2 A when lying on bed one night, seems I underestimated its trickiness :/↵
↵
(1 September 2017 is also when the story of **Ha**rry Potter ends, so to me seems like a great coincidence?)↵
↵
After my unsuccessful performance at the National Olympiad (that's another thing to talk about), on that evening when everything seemed dull, I changed Div. 1 E to what it looks like now — it used to be Div. 1 C or so. "I'm poor at problemsolving. This is the hardest I can come up with," I thought, "and if it doesn't qualify then I'd better give up on holding a round with Div. 1."↵
↵
Then in early August I created the proposal with all problems. After it was reviewed, some of them were changed, moved or replaced, and I ended up having no Div. 1 D. I had an idea and put it to Div. 1 D, but we had difficulty distinguishing different complexities, so it was set aside and replaced with the problem from [user:adedalic,2017-09-02]. Schoolwork kept disrupting me from working on preparation, but I managed to allocate time to do it all for my own problems (except tutorials, :P). [user:adedalic,2017-09-02]'s problem is prepared by him and [user:KAN,2017-09-02], thank you!↵
↵
Then two hours before the contest, it was suggested that swapping Div. 1 C and Div. 1 D would be good. I had't had enough time to test the new problem myself, but I thought the second division may prefer data structures to multidimensional DP and agreed. Then Div. 1 contestants jump from A to C and had unfavourable luck... My sympathy, hope you have enjoyed the problems themselves.↵
↵
These are random fragments of the story behind this round. It wouldn't have been possible without you, dear contestants and members of the community. My deep gratitude!↵
↵
Also, the problems feature songs created by songwriters and the voice of Hatsune Miku. Let it be happy or sad, separation or reunion, the problems are all inspired by the songs at the very beginning (not necessarily contents though, for example 2A and 1E are just related to the songs in title). Here's the list if you're interested.↵
↵
* [_ODDS&ENDS_](http://vocadb.net/S/15662) by ryo↵
* [_Tell Your World_](http://vocadb.net/S/8395) by kz↵
* [_from Y to Y_](http://vocadb.net/S/4230) by OneRoom↵
* [_Rooter's Song_](http://vocadb.net/S/71159) by DECO*27↵
* [_Sayonara Souvenir_](http://vocadb.net/S/110348) (Goodbye Souvenir) by Toa↵
* [_shake it!_](http://vocadb.net/S/11593) by emon(Tes.)↵
* [_Hanairo Biyori_](http://vocadb.net/S/39300) (Flower Colored Weather) by Natsume Chiaki↵
↵
</spoiler>↵
↵
Thank you for reading. Next round? Perhaps something more traditional, who knows? Believe me, I'll try harder if this happens.↵
↵
Cheers! \\(^ ^)/↵
↵
<hr>↵
↵
**UPD** Packages for problems are uploaded. They are in Polygon format and contain everything including statements, tests & generators, validators & checkers, and solutions. You can download them from [Google Drive](https://drive.google.com/drive/folders/0B5z87ZbXNZyEcXBtSVhWbDJEN00?usp=sharing) or [Baidu Drive](https://pan.baidu.com/s/1eSJ68gE).
