[tutorial:1017A]↵
↵
<spoiler summary="Solution(arsijo)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
int n;↵
cin >> n;↵
int a, b, c, d;↵
cin >> a >> b >> c >> d;↵
int S = a + b + c + d;↵
int Ans = 1;↵
for(int i = 2; i <= n; i++)↵
{↵
cin >> a >> b >> c >> d;↵
if(a + b + c + d > S)↵
{↵
Ans++;↵
}↵
}↵
printf("%d\n",Ans);↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1017B]↵
↵
<spoiler summary="Solution(arsijo)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
long long ar[4];↵
char c1[4] = {'0', '0', '1', '1'};↵
char c2[4] = {'0', '1', '0', '1'};↵
↵
int main() {↵
int n;↵
cin >> n;↵
string a, b;↵
cin >> a >> b;↵
for(int i = 0; i < n; i++){↵
for(int j = 0; j < 4; j++){↵
if(c1[j] == a[i] && c2[j] == b[i]){↵
ar[j]++;↵
}↵
}↵
}↵
cout << ar[0] * ar[2] + ar[0] * ar[3] + ar[1] * ar[2] << endl;↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1017C]↵
↵
<spoiler summary="Solution(Magolor)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 100000↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
int n, L, A[MAXN+5];↵
int main()↵
{↵
n = rf();↵
L = (int)sqrt(n);↵
for(rint i = 1, o = n, j; i <= n; i += L)↵
for(j = min(i+L-1,n); j >= i; A[j--] = o--);↵
for(rint i = 1; i <= n; i++)↵
printf("%d%c",A[i],"\n "[i<n]);↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1017D]↵
↵
<spoiler summary="Solution(Magolor)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 100000↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
int Wu[4096], f[64][64][104], g[4096][104], w[16], m, n, q, E, K, B = 6, L = 63, H = 4032; char _[16];↵
int main()↵
{↵
m = rf();↵
n = rf();↵
q = rf();↵
generate(w,w+m,rf);↵
E = 1<<m;↵
for(rint S = 0, j; S < E; S++)↵
{↵
for(j = 0; j < m; j++)↵
S&1<<j?:Wu[S]+=w[j];↵
Wu[S] = min(Wu[S],101);↵
}↵
for(rint i = 1, j, S; i <= n; i++)↵
{↵
scanf("%s",_+1);↵
for(S = 0, j = m; j; j--)↵
S = S<<1|(_[j]^'0');↵
for(j = 0; j < 64; j++)↵
++f[(S&H)>>B][j][Wu[((j^(S&L))|H)&~-E]];↵
}↵
for(rint S = 0, a, b, j; S < E; S++)↵
{↵
for(j = 0; j < 64; j++)↵
for(a = 0, b = Wu[(((j<<B)^(S&H))|L)&~-E]; b <= 100; a++, b++)↵
g[S][b] += f[j][S&L][a];↵
partial_sum(g[S],g[S]+101,g[S]);↵
}↵
for(rint i = 1, j, S; i <= q; i++)↵
{↵
scanf("%s",_+1);↵
for(S = 0, j = m; j; j--)↵
S = S<<1|(_[j]^'0');↵
printf("%d\n",g[S][rf()]);↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1017E]↵
↵
<spoiler summary="Solution(Magolor)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
//=====Computational Geometry Definitions↵
struct Vec↵
{↵
int x,y; Vec(){} Vec(int _x, int _y){x=_x,y=_y;} inline Vec operator + (Vec b){return Vec(x+b.x,y+b.y);}↵
inline Vec operator - (Vec b){return Vec(x-b.x,y-b.y);} inline Vec operator - (){return Vec(-x,-y);}↵
inline ll operator * (Vec b){return (ll)x*b.x+(ll)y*b.y;} inline ll operator % (Vec b){return (ll)x*b.y-(ll)b.x*y;}↵
inline ll operator ~ (){return (ll)x*x+(ll)y*y;} inline bool operator < (const Vec &b)const{return x^b.x?x<b.x:y<b.y;}↵
inline bool operator ==(Vec b){return x==b.x&&y==b.y;} inline bool operator !=(Vec b){return x^b.x||y^b.y;}↵
}; typedef Vec Pt; inline bool ToLeft(Vec a, Vec b){return b%a>0;} inline bool Para(Vec a, Vec b){return !(a%b);}↵
Pt LTL; inline bool cmpltl(Pt a, Pt b){a = a-LTL; b = b-LTL; return Para(a,b) ? ~a<~b : ToLeft(b,a);}↵
typedef vector<Pt> Poly; Poly A, B, C, D; typedef vector<ll> Str; Str T, S; int n, m; vector<int> nex;↵
//=====↵
void CH(Poly &A, Poly &R)↵
{↵
R.push_back(Pt());↵
LTL = *min_element(A.begin(),A.end());↵
sort(A.begin(),A.end(),cmpltl);↵
for(rint i = 0; i < (int)A.size(); i++)↵
{↵
for(; R.size()>2&&!ToLeft(A[i]-R.back(),R.back()-R[R.size()-2]); )↵
R.pop_back();↵
R.push_back(A[i]);↵
}↵
R[0] = R[R.size()-1];↵
R.push_back(R[1]);↵
}↵
void CTOS(Poly &p, Str &s)↵
{↵
s.push_back(0);↵
for(rint i = 1; i < (int)p.size()-1; i++)↵
{↵
s.push_back(~(p[i]-p[i-1]));↵
s.push_back((p[i]-p[i-1])%(p[i+1]-p[i]));↵
}↵
}↵
void CalNex()↵
{↵
nex.resize(m+1);↵
for(rint i = 2, j = 1; i <= m; i++)↵
{↵
for(; j>1&&S[i]^S[j]; )↵
j = nex[j-1]+1;↵
j += S[i]==S[j];↵
nex[i] = j-1;↵
}↵
}↵
bool KMP()↵
{↵
for(rint i = 1, j = 1; i <= n; i++)↵
{↵
for(; j>1&&(j>m||T[i]^S[j]); )↵
j = nex[j-1]+1;↵
j+=T[i]==S[j]; ↵
if(j>m)↵
return true;↵
}↵
return false;↵
}↵
int main()↵
{↵
A.resize(rf()); B.resize(rf());↵
for(rint i = 0, s = (int)A.size(); i < s; i++)↵
A[i].x = rf(), A[i].y = rf();↵
CH(A,C);↵
CTOS(C,T);↵
n = T.size()-1;↵
for(rint i = 0, s = (int)B.size(); i < s; i++)↵
B[i].x = rf(), B[i].y = rf();↵
CH(B,D);↵
CTOS(D,S);↵
m = S.size()-1;↵
for(rint i = 1, s = (int)T.size(); i < s; i++)↵
T.push_back(T[i]);↵
n <<= 1;↵
CalNex();↵
puts(KMP()?"YES":"NO");↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution(Kostroma)">↵
↵
~~~~~↵
↵
#pragma comment(linker, "/STACK:512000000")↵
#define _CRT_SECURE_NO_WARNINGS↵
//#include "testlib.h"↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define all(a) a.begin(), a.end()↵
using li = long long;↵
using ld = long double;↵
void solve(bool);↵
void precalc();↵
clock_t start;↵
int main() {↵
#ifdef AIM↵
freopen("/home/alexandero/CLionProjects/ACM/input.txt", "r", stdin);↵
//freopen("/home/alexandero/CLionProjects/ACM/output.txt", "w", stdout);↵
//freopen("out.txt", "w", stdout);↵
#else↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
#endif↵
start = clock();↵
int t = 1;↵
#ifndef AIM↵
cout.sync_with_stdio(0);↵
cin.tie(0);↵
#endif↵
cout.precision(20);↵
cout << fixed;↵
//cin >> t;↵
precalc();↵
while (t--) {↵
solve(true);↵
}↵
cout.flush();↵
↵
#ifdef AIM1↵
while (true) {↵
solve(false);↵
}↵
#endif↵
↵
#ifdef AIM↵
cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";↵
#endif↵
return 0;↵
}↵
↵
//BE CAREFUL: IS INT REALLY INT?↵
↵
template<typename T>↵
T binpow(T q, T w, T mod) {↵
if (!w)↵
return 1 % mod;↵
if (w & 1)↵
return q * 1LL * binpow(q, w - 1, mod) % mod;↵
return binpow(q * 1LL * q % mod, w / 2, mod);↵
}↵
↵
template<typename T>↵
T gcd(T q, T w) {↵
while (w) {↵
q %= w;↵
swap(q, w);↵
}↵
return q;↵
}↵
template<typename T>↵
T lcm(T q, T w) {↵
return q / gcd(q, w) * w;↵
}↵
↵
template <typename T>↵
void make_unique(vector<T>& vec) {↵
sort(all(vec));↵
vec.erase(unique(all(vec)), vec.end());↵
}↵
↵
template<typename T>↵
void relax_min(T& cur, T val) {↵
cur = min(cur, val);↵
}↵
↵
template<typename T>↵
void relax_max(T& cur, T val) {↵
cur = max(cur, val);↵
}↵
↵
void precalc() {↵
↵
}↵
↵
#define int li↵
//const li mod = 1000000007;↵
//using ull = unsigned long long;↵
↵
struct Point {↵
int x, y;↵
Point() {}↵
Point(int x, int y) : x(x), y(y) {}↵
Point operator - (const Point& ot) const {↵
return Point(x - ot.x, y - ot.y);↵
}↵
int operator * (const Point& ot) const {↵
return x * ot.y - y * ot.x;↵
}↵
void scan() {↵
cin >> x >> y;↵
}↵
bool operator < (const Point& ot) const {↵
return make_pair(x, y) < make_pair(ot.x, ot.y);↵
}↵
int sqr_len() const {↵
return x * x + y * y;↵
}↵
long double get_len() const {↵
return sqrtl(sqr_len());↵
}↵
int operator % (const Point& ot) const {↵
return x * ot.x + y * ot.y;↵
}↵
};↵
↵
struct Polygon {↵
vector<Point> hull;↵
Polygon(int n) {↵
vector<Point> points(n);↵
for (int i = 0; i < n; ++i) {↵
points[i].scan();↵
}↵
sort(all(points));↵
vector<Point> up, down;↵
for (auto& pt : points) {↵
while (up.size() > 1 && (up[up.size() - 2] - up.back()) * (pt - up.back()) >= 0) {↵
up.pop_back();↵
}↵
up.push_back(pt);↵
while (down.size() > 1 && (down[down.size() - 2] - down.back()) * (pt - down.back()) <= 0) {↵
down.pop_back();↵
}↵
down.push_back(pt);↵
}↵
hull = up;↵
for (int i = (int)down.size() - 2; i > 0; --i) {↵
hull.push_back(down[i]);↵
}↵
}↵
int sqr_len(int pos) const {↵
return (hull[(pos + 1) % hull.size()] - hull[pos]).sqr_len();↵
}↵
int size() const {↵
return (int)hull.size();↵
}↵
long double get_angle(int pos) const {↵
auto a = hull[(pos + 1) % hull.size()] - hull[pos], b = hull[(pos + hull.size() - 1) % hull.size()] - hull[pos];↵
long double co = (a % b) / a.get_len() / b.get_len();↵
return co;↵
}↵
};↵
↵
void solve(bool read) {↵
vector<Polygon> polys;↵
int n[2];↵
cin >> n[0] >> n[1];↵
for (int i = 0; i < 2; ++i) {↵
polys.emplace_back(n[i]);↵
}↵
if (polys[0].size() != polys[1].size()) {↵
cout << "NO\n";↵
return;↵
}↵
vector<long double> all_lens;↵
int m = polys[0].size();↵
for (int i = 0; i < m; ++i) {↵
all_lens.push_back(polys[0].sqr_len(i));↵
all_lens.push_back(polys[0].get_angle(i));↵
}↵
all_lens.push_back(-1);↵
for (int j = 0; j < 2; ++j) {↵
for (int i = 0; i < m; ++i) {↵
all_lens.push_back(polys[1].sqr_len(i));↵
all_lens.push_back(polys[1].get_angle(i));↵
}↵
}↵
/*for (int x : all_lens) {↵
cout << x << " ";↵
}↵
cout << "\n";*/↵
vector<int> p(all_lens.size());↵
for (int i = 1; i < p.size(); ++i) {↵
int j = p[i - 1];↵
while (j > 0 && all_lens[i] != all_lens[j]) {↵
j = p[j - 1];↵
}↵
if (all_lens[i] == all_lens[j]) {↵
++j;↵
}↵
p[i] = j;↵
if (p[i] == 2 * m) {↵
cout << "YES\n";↵
return;↵
}↵
}↵
cout << "NO\n";↵
↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1017F]↵
↵
<spoiler summary="Solution(Magolor,optimized by arsijo)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define uint unsigned int↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
bitset<100000032> _b; int n; uint A, B, C, D, Ans;↵
inline uint f(int p){↵
return((A*p+B)*p+C)*p+D;↵
}↵
inline int cnt(int p, int n){↵
int r=0;↵
for(;n/=p;r+=n);↵
return r;↵
}↵
inline auto b(int i)->decltype(_b[0]){↵
return _b[(i&1)&&(i%6!=3)?i/6<<1|((i%6)>1):0];↵
}↵
inline auto b2(int i)->decltype(_b[0]){↵
return _b[i/6<<1|1];↵
}↵
inline auto b3(int i)->decltype(_b[0]){↵
return _b[i/6<<1];↵
}↵
↵
int main()↵
{↵
n = rf();↵
A = rf();↵
B = rf();↵
C = rf();↵
D = rf();↵
_b[0] = 1;↵
Ans = cnt(2,n)*f(2)+cnt(3,n)*f(3);↵
for(rint i = 5, j, z, c, w; i <= n; i += 4){↵
if(!b2(i))↵
{↵
Ans += cnt(i,n)*f(i);↵
if(i <= 20000){↵
w = i + i;↵
c = w % 6;↵
z = (i * i) % 6;↵
if(c == 0){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w){↵
b3(j) = 1;↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w){↵
b2(j) = 1;↵
}↵
}↵
}else if(c == 2){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w){↵
b3(j) = 1;↵
j += w + w;↵
if(j <= n){↵
b2(j) = 1;↵
}↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w + w){↵
b2(j) = 1;↵
j += w;↵
if(j <= n){↵
b3(j) = 1;↵
}↵
}↵
}↵
}else if(c == 4){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w + w){↵
b3(j) = 1;↵
j += w;↵
if(j <= n){↵
b2(j) = 1;↵
}↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w){↵
b2(j) = 1;↵
j += w + w;↵
if(j <= n){↵
b3(j) = 1;↵
}↵
}↵
}↵
}↵
}↵
}↵
i += 2;↵
if(i <= n && !b3(i))↵
{↵
Ans += cnt(i,n)*f(i);↵
if(i <= 20000){↵
w = i + i;↵
c = w % 6;↵
z = (i * i) % 6;↵
if(c == 0){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w){↵
b3(j) = 1;↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w){↵
b2(j) = 1;↵
}↵
}↵
}else if(c == 2){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w){↵
b3(j) = 1;↵
j += w + w;↵
if(j <= n){↵
b2(j) = 1;↵
}↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w + w){↵
b2(j) = 1;↵
j += w;↵
if(j <= n){↵
b3(j) = 1;↵
}↵
}↵
}↵
}else if(c == 4){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w + w){↵
b3(j) = 1;↵
j += w;↵
if(j <= n){↵
b2(j) = 1;↵
}↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w){↵
b2(j) = 1;↵
j += w + w;↵
if(j <= n){↵
b3(j) = 1;↵
}↵
}↵
}↵
}↵
}↵
}↵
}↵
printf("%u\n",Ans);↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution(000000)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
typedef unsigned int ll;↵
const ll maxn=4e8;↵
const ll maxp=sqrt(maxn)+10;↵
ll f[4][maxp],g[4][maxp];↵
ll n,m,A,B,C,D,ans,res,tmp,rt;↵
↵
ll p1(ll x){↵
ll y=x+1; if (x%2==0) x/=2; else y/=2;↵
return x*y;↵
}↵
ll p2(ll x){↵
long long y=x+1,z=x*2+1;↵
if (x%2==0) x/=2; else y/=2;↵
if (z%3==0) z/=3; else if (x%3==0) x/=3; else y/=3;↵
return (ll)x*y*z;↵
}↵
ll p3(ll x){↵
ll y=p1(x);↵
return y*y;↵
}↵
bool is_prime(ll x){↵
for (ll i=2;i*i<=x;i++) if (x%i==0) return false;↵
return true;↵
}↵
↵
ll solve(ll n)↵
{↵
ll i,j,rt,o[4];↵
for (m=1;m*m<=n;m++) {↵
f[0][m]=(n/m-1);↵
f[1][m]=(p1(n/m)-1)*C;↵
f[2][m]=(p2(n/m)-1)*B;↵
f[3][m]=(p3(n/m)-1)*A;↵
}↵
for (i=1;i<=m;i++) {↵
g[0][i]=(i-1);↵
g[1][i]=(p1(i)-1)*C;↵
g[2][i]=(p2(i)-1)*B;↵
g[3][i]=(p3(i)-1)*A;↵
}↵
for (i=2;i<=m;i++) {↵
if (g[0][i]==g[0][i-1]) continue;↵
o[0]=1; for (int w=1;w<4;w++) o[w]=o[w-1]*i;↵
for (j=1;j<=min(m-1,n/i/i);j++)↵
for (int w=0;w<4;w++)↵
if (i*j<m) f[w][j]-=o[w]*(f[w][i*j]-g[w][i-1]);↵
else f[w][j]-=o[w]*(g[w][n/i/j]-g[w][i-1]);↵
for (j=m;j>=i*i;j--)↵
for (int w=0;w<4;w++)↵
g[w][j]-=o[w]*(g[w][j/i]-g[w][i-1]);↵
}↵
for (int i=1;i<=m+1;i++) f[0][i]*=D,g[0][i]*=D;↵
rt=0;↵
for (ll i=1;n/i>m;i++) {↵
for (int w=0;w<4;w++) rt+=(f[w][i]-g[w][m]);↵
//cout<<"H"<<rt<<endl;↵
}↵
return rt;↵
}↵
↵
int main()↵
{↵
//freopen("input.txt","r",stdin);↵
ll n; cin >> n >> A >> B >> C >> D;↵
ans=solve(n);↵
for (ll i=2;i<=m;i++){↵
if (is_prime(i)){↵
res=A*i*i*i+B*i*i+C*i+D; tmp=n;↵
while (tmp){↵
ans+=res*(tmp/i);↵
tmp/=i;↵
}↵
}↵
}↵
cout << ans << endl;↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1017G]↵
↵
<spoiler summary="Solution(arsijo)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MAX = 1e5 + 10;↵
↵
bool black[MAX]; // is it vertex black now↵
vector<int> vec[MAX]; // main edges↵
bool old_black[MAX]; // to remember the tree before block↵
↵
const int MAX_BLOCK_SIZE = 600;↵
↵
int t[MAX], v[MAX]; // queries↵
↵
bool used[MAX]; // is in mini-tree↵
vector<pair<pair<int, int>, int> > v2[MAX]; // mini-tree edges (son, number of white vertices, dist)↵
int push[MAX]; // push of the i-th vertex in mini-tree↵
bool clear[MAX]; // do we need to clear first↵
↵
void dfs_1(int pos, int prev = -1, int white = 0, int dist = 0){↵
if(used[pos]){↵
if(prev != -1){↵
v2[prev].push_back(make_pair(make_pair(pos, white), dist));↵
}↵
for(int a : vec[pos]){↵
dfs_1(a, pos, 0, 0);↵
}↵
}else{↵
if(!black[pos]){↵
white++;↵
}↵
for(int a : vec[pos]){↵
dfs_1(a, prev, white, dist + 1);↵
}↵
}↵
}↵
↵
void make_1(int pos){↵
if(!black[pos]){↵
black[pos] = true;↵
return;↵
}↵
push[pos]++;↵
for(auto a : v2[pos]){↵
if(a.first.second + 1 <= push[pos]){↵
make_1(a.first.first);↵
}↵
}↵
}↵
↵
void make_2(int pos){↵
black[pos] = false;↵
push[pos] = 0;↵
clear[pos] = true;↵
for(auto &a : v2[pos]){↵
a.first.second = a.second;↵
make_2(a.first.first);↵
}↵
}↵
↵
void dfs_2(int pos, int p = 0, bool cl = false){↵
if(used[pos]){↵
p = push[pos];↵
cl |= clear[pos];↵
}else{↵
black[pos] = old_black[pos];↵
if(cl){↵
black[pos] = false;↵
}↵
if(!black[pos] && p){↵
black[pos] = true;↵
p--;↵
}↵
}↵
for(int a : vec[pos]){↵
dfs_2(a, p, cl);↵
}↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio();↵
cin.tie(0);↵
cout.tie(0);↵
int n, q;↵
cin >> n >> q;↵
for(int i = 2; i <= n; i++){↵
int a;↵
cin >> a;↵
vec[a].push_back(i);↵
}↵
for(int i = 1; i <= q; i++){↵
cin >> t[i] >> v[i];↵
}↵
int root = 1;↵
for(int i = 1; i <= q; i += MAX_BLOCK_SIZE){↵
for(int j = 1; j <= n; j++){↵
used[j] = false;↵
v2[j].clear();↵
old_black[j] = black[j];↵
push[j] = 0;↵
clear[j] = false;↵
}↵
for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){↵
used[v[i + j]] = true;↵
}↵
dfs_1(root);↵
for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){↵
int t = ::t[i + j];↵
int v = ::v[i + j];↵
if(t == 1){↵
make_1(v);↵
}else if(t == 2){↵
make_2(v);↵
}else{↵
cout << (black[v] ? "black" : "white") << "\n";↵
}↵
}↵
dfs_2(root);↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1017H]↵
↵
<spoiler summary="Solution(Magolor)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 200000↵
#define MOD 998244353↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
int n, m, q, B, C, T, fac[MAXN+5], efac[MAXN+5], Ans[MAXN+5], A[MAXN+5], t[MAXN+5], c[MAXN+5];↵
int mp[MAXN+5], rv[480], h[480][100032], _init[MAXN+5], d[105][100032]; bitset<100032> b[480];↵
typedef pair<int,int> pii; pii S[MAXN+5]; struct QU{int u,l,r,k,i;}Q[MAXN+5];↵
inline bool cmpi(const QU &a, const QU &b)↵
{↵
return a.i<b.i;↵
}↵
inline bool cmpm(const QU &a, const QU &b)↵
{↵
return a.u^b.u?a.u<b.u:a.u&1?a.r<b.r:a.r>b.r;↵
}↵
//fastpow↵
inline int fxp(int s, int n=MOD-2){int a=1;for(;n;n&1?a=1ll*a*s%MOD:0,s=1ll*s*s%MOD,n>>=1);return a;}↵
inline void Init(int k)↵
{↵
if(_init[k]) return;↵
_init[k] = ++C;↵
int *D = d[C], s = 1ll*m*k%MOD;↵
D[0] = 1;↵
for(rint i = 1; i <= n; i++)↵
D[i] = 1ll*D[i-1]*(s+i)%MOD;↵
}↵
inline int dxp(int a, int b)↵
{↵
return 1ll*fac[a]*efac[a-b]%MOD;↵
}↵
inline int DXP(int k, int l)↵
{↵
return d[_init[k]][l]; ↵
}↵
void insert(int x)↵
{↵
--h[t[x]][c[x]++];↵
++h[t[x]][c[x]];↵
S[++T] = pii(t[x],c[x]);↵
}↵
void erase(int x)↵
{↵
--h[t[x]][c[x]--];↵
++h[t[x]][c[x]];↵
S[++T] = pii(t[x],c[x]);↵
}↵
inline int calc(int k)↵
{↵
int _ = T; T = 0;↵
for(rint i = 1; i <= _; i++)↵
if(!b[S[i].first][S[i].second]&&h[S[i].first][S[i].second])↵
S[++T] = S[i], b[S[i].first][S[i].second] = 1;↵
int Ans = 1;↵
for(rint i = 1; i <= T; i++)↵
{↵
b[S[i].first][S[i].second] = 0;↵
Ans = 1ll*Ans*fxp(dxp(rv[S[i].first]+k,S[i].second),h[S[i].first][S[i].second])%MOD;↵
}↵
return Ans;↵
}↵
int main()↵
{↵
n = MAXN;↵
for(rint i = fac[0] = 1; i <= n; i++)↵
fac[i] = 1ll*i*fac[i-1]%MOD;↵
efac[n] = fxp(fac[n]);↵
for(rint i = n; i; i--)↵
efac[i-1] = 1ll*i*efac[i]%MOD;↵
n = rf();↵
m = rf();↵
q = rf();↵
B = n/sqrt(q*2/3)+1;↵
for(rint i = 1; i <= n; i++)↵
++t[A[i]=rf()];↵
for(rint i = 1, c = 0; i <= n; i++)↵
mp[t[A[i]]]?:rv[mp[t[A[i]]]=++c]=t[A[i]];↵
for(rint i = 1; i <= m; i++)↵
t[i] = mp[t[i]];↵
for(rint i = 1, l, r, k; i <= q; i++)↵
{↵
l = rf();↵
r = rf();↵
k = rf();↵
Init(k);↵
Q[i] = {~-l/B,l,r,k,i};↵
}↵
sort(Q+1,Q+q+1,cmpm);↵
for(rint i = 1; i <= n; i++)↵
++h[t[A[i]]][0];↵
for(rint i = 1, l = 1, r = 0; i <= q; i++)↵
{↵
for(; l > Q[i].l; insert(A[--l]));↵
for(; r < Q[i].r; insert(A[++r]));↵
for(; l < Q[i].l; erase(A[l++]));↵
for(; r > Q[i].r; erase(A[r--]));↵
Ans[Q[i].i] = calc(Q[i].k);↵
}↵
sort(Q+1,Q+q+1,cmpi);↵
for(rint i = 1; i <= q; i++)↵
printf("%d\n",1ll*DXP(Q[i].k,n-(Q[i].r-Q[i].l+1))*Ans[i]%MOD);↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution(Kostroma)">↵
↵
~~~~~↵
↵
#pragma comment(linker, "/STACK:512000000")↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define all(a) a.begin(), a.end()↵
typedef long long li;↵
typedef long double ld;↵
void solve(__attribute__((unused)) bool);↵
void precalc();↵
clock_t start;↵
#define FILENAME ""↵
↵
int main() {↵
#ifdef AIM↵
string s = FILENAME;↵
// assert(!s.empty());↵
freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);↵
//freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout);↵
#else↵
// freopen(FILENAME ".in", "r", stdin);↵
// freopen(FILENAME ".out", "w", stdout);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
#endif↵
start = clock();↵
int t = 1;↵
#ifndef AIM↵
cout.sync_with_stdio(0);↵
cin.tie(0);↵
#endif↵
precalc();↵
cout.precision(10);↵
cout << fixed;↵
//cin >> t;↵
int testNum = 1;↵
while (t--) {↵
//cout << "Case #" << testNum++ << ": ";↵
solve(true);↵
}↵
cout.flush();↵
#ifdef AIM1↵
while (true) {↵
solve(false);↵
}↵
#endif↵
↵
#ifdef AIM↵
cout.flush();↵
auto end = clock();↵
↵
usleep(10000);↵
print_stats(end - start);↵
usleep(10000);↵
#endif↵
↵
return 0;↵
}↵
↵
template<typename T>↵
T binpow(T q, T w, T mod) {↵
if (!w)↵
return 1 % mod;↵
if (w & 1)↵
return q * 1LL * binpow(q, w - 1, mod) % mod;↵
return binpow(q * 1LL * q % mod, w / 2, mod);↵
}↵
↵
template<typename T>↵
T gcd(T q, T w) {↵
while (w) {↵
q %= w;↵
swap(q, w);↵
}↵
return q;↵
}↵
template<typename T>↵
T lcm(T q, T w) {↵
return q / gcd(q, w) * w;↵
}↵
↵
template <typename T>↵
void make_unique(vector<T>& a) {↵
sort(all(a));↵
a.erase(unique(all(a)), a.end());↵
}↵
↵
template<typename T>↵
void relax_min(T& cur, T val) {↵
cur = min(cur, val);↵
}↵
↵
template<typename T>↵
void relax_max(T& cur, T val) {↵
cur = max(cur, val);↵
}↵
↵
void precalc() {↵
}↵
↵
#define int li↵
const int mod = 998244353;↵
↵
struct Query {↵
int l, r, id;↵
};↵
↵
vector<int> res;↵
vector<int> a;↵
int n;↵
↵
int TIMER = 0;↵
const int C = 200500;↵
int used[C];↵
int cur_cnt[C];↵
int rev[C];↵
map<int, vector<int>> down;↵
vector<int> init;↵
↵
void kill(vector<Query>& all_q, int block_size, int k) {↵
vector<vector<Query>> by_block(n / block_size + 1);↵
for (auto& cur_q : all_q) {↵
by_block[cur_q.l / block_size].push_back(cur_q);↵
}↵
for (int i = 0; i < by_block.size(); ++i) {↵
++TIMER;↵
auto& q = by_block[i];↵
sort(all(q), [&] (const Query& o1, const Query& o2) {↵
return o1.r < o2.r;↵
});↵
int cur_l = min(n, (i + 1) * block_size);↵
int cur_r = cur_l;↵
int cur_prod = 1;↵
↵
auto add_item = [&] (int val) {↵
if (used[val] != TIMER) {↵
used[val] = TIMER;↵
cur_cnt[val] = 0;↵
}↵
int cur_k = k + init[val];↵
++cur_cnt[val];↵
cur_prod = cur_prod * (cur_k - cur_cnt[val] + 1) % mod;↵
};↵
auto remove_item = [&] (int val) {↵
int cur_k = k + init[val];↵
cur_prod = cur_prod * rev[cur_k - cur_cnt[val] + 1] % mod;↵
--cur_cnt[val];↵
};↵
↵
for (auto& cur_q : q) {↵
while (cur_r < cur_q.r) {↵
add_item(a[cur_r++]);↵
}↵
while (cur_l > cur_q.l) {↵
add_item(a[--cur_l]);↵
}↵
while (cur_r > cur_q.r) {↵
remove_item(a[--cur_r]);↵
}↵
while (cur_l < cur_q.l) {↵
remove_item(a[cur_l++]);↵
}↵
res[cur_q.id] = cur_prod * down[k][n - cur_q.r + cur_q.l] % mod;↵
}↵
}↵
}↵
↵
void solve(__attribute__((unused)) bool read) {↵
for (int i = 1; i < C; ++i) {↵
rev[i] = binpow(i, mod - 2, mod);↵
}↵
int m, Q;↵
//read = false;↵
if (read) {↵
cin >> n >> m >> Q;↵
} else {↵
n = 50000;↵
m = 100000;↵
Q = 50000;↵
}↵
a.resize(n);↵
init.assign(m, 0);↵
for (int i = 0; i < n; ++i) {↵
if (read) {↵
cin >> a[i];↵
--a[i];↵
} else {↵
a[i] = rand() % m;↵
}↵
++init[a[i]];↵
}↵
map<int, vector<Query>> q;↵
for (int i = 0; i < Q; ++i) {↵
int l, r, k;↵
if (read) {↵
cin >> l >> r >> k;↵
} else {↵
do {↵
l = rand() % n + 1;↵
r = rand() % n + 1;↵
} while (l > r);↵
k = rand() % 100;↵
}↵
--l;↵
q[k].push_back({l, r, i});↵
down[k] = vector<int>();↵
}↵
res.assign(Q, 0);↵
for (auto& item : down) {↵
int init_val = (item.first * m) % mod;↵
auto& vec = item.second;↵
vec.assign(n + 1, 1);↵
for (int i = 1; i < vec.size(); ++i) {↵
vec[i] = vec[i - 1] * (init_val + i) % mod;↵
}↵
}↵
for (auto& item : q) {↵
int k = item.first;↵
auto& cur_q = item.second;↵
int block_size = std::max((int)(n / sqrt((int)cur_q.size())), 1LL);↵
kill(cur_q, block_size, k);↵
}↵
↵
for (int i = 0; i < Q; ++i) {↵
cout << res[i] << "\n";↵
}↵
↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### Bonus Problem↵
It is the previous D1E and its standard solution is hacked. Can you solve it?↵
↵
<spoiler summary="Bonus problem">↵
↵
**Legend**↵
↵
How can the man in the high castle, Abendsen, escape so many times? Because he has a full plan of escaping —— with his films.↵
↵
The map of the cities can be described as a tree (i.e. connected graph with $n$ vertices and $n-1$ edges) rooted at node $1$ —— where Abenden lives.↵
↵
When he starts his escaping, he plans **at most** $k$ travels: one travel is a simple path between two (not necessarily different) vertices. So he goes from $1$ to some vertex $v_1$, and then goes from $v_1$ to $v_2$, and so on $\ldots$↵
↵
When he is visiting a vertex (even though he has visited this vertex before) he will get some films. But in some vertexes, he has to give some films. Note that Abendsen \textbf{can} have a negative amount of films. But after every travel, he **has to have a non-negative amount of films**. Note that when Abendsen is starting a new travel, **he is visiting the starting vertex too**. It sounds weird but it is a different world!↵
↵
At first, Abendsen does not have any films.↵
↵
He wants to maximize the number of the films he gets after the escape. So please help him find out the maximized films number he can get.↵
↵
**Input Format**↵
↵
The first line two contains two integers $n$ and $k$ ($1 \le n \le 1000$, $1 \le k \le 10^6$) —— the number of vertices and the maximum number of travels allowed.↵
↵
The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($|w_i|\leq 10^8$) —— how many films will Abendsen get (or give if $w_i$ is negative) if he visits the $i$-th vertex.↵
↵
Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$ ($1\leq u_i, v_i\leq n$, $u_i\neq v_i$) —— vertices connected by the $i$-th edge.↵
↵
It is guaranteed that the input data describes a correct tree.↵
↵
**Output Format**↵
↵
Print one integer, the maximum number of films he can get.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution(arsijo)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main()↵
{↵
int n;↵
cin >> n;↵
int a, b, c, d;↵
cin >> a >> b >> c >> d;↵
int S = a + b + c + d;↵
int Ans = 1;↵
for(int i = 2; i <= n; i++)↵
{↵
cin >> a >> b >> c >> d;↵
if(a + b + c + d > S)↵
{↵
Ans++;↵
}↵
}↵
printf("%d\n",Ans);↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1017B]↵
↵
<spoiler summary="Solution(arsijo)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
long long ar[4];↵
char c1[4] = {'0', '0', '1', '1'};↵
char c2[4] = {'0', '1', '0', '1'};↵
↵
int main() {↵
int n;↵
cin >> n;↵
string a, b;↵
cin >> a >> b;↵
for(int i = 0; i < n; i++){↵
for(int j = 0; j < 4; j++){↵
if(c1[j] == a[i] && c2[j] == b[i]){↵
ar[j]++;↵
}↵
}↵
}↵
cout << ar[0] * ar[2] + ar[0] * ar[3] + ar[1] * ar[2] << endl;↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1017C]↵
↵
<spoiler summary="Solution(Magolor)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 100000↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
int n, L, A[MAXN+5];↵
int main()↵
{↵
n = rf();↵
L = (int)sqrt(n);↵
for(rint i = 1, o = n, j; i <= n; i += L)↵
for(j = min(i+L-1,n); j >= i; A[j--] = o--);↵
for(rint i = 1; i <= n; i++)↵
printf("%d%c",A[i],"\n "[i<n]);↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1017D]↵
↵
<spoiler summary="Solution(Magolor)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 100000↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
int Wu[4096], f[64][64][104], g[4096][104], w[16], m, n, q, E, K, B = 6, L = 63, H = 4032; char _[16];↵
int main()↵
{↵
m = rf();↵
n = rf();↵
q = rf();↵
generate(w,w+m,rf);↵
E = 1<<m;↵
for(rint S = 0, j; S < E; S++)↵
{↵
for(j = 0; j < m; j++)↵
S&1<<j?:Wu[S]+=w[j];↵
Wu[S] = min(Wu[S],101);↵
}↵
for(rint i = 1, j, S; i <= n; i++)↵
{↵
scanf("%s",_+1);↵
for(S = 0, j = m; j; j--)↵
S = S<<1|(_[j]^'0');↵
for(j = 0; j < 64; j++)↵
++f[(S&H)>>B][j][Wu[((j^(S&L))|H)&~-E]];↵
}↵
for(rint S = 0, a, b, j; S < E; S++)↵
{↵
for(j = 0; j < 64; j++)↵
for(a = 0, b = Wu[(((j<<B)^(S&H))|L)&~-E]; b <= 100; a++, b++)↵
g[S][b] += f[j][S&L][a];↵
partial_sum(g[S],g[S]+101,g[S]);↵
}↵
for(rint i = 1, j, S; i <= q; i++)↵
{↵
scanf("%s",_+1);↵
for(S = 0, j = m; j; j--)↵
S = S<<1|(_[j]^'0');↵
printf("%d\n",g[S][rf()]);↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1017E]↵
↵
<spoiler summary="Solution(Magolor)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
//=====Computational Geometry Definitions↵
struct Vec↵
{↵
int x,y; Vec(){} Vec(int _x, int _y){x=_x,y=_y;} inline Vec operator + (Vec b){return Vec(x+b.x,y+b.y);}↵
inline Vec operator - (Vec b){return Vec(x-b.x,y-b.y);} inline Vec operator - (){return Vec(-x,-y);}↵
inline ll operator * (Vec b){return (ll)x*b.x+(ll)y*b.y;} inline ll operator % (Vec b){return (ll)x*b.y-(ll)b.x*y;}↵
inline ll operator ~ (){return (ll)x*x+(ll)y*y;} inline bool operator < (const Vec &b)const{return x^b.x?x<b.x:y<b.y;}↵
inline bool operator ==(Vec b){return x==b.x&&y==b.y;} inline bool operator !=(Vec b){return x^b.x||y^b.y;}↵
}; typedef Vec Pt; inline bool ToLeft(Vec a, Vec b){return b%a>0;} inline bool Para(Vec a, Vec b){return !(a%b);}↵
Pt LTL; inline bool cmpltl(Pt a, Pt b){a = a-LTL; b = b-LTL; return Para(a,b) ? ~a<~b : ToLeft(b,a);}↵
typedef vector<Pt> Poly; Poly A, B, C, D; typedef vector<ll> Str; Str T, S; int n, m; vector<int> nex;↵
//=====↵
void CH(Poly &A, Poly &R)↵
{↵
R.push_back(Pt());↵
LTL = *min_element(A.begin(),A.end());↵
sort(A.begin(),A.end(),cmpltl);↵
for(rint i = 0; i < (int)A.size(); i++)↵
{↵
for(; R.size()>2&&!ToLeft(A[i]-R.back(),R.back()-R[R.size()-2]); )↵
R.pop_back();↵
R.push_back(A[i]);↵
}↵
R[0] = R[R.size()-1];↵
R.push_back(R[1]);↵
}↵
void CTOS(Poly &p, Str &s)↵
{↵
s.push_back(0);↵
for(rint i = 1; i < (int)p.size()-1; i++)↵
{↵
s.push_back(~(p[i]-p[i-1]));↵
s.push_back((p[i]-p[i-1])%(p[i+1]-p[i]));↵
}↵
}↵
void CalNex()↵
{↵
nex.resize(m+1);↵
for(rint i = 2, j = 1; i <= m; i++)↵
{↵
for(; j>1&&S[i]^S[j]; )↵
j = nex[j-1]+1;↵
j += S[i]==S[j];↵
nex[i] = j-1;↵
}↵
}↵
bool KMP()↵
{↵
for(rint i = 1, j = 1; i <= n; i++)↵
{↵
for(; j>1&&(j>m||T[i]^S[j]); )↵
j = nex[j-1]+1;↵
j+=T[i]==S[j]; ↵
if(j>m)↵
return true;↵
}↵
return false;↵
}↵
int main()↵
{↵
A.resize(rf()); B.resize(rf());↵
for(rint i = 0, s = (int)A.size(); i < s; i++)↵
A[i].x = rf(), A[i].y = rf();↵
CH(A,C);↵
CTOS(C,T);↵
n = T.size()-1;↵
for(rint i = 0, s = (int)B.size(); i < s; i++)↵
B[i].x = rf(), B[i].y = rf();↵
CH(B,D);↵
CTOS(D,S);↵
m = S.size()-1;↵
for(rint i = 1, s = (int)T.size(); i < s; i++)↵
T.push_back(T[i]);↵
n <<= 1;↵
CalNex();↵
puts(KMP()?"YES":"NO");↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution(Kostroma)">↵
↵
~~~~~↵
↵
#pragma comment(linker, "/STACK:512000000")↵
#define _CRT_SECURE_NO_WARNINGS↵
//#include "testlib.h"↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define all(a) a.begin(), a.end()↵
using li = long long;↵
using ld = long double;↵
void solve(bool);↵
void precalc();↵
clock_t start;↵
int main() {↵
#ifdef AIM↵
freopen("/home/alexandero/CLionProjects/ACM/input.txt", "r", stdin);↵
//freopen("/home/alexandero/CLionProjects/ACM/output.txt", "w", stdout);↵
//freopen("out.txt", "w", stdout);↵
#else↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
#endif↵
start = clock();↵
int t = 1;↵
#ifndef AIM↵
cout.sync_with_stdio(0);↵
cin.tie(0);↵
#endif↵
cout.precision(20);↵
cout << fixed;↵
//cin >> t;↵
precalc();↵
while (t--) {↵
solve(true);↵
}↵
cout.flush();↵
↵
#ifdef AIM1↵
while (true) {↵
solve(false);↵
}↵
#endif↵
↵
#ifdef AIM↵
cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";↵
#endif↵
return 0;↵
}↵
↵
//BE CAREFUL: IS INT REALLY INT?↵
↵
template<typename T>↵
T binpow(T q, T w, T mod) {↵
if (!w)↵
return 1 % mod;↵
if (w & 1)↵
return q * 1LL * binpow(q, w - 1, mod) % mod;↵
return binpow(q * 1LL * q % mod, w / 2, mod);↵
}↵
↵
template<typename T>↵
T gcd(T q, T w) {↵
while (w) {↵
q %= w;↵
swap(q, w);↵
}↵
return q;↵
}↵
template<typename T>↵
T lcm(T q, T w) {↵
return q / gcd(q, w) * w;↵
}↵
↵
template <typename T>↵
void make_unique(vector<T>& vec) {↵
sort(all(vec));↵
vec.erase(unique(all(vec)), vec.end());↵
}↵
↵
template<typename T>↵
void relax_min(T& cur, T val) {↵
cur = min(cur, val);↵
}↵
↵
template<typename T>↵
void relax_max(T& cur, T val) {↵
cur = max(cur, val);↵
}↵
↵
void precalc() {↵
↵
}↵
↵
#define int li↵
//const li mod = 1000000007;↵
//using ull = unsigned long long;↵
↵
struct Point {↵
int x, y;↵
Point() {}↵
Point(int x, int y) : x(x), y(y) {}↵
Point operator - (const Point& ot) const {↵
return Point(x - ot.x, y - ot.y);↵
}↵
int operator * (const Point& ot) const {↵
return x * ot.y - y * ot.x;↵
}↵
void scan() {↵
cin >> x >> y;↵
}↵
bool operator < (const Point& ot) const {↵
return make_pair(x, y) < make_pair(ot.x, ot.y);↵
}↵
int sqr_len() const {↵
return x * x + y * y;↵
}↵
long double get_len() const {↵
return sqrtl(sqr_len());↵
}↵
int operator % (const Point& ot) const {↵
return x * ot.x + y * ot.y;↵
}↵
};↵
↵
struct Polygon {↵
vector<Point> hull;↵
Polygon(int n) {↵
vector<Point> points(n);↵
for (int i = 0; i < n; ++i) {↵
points[i].scan();↵
}↵
sort(all(points));↵
vector<Point> up, down;↵
for (auto& pt : points) {↵
while (up.size() > 1 && (up[up.size() - 2] - up.back()) * (pt - up.back()) >= 0) {↵
up.pop_back();↵
}↵
up.push_back(pt);↵
while (down.size() > 1 && (down[down.size() - 2] - down.back()) * (pt - down.back()) <= 0) {↵
down.pop_back();↵
}↵
down.push_back(pt);↵
}↵
hull = up;↵
for (int i = (int)down.size() - 2; i > 0; --i) {↵
hull.push_back(down[i]);↵
}↵
}↵
int sqr_len(int pos) const {↵
return (hull[(pos + 1) % hull.size()] - hull[pos]).sqr_len();↵
}↵
int size() const {↵
return (int)hull.size();↵
}↵
long double get_angle(int pos) const {↵
auto a = hull[(pos + 1) % hull.size()] - hull[pos], b = hull[(pos + hull.size() - 1) % hull.size()] - hull[pos];↵
long double co = (a % b) / a.get_len() / b.get_len();↵
return co;↵
}↵
};↵
↵
void solve(bool read) {↵
vector<Polygon> polys;↵
int n[2];↵
cin >> n[0] >> n[1];↵
for (int i = 0; i < 2; ++i) {↵
polys.emplace_back(n[i]);↵
}↵
if (polys[0].size() != polys[1].size()) {↵
cout << "NO\n";↵
return;↵
}↵
vector<long double> all_lens;↵
int m = polys[0].size();↵
for (int i = 0; i < m; ++i) {↵
all_lens.push_back(polys[0].sqr_len(i));↵
all_lens.push_back(polys[0].get_angle(i));↵
}↵
all_lens.push_back(-1);↵
for (int j = 0; j < 2; ++j) {↵
for (int i = 0; i < m; ++i) {↵
all_lens.push_back(polys[1].sqr_len(i));↵
all_lens.push_back(polys[1].get_angle(i));↵
}↵
}↵
/*for (int x : all_lens) {↵
cout << x << " ";↵
}↵
cout << "\n";*/↵
vector<int> p(all_lens.size());↵
for (int i = 1; i < p.size(); ++i) {↵
int j = p[i - 1];↵
while (j > 0 && all_lens[i] != all_lens[j]) {↵
j = p[j - 1];↵
}↵
if (all_lens[i] == all_lens[j]) {↵
++j;↵
}↵
p[i] = j;↵
if (p[i] == 2 * m) {↵
cout << "YES\n";↵
return;↵
}↵
}↵
cout << "NO\n";↵
↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1017F]↵
↵
<spoiler summary="Solution(Magolor,optimized by arsijo)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define uint unsigned int↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
bitset<100000032> _b; int n; uint A, B, C, D, Ans;↵
inline uint f(int p){↵
return((A*p+B)*p+C)*p+D;↵
}↵
inline int cnt(int p, int n){↵
int r=0;↵
for(;n/=p;r+=n);↵
return r;↵
}↵
inline auto b(int i)->decltype(_b[0]){↵
return _b[(i&1)&&(i%6!=3)?i/6<<1|((i%6)>1):0];↵
}↵
inline auto b2(int i)->decltype(_b[0]){↵
return _b[i/6<<1|1];↵
}↵
inline auto b3(int i)->decltype(_b[0]){↵
return _b[i/6<<1];↵
}↵
↵
int main()↵
{↵
n = rf();↵
A = rf();↵
B = rf();↵
C = rf();↵
D = rf();↵
_b[0] = 1;↵
Ans = cnt(2,n)*f(2)+cnt(3,n)*f(3);↵
for(rint i = 5, j, z, c, w; i <= n; i += 4){↵
if(!b2(i))↵
{↵
Ans += cnt(i,n)*f(i);↵
if(i <= 20000){↵
w = i + i;↵
c = w % 6;↵
z = (i * i) % 6;↵
if(c == 0){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w){↵
b3(j) = 1;↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w){↵
b2(j) = 1;↵
}↵
}↵
}else if(c == 2){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w){↵
b3(j) = 1;↵
j += w + w;↵
if(j <= n){↵
b2(j) = 1;↵
}↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w + w){↵
b2(j) = 1;↵
j += w;↵
if(j <= n){↵
b3(j) = 1;↵
}↵
}↵
}↵
}else if(c == 4){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w + w){↵
b3(j) = 1;↵
j += w;↵
if(j <= n){↵
b2(j) = 1;↵
}↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w){↵
b2(j) = 1;↵
j += w + w;↵
if(j <= n){↵
b3(j) = 1;↵
}↵
}↵
}↵
}↵
}↵
}↵
i += 2;↵
if(i <= n && !b3(i))↵
{↵
Ans += cnt(i,n)*f(i);↵
if(i <= 20000){↵
w = i + i;↵
c = w % 6;↵
z = (i * i) % 6;↵
if(c == 0){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w){↵
b3(j) = 1;↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w){↵
b2(j) = 1;↵
}↵
}↵
}else if(c == 2){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w){↵
b3(j) = 1;↵
j += w + w;↵
if(j <= n){↵
b2(j) = 1;↵
}↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w + w){↵
b2(j) = 1;↵
j += w;↵
if(j <= n){↵
b3(j) = 1;↵
}↵
}↵
}↵
}else if(c == 4){↵
if(z == 1){↵
for(j = i * i; j <= n; j += w + w){↵
b3(j) = 1;↵
j += w;↵
if(j <= n){↵
b2(j) = 1;↵
}↵
}↵
}else if(z == 5){↵
for(j = i * i; j <= n; j += w){↵
b2(j) = 1;↵
j += w + w;↵
if(j <= n){↵
b3(j) = 1;↵
}↵
}↵
}↵
}↵
}↵
}↵
}↵
printf("%u\n",Ans);↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Solution(000000)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
typedef unsigned int ll;↵
const ll maxn=4e8;↵
const ll maxp=sqrt(maxn)+10;↵
ll f[4][maxp],g[4][maxp];↵
ll n,m,A,B,C,D,ans,res,tmp,rt;↵
↵
ll p1(ll x){↵
ll y=x+1; if (x%2==0) x/=2; else y/=2;↵
return x*y;↵
}↵
ll p2(ll x){↵
long long y=x+1,z=x*2+1;↵
if (x%2==0) x/=2; else y/=2;↵
if (z%3==0) z/=3; else if (x%3==0) x/=3; else y/=3;↵
return (ll)x*y*z;↵
}↵
ll p3(ll x){↵
ll y=p1(x);↵
return y*y;↵
}↵
bool is_prime(ll x){↵
for (ll i=2;i*i<=x;i++) if (x%i==0) return false;↵
return true;↵
}↵
↵
ll solve(ll n)↵
{↵
ll i,j,rt,o[4];↵
for (m=1;m*m<=n;m++) {↵
f[0][m]=(n/m-1);↵
f[1][m]=(p1(n/m)-1)*C;↵
f[2][m]=(p2(n/m)-1)*B;↵
f[3][m]=(p3(n/m)-1)*A;↵
}↵
for (i=1;i<=m;i++) {↵
g[0][i]=(i-1);↵
g[1][i]=(p1(i)-1)*C;↵
g[2][i]=(p2(i)-1)*B;↵
g[3][i]=(p3(i)-1)*A;↵
}↵
for (i=2;i<=m;i++) {↵
if (g[0][i]==g[0][i-1]) continue;↵
o[0]=1; for (int w=1;w<4;w++) o[w]=o[w-1]*i;↵
for (j=1;j<=min(m-1,n/i/i);j++)↵
for (int w=0;w<4;w++)↵
if (i*j<m) f[w][j]-=o[w]*(f[w][i*j]-g[w][i-1]);↵
else f[w][j]-=o[w]*(g[w][n/i/j]-g[w][i-1]);↵
for (j=m;j>=i*i;j--)↵
for (int w=0;w<4;w++)↵
g[w][j]-=o[w]*(g[w][j/i]-g[w][i-1]);↵
}↵
for (int i=1;i<=m+1;i++) f[0][i]*=D,g[0][i]*=D;↵
rt=0;↵
for (ll i=1;n/i>m;i++) {↵
for (int w=0;w<4;w++) rt+=(f[w][i]-g[w][m]);↵
//cout<<"H"<<rt<<endl;↵
}↵
return rt;↵
}↵
↵
int main()↵
{↵
//freopen("input.txt","r",stdin);↵
ll n; cin >> n >> A >> B >> C >> D;↵
ans=solve(n);↵
for (ll i=2;i<=m;i++){↵
if (is_prime(i)){↵
res=A*i*i*i+B*i*i+C*i+D; tmp=n;↵
while (tmp){↵
ans+=res*(tmp/i);↵
tmp/=i;↵
}↵
}↵
}↵
cout << ans << endl;↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1017G]↵
↵
<spoiler summary="Solution(arsijo)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MAX = 1e5 + 10;↵
↵
bool black[MAX]; // is it vertex black now↵
vector<int> vec[MAX]; // main edges↵
bool old_black[MAX]; // to remember the tree before block↵
↵
const int MAX_BLOCK_SIZE = 600;↵
↵
int t[MAX], v[MAX]; // queries↵
↵
bool used[MAX]; // is in mini-tree↵
vector<pair<pair<int, int>, int> > v2[MAX]; // mini-tree edges (son, number of white vertices, dist)↵
int push[MAX]; // push of the i-th vertex in mini-tree↵
bool clear[MAX]; // do we need to clear first↵
↵
void dfs_1(int pos, int prev = -1, int white = 0, int dist = 0){↵
if(used[pos]){↵
if(prev != -1){↵
v2[prev].push_back(make_pair(make_pair(pos, white), dist));↵
}↵
for(int a : vec[pos]){↵
dfs_1(a, pos, 0, 0);↵
}↵
}else{↵
if(!black[pos]){↵
white++;↵
}↵
for(int a : vec[pos]){↵
dfs_1(a, prev, white, dist + 1);↵
}↵
}↵
}↵
↵
void make_1(int pos){↵
if(!black[pos]){↵
black[pos] = true;↵
return;↵
}↵
push[pos]++;↵
for(auto a : v2[pos]){↵
if(a.first.second + 1 <= push[pos]){↵
make_1(a.first.first);↵
}↵
}↵
}↵
↵
void make_2(int pos){↵
black[pos] = false;↵
push[pos] = 0;↵
clear[pos] = true;↵
for(auto &a : v2[pos]){↵
a.first.second = a.second;↵
make_2(a.first.first);↵
}↵
}↵
↵
void dfs_2(int pos, int p = 0, bool cl = false){↵
if(used[pos]){↵
p = push[pos];↵
cl |= clear[pos];↵
}else{↵
black[pos] = old_black[pos];↵
if(cl){↵
black[pos] = false;↵
}↵
if(!black[pos] && p){↵
black[pos] = true;↵
p--;↵
}↵
}↵
for(int a : vec[pos]){↵
dfs_2(a, p, cl);↵
}↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio();↵
cin.tie(0);↵
cout.tie(0);↵
int n, q;↵
cin >> n >> q;↵
for(int i = 2; i <= n; i++){↵
int a;↵
cin >> a;↵
vec[a].push_back(i);↵
}↵
for(int i = 1; i <= q; i++){↵
cin >> t[i] >> v[i];↵
}↵
int root = 1;↵
for(int i = 1; i <= q; i += MAX_BLOCK_SIZE){↵
for(int j = 1; j <= n; j++){↵
used[j] = false;↵
v2[j].clear();↵
old_black[j] = black[j];↵
push[j] = 0;↵
clear[j] = false;↵
}↵
for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){↵
used[v[i + j]] = true;↵
}↵
dfs_1(root);↵
for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){↵
int t = ::t[i + j];↵
int v = ::v[i + j];↵
if(t == 1){↵
make_1(v);↵
}else if(t == 2){↵
make_2(v);↵
}else{↵
cout << (black[v] ? "black" : "white") << "\n";↵
}↵
}↵
dfs_2(root);↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
[tutorial:1017H]↵
↵
<spoiler summary="Solution(Magolor)">↵
↵
~~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 200000↵
#define MOD 998244353↵
#define rint register int↵
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}↵
int n, m, q, B, C, T, fac[MAXN+5], efac[MAXN+5], Ans[MAXN+5], A[MAXN+5], t[MAXN+5], c[MAXN+5];↵
int mp[MAXN+5], rv[480], h[480][100032], _init[MAXN+5], d[105][100032]; bitset<100032> b[480];↵
typedef pair<int,int> pii; pii S[MAXN+5]; struct QU{int u,l,r,k,i;}Q[MAXN+5];↵
inline bool cmpi(const QU &a, const QU &b)↵
{↵
return a.i<b.i;↵
}↵
inline bool cmpm(const QU &a, const QU &b)↵
{↵
return a.u^b.u?a.u<b.u:a.u&1?a.r<b.r:a.r>b.r;↵
}↵
//fastpow↵
inline int fxp(int s, int n=MOD-2){int a=1;for(;n;n&1?a=1ll*a*s%MOD:0,s=1ll*s*s%MOD,n>>=1);return a;}↵
inline void Init(int k)↵
{↵
if(_init[k]) return;↵
_init[k] = ++C;↵
int *D = d[C], s = 1ll*m*k%MOD;↵
D[0] = 1;↵
for(rint i = 1; i <= n; i++)↵
D[i] = 1ll*D[i-1]*(s+i)%MOD;↵
}↵
inline int dxp(int a, int b)↵
{↵
return 1ll*fac[a]*efac[a-b]%MOD;↵
}↵
inline int DXP(int k, int l)↵
{↵
return d[_init[k]][l]; ↵
}↵
void insert(int x)↵
{↵
--h[t[x]][c[x]++];↵
++h[t[x]][c[x]];↵
S[++T] = pii(t[x],c[x]);↵
}↵
void erase(int x)↵
{↵
--h[t[x]][c[x]--];↵
++h[t[x]][c[x]];↵
S[++T] = pii(t[x],c[x]);↵
}↵
inline int calc(int k)↵
{↵
int _ = T; T = 0;↵
for(rint i = 1; i <= _; i++)↵
if(!b[S[i].first][S[i].second]&&h[S[i].first][S[i].second])↵
S[++T] = S[i], b[S[i].first][S[i].second] = 1;↵
int Ans = 1;↵
for(rint i = 1; i <= T; i++)↵
{↵
b[S[i].first][S[i].second] = 0;↵
Ans = 1ll*Ans*fxp(dxp(rv[S[i].first]+k,S[i].second),h[S[i].first][S[i].second])%MOD;↵
}↵
return Ans;↵
}↵
int main()↵
{↵
n = MAXN;↵
for(rint i = fac[0] = 1; i <= n; i++)↵
fac[i] = 1ll*i*fac[i-1]%MOD;↵
efac[n] = fxp(fac[n]);↵
for(rint i = n; i; i--)↵
efac[i-1] = 1ll*i*efac[i]%MOD;↵
n = rf();↵
m = rf();↵
q = rf();↵
B = n/sqrt(q*2/3)+1;↵
for(rint i = 1; i <= n; i++)↵
++t[A[i]=rf()];↵
for(rint i = 1, c = 0; i <= n; i++)↵
mp[t[A[i]]]?:rv[mp[t[A[i]]]=++c]=t[A[i]];↵
for(rint i = 1; i <= m; i++)↵
t[i] = mp[t[i]];↵
for(rint i = 1, l, r, k; i <= q; i++)↵
{↵
l = rf();↵
r = rf();↵
k = rf();↵
Init(k);↵
Q[i] = {~-l/B,l,r,k,i};↵
}↵
sort(Q+1,Q+q+1,cmpm);↵
for(rint i = 1; i <= n; i++)↵
++h[t[A[i]]][0];↵
for(rint i = 1, l = 1, r = 0; i <= q; i++)↵
{↵
for(; l > Q[i].l; insert(A[--l]));↵
for(; r < Q[i].r; insert(A[++r]));↵
for(; l < Q[i].l; erase(A[l++]));↵
for(; r > Q[i].r; erase(A[r--]));↵
Ans[Q[i].i] = calc(Q[i].k);↵
}↵
sort(Q+1,Q+q+1,cmpi);↵
for(rint i = 1; i <= q; i++)↵
printf("%d\n",1ll*DXP(Q[i].k,n-(Q[i].r-Q[i].l+1))*Ans[i]%MOD);↵
return 0;↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Solution(Kostroma)">↵
↵
~~~~~↵
↵
#pragma comment(linker, "/STACK:512000000")↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define all(a) a.begin(), a.end()↵
typedef long long li;↵
typedef long double ld;↵
void solve(__attribute__((unused)) bool);↵
void precalc();↵
clock_t start;↵
#define FILENAME ""↵
↵
int main() {↵
#ifdef AIM↵
string s = FILENAME;↵
// assert(!s.empty());↵
freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);↵
//freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout);↵
#else↵
// freopen(FILENAME ".in", "r", stdin);↵
// freopen(FILENAME ".out", "w", stdout);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
#endif↵
start = clock();↵
int t = 1;↵
#ifndef AIM↵
cout.sync_with_stdio(0);↵
cin.tie(0);↵
#endif↵
precalc();↵
cout.precision(10);↵
cout << fixed;↵
//cin >> t;↵
int testNum = 1;↵
while (t--) {↵
//cout << "Case #" << testNum++ << ": ";↵
solve(true);↵
}↵
cout.flush();↵
#ifdef AIM1↵
while (true) {↵
solve(false);↵
}↵
#endif↵
↵
#ifdef AIM↵
cout.flush();↵
auto end = clock();↵
↵
usleep(10000);↵
print_stats(end - start);↵
usleep(10000);↵
#endif↵
↵
return 0;↵
}↵
↵
template<typename T>↵
T binpow(T q, T w, T mod) {↵
if (!w)↵
return 1 % mod;↵
if (w & 1)↵
return q * 1LL * binpow(q, w - 1, mod) % mod;↵
return binpow(q * 1LL * q % mod, w / 2, mod);↵
}↵
↵
template<typename T>↵
T gcd(T q, T w) {↵
while (w) {↵
q %= w;↵
swap(q, w);↵
}↵
return q;↵
}↵
template<typename T>↵
T lcm(T q, T w) {↵
return q / gcd(q, w) * w;↵
}↵
↵
template <typename T>↵
void make_unique(vector<T>& a) {↵
sort(all(a));↵
a.erase(unique(all(a)), a.end());↵
}↵
↵
template<typename T>↵
void relax_min(T& cur, T val) {↵
cur = min(cur, val);↵
}↵
↵
template<typename T>↵
void relax_max(T& cur, T val) {↵
cur = max(cur, val);↵
}↵
↵
void precalc() {↵
}↵
↵
#define int li↵
const int mod = 998244353;↵
↵
struct Query {↵
int l, r, id;↵
};↵
↵
vector<int> res;↵
vector<int> a;↵
int n;↵
↵
int TIMER = 0;↵
const int C = 200500;↵
int used[C];↵
int cur_cnt[C];↵
int rev[C];↵
map<int, vector<int>> down;↵
vector<int> init;↵
↵
void kill(vector<Query>& all_q, int block_size, int k) {↵
vector<vector<Query>> by_block(n / block_size + 1);↵
for (auto& cur_q : all_q) {↵
by_block[cur_q.l / block_size].push_back(cur_q);↵
}↵
for (int i = 0; i < by_block.size(); ++i) {↵
++TIMER;↵
auto& q = by_block[i];↵
sort(all(q), [&] (const Query& o1, const Query& o2) {↵
return o1.r < o2.r;↵
});↵
int cur_l = min(n, (i + 1) * block_size);↵
int cur_r = cur_l;↵
int cur_prod = 1;↵
↵
auto add_item = [&] (int val) {↵
if (used[val] != TIMER) {↵
used[val] = TIMER;↵
cur_cnt[val] = 0;↵
}↵
int cur_k = k + init[val];↵
++cur_cnt[val];↵
cur_prod = cur_prod * (cur_k - cur_cnt[val] + 1) % mod;↵
};↵
auto remove_item = [&] (int val) {↵
int cur_k = k + init[val];↵
cur_prod = cur_prod * rev[cur_k - cur_cnt[val] + 1] % mod;↵
--cur_cnt[val];↵
};↵
↵
for (auto& cur_q : q) {↵
while (cur_r < cur_q.r) {↵
add_item(a[cur_r++]);↵
}↵
while (cur_l > cur_q.l) {↵
add_item(a[--cur_l]);↵
}↵
while (cur_r > cur_q.r) {↵
remove_item(a[--cur_r]);↵
}↵
while (cur_l < cur_q.l) {↵
remove_item(a[cur_l++]);↵
}↵
res[cur_q.id] = cur_prod * down[k][n - cur_q.r + cur_q.l] % mod;↵
}↵
}↵
}↵
↵
void solve(__attribute__((unused)) bool read) {↵
for (int i = 1; i < C; ++i) {↵
rev[i] = binpow(i, mod - 2, mod);↵
}↵
int m, Q;↵
//read = false;↵
if (read) {↵
cin >> n >> m >> Q;↵
} else {↵
n = 50000;↵
m = 100000;↵
Q = 50000;↵
}↵
a.resize(n);↵
init.assign(m, 0);↵
for (int i = 0; i < n; ++i) {↵
if (read) {↵
cin >> a[i];↵
--a[i];↵
} else {↵
a[i] = rand() % m;↵
}↵
++init[a[i]];↵
}↵
map<int, vector<Query>> q;↵
for (int i = 0; i < Q; ++i) {↵
int l, r, k;↵
if (read) {↵
cin >> l >> r >> k;↵
} else {↵
do {↵
l = rand() % n + 1;↵
r = rand() % n + 1;↵
} while (l > r);↵
k = rand() % 100;↵
}↵
--l;↵
q[k].push_back({l, r, i});↵
down[k] = vector<int>();↵
}↵
res.assign(Q, 0);↵
for (auto& item : down) {↵
int init_val = (item.first * m) % mod;↵
auto& vec = item.second;↵
vec.assign(n + 1, 1);↵
for (int i = 1; i < vec.size(); ++i) {↵
vec[i] = vec[i - 1] * (init_val + i) % mod;↵
}↵
}↵
for (auto& item : q) {↵
int k = item.first;↵
auto& cur_q = item.second;↵
int block_size = std::max((int)(n / sqrt((int)cur_q.size())), 1LL);↵
kill(cur_q, block_size, k);↵
}↵
↵
for (int i = 0; i < Q; ++i) {↵
cout << res[i] << "\n";↵
}↵
↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
### Bonus Problem↵
It is the previous D1E and its standard solution is hacked. Can you solve it?↵
↵
<spoiler summary="Bonus problem">↵
↵
**Legend**↵
↵
How can the man in the high castle, Abendsen, escape so many times? Because he has a full plan of escaping —— with his films.↵
↵
The map of the cities can be described as a tree (i.e. connected graph with $n$ vertices and $n-1$ edges) rooted at node $1$ —— where Abenden lives.↵
↵
When he starts his escaping, he plans **at most** $k$ travels: one travel is a simple path between two (not necessarily different) vertices. So he goes from $1$ to some vertex $v_1$, and then goes from $v_1$ to $v_2$, and so on $\ldots$↵
↵
When he is visiting a vertex (even though he has visited this vertex before) he will get some films. But in some vertexes, he has to give some films. Note that Abendsen \textbf{can} have a negative amount of films. But after every travel, he **has to have a non-negative amount of films**. Note that when Abendsen is starting a new travel, **he is visiting the starting vertex too**. It sounds weird but it is a different world!↵
↵
At first, Abendsen does not have any films.↵
↵
He wants to maximize the number of the films he gets after the escape. So please help him find out the maximized films number he can get.↵
↵
**Input Format**↵
↵
The first line two contains two integers $n$ and $k$ ($1 \le n \le 1000$, $1 \le k \le 10^6$) —— the number of vertices and the maximum number of travels allowed.↵
↵
The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($|w_i|\leq 10^8$) —— how many films will Abendsen get (or give if $w_i$ is negative) if he visits the $i$-th vertex.↵
↵
Each of the next $n-1$ lines contains two integers $u_i$ and $v_i$ ($1\leq u_i, v_i\leq n$, $u_i\neq v_i$) —— vertices connected by the $i$-th edge.↵
↵
It is guaranteed that the input data describes a correct tree.↵
↵
**Output Format**↵
↵
Print one integer, the maximum number of films he can get.↵
↵
↵
</spoiler>↵
↵
