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)), I, as the author of most problems, have a feeling that lots are complaining behind the screen that problems are too tricky or hard, or are 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 hints and codes for the problems. Detailed tutorials of later problems will be available by tomorrow. Meanwhile, feel free to discuss about problems in the comments, and point out if something is incorrect. Thank you for your patience!↵
↵
### [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="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>↵
↵
↵
With the end of Codeforces Round #431 ([Div. 1](http://codeforces.me/contest/848) and [Div. 2](http://codeforces.me/contest/849)), I, as the author of most problems, have a feeling that lots are complaining behind the screen that problems are too tricky or hard, or are 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 hints and codes for the problems. Detailed tutorials of later problems will be available by tomorrow. Meanwhile, feel free to discuss about problems in the comments, and point out if something is incorrect. Thank you for your patience!↵
↵
### [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="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>↵
↵
