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";
}
}