Tutorial is loading...
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;
}
Tutorial is loading...
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;
}
Tutorial is loading...
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;
}
Tutorial is loading...
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;
}
Tutorial is loading...
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;
}
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";
}
Tutorial is loading...
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;
}
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;
}
Tutorial is loading...
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;
}
Tutorial is loading...
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;
}
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";
}
}
Bonus Problem
It is the previous D1E and its standard solution is hacked. Can you solve it?
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 v1, and then goes from v1 to v2, and so on ...
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 ≤ n ≤ 1000, 1 ≤ k ≤ 106) —— the number of vertices and the maximum number of travels allowed.
The second line contains n integers w1, w2, ..., wn (|wi| ≤ 108) —— how many films will Abendsen get (or give if wi is negative) if he visits the i-th vertex.
Each of the next n - 1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) —— 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.
