You can now find the contest in the public gym, [contest:105064] (the ghost submissions can still be accessed in [the older mashup](https://codeforces.me/contestInvitation/3db62e18494ff4c05b0bfb537635f448cb23599d)).↵
↵
↵
<spoiler summary="Top 15">↵
1. HR se puuch ke batayenge: [user:rivalq,2024-03-31], [user:magga,2024-03-31], [user:Kira_1234,2024-03-31]↵
↵
2. nulllösungssatz: [user:Dominater069,2024-03-31], [user:aryanc403,2024-03-31], [user:IceKnight1093,2024-03-31]↵
↵
3. 4C3: [user:koderkushy,2024-03-31], [user:piyush_pransukhka,2024-03-31], [user:kingmessi,2024-03-31]↵
↵
4. tbd: [user:keyurchd_11,2024-03-31], [user:shiven,2024-03-31], [user:GenghizKhan,2024-03-31]↵
↵
5. ElDiablo: [user:ElDiablo,2024-03-31]↵
↵
6. rng: [user:Atekichan,2024-03-31], [user:sv1shan,2024-03-31]↵
↵
7. SmolBrain: [user:SmolBrain,2024-03-31] ↵
↵
8. Pols_Station: [user:Pols_Agyi_Pols,2024-03-31]↵
↵
9. PalindORme: [user:the_hyp0cr1t3,2024-03-31], [user:JeevanJyot,2024-03-31], [user:ExplodingFreeze,2024-03-31]↵
↵
10. Team: [user:jtnydv25,2024-03-31] ↵
↵
11. Cult Council: [user:AKSLEGION,2024-03-31], [user:D1orite,2024-03-31], [user:shorya1835,2024-03-31]↵
↵
12. IDK: [user:ha___il,2024-03-31], [user:JadeReaper,2024-03-31], [user:akcube,2024-03-31]↵
↵
13. ThreeMusketeers: [user:gakshat468,2024-03-31], [user:sg0071729,2024-03-31], [user:21cs01033,2024-03-31] ↵
↵
14. cns_lena_chahiye_tha: [user:dhruvsomani,2024-03-31], [user:vikram108,2024-03-31], [user:ParadigmShift,2024-03-31]↵
↵
15. 3CoOks: [user:thirdcook,2024-03-31], [user:a_garg,2024-03-31], [user:Rayquaza,2024-03-31]↵
</spoiler>↵
↵
<spoiler summary="IITD Top 3">↵
1. ElDiablo: [user:ElDiablo,2024-03-31]↵
↵
2. Team: [user:jtnydv25,2024-03-31] ↵
↵
3. monoid: [user:htnaver,2024-03-31], [user:kayou81,2024-03-31], [user:atimanas,2024-03-31]↵
↵
4. No clue: [user:Beelzebub_blue,2024-04-01]↵
↵
5. Death Valley: [user:1729_prism,2024-04-01], [user:Abhishek_821023,2024-04-01], [user:dark_ethics,2024-04-01]↵
↵
We'll give prizes to the next 3 IITD teams not in the top 15.↵
</spoiler>↵
↵
↵
<spoiler summary="First Solves">↵
A: ThreeMusketeers: [user:gakshat468,2024-04-01], [user:sg0071729,2024-04-01], [user:21cs01033,2024-04-01]↵
↵
↵
B: No clue: [user:Beelzebub_blue,2024-04-01]↵
↵
↵
C: nulllösungssatz: [user:Dominater069,2024-04-01], [user:aryanc403,2024-04-01], [user:IceKnight1093,2024-04-01]↵
↵
↵
D: HR se puuch ke batayenge: [user:rivalq,2024-04-01], [user:magga,2024-04-01], [user:Kira_1234,2024-04-01]↵
↵
↵
E: nulllösungssatz: [user:Dominater069,2024-04-01], [user:aryanc403,2024-04-01], [user:IceKnight1093,2024-04-01]↵
↵
↵
F: tbd: [user:keyurchd_11,2024-04-01], [user:shiven,2024-04-01], [user:GenghizKhan,2024-04-01]↵
↵
↵
G: unforgettable playz: [user:noobcodur,2024-04-01], [user:oviyan_gandhi,2024-04-01], [user:unforgettablepl,2024-04-01]↵
↵
↵
H: HR se puuch ke batayenge: [user:rivalq,2024-04-01], [user:magga,2024-04-01], [user:Kira_1234,2024-04-01]↵
↵
↵
I: OverShadow: [user:Coder_Nayak,2024-04-01], [user:Krypto_Ray,2024-04-01], [user:sloppy_coder,2024-04-01]↵
↵
↵
J: nulllösungssatz: [user:Dominater069,2024-04-01], [user:aryanc403,2024-04-01], [user:IceKnight1093,2024-04-01]↵
↵
↵
K: nulllösungssatz: [user:Dominater069,2024-04-01], [user:aryanc403,2024-04-01], [user:IceKnight1093,2024-04-01]↵
↵
</spoiler>↵
↵
[tutorial:105064A]↵
Setter: [user:BladeRunner,2024-04-01]↵
↵
<spoiler summary="code">↵
```↵
//solution to Highly Constrained Permutation↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve()↵
{↵
int n; cin>>n;↵
vector<int> a(n+1),b(n+1);↵
↵
for(int i=1;i<=n;i++) cin>>a[i];↵
for(int i=1;i<=n;i++) cin>>b[i];↵
↵
vector<vector<int>> adj(n+1);↵
↵
//make graph in the forward direction first↵
vector<int> last(n+1);↵
for(int i=1;i<=n;i++)↵
{↵
//deal with last[a[i]-1] case↵
if(a[i]!=1)↵
{↵
if(last[a[i]-1]==0)↵
{↵
cout<<-1<<'\n';↵
return;↵
}↵
else adj[last[a[i]-1]].push_back(i);↵
}↵
//deal with the last[a[i]] case↵
if(last[a[i]] != 0) adj[i].push_back(last[a[i]]);↵
last[a[i]]=i;↵
}↵
↵
//now in the backward direction↵
vector<int> next(n+1);↵
for(int i=n;i>=1;i--)↵
{↵
//deal with next[b[i]-1] case↵
if(b[i]!=1)↵
{↵
if(next[b[i]-1]==0)↵
{↵
cout<<-1<<'\n';↵
return;↵
}↵
else adj[i].push_back(next[b[i]-1]);↵
}↵
//deal with the next[b[i]] case↵
if(next[b[i]] != 0) adj[next[b[i]]].push_back(i);↵
next[b[i]]=i;↵
}↵
↵
//so now toposort this graph↵
vector<bool> popped(n+1,false);↵
vector<int> indg(n+1);↵
queue<int> q;↵
↵
// for(int i=1;i<=n;i++)↵
// {↵
// cout<<i<<'\n';↵
// for(auto j:adj[i]) cout<<j<<' ';↵
// cout<<'\n';↵
// }↵
↵
for(int i=1;i<=n;i++)↵
{↵
for(auto j:adj[i]) indg[j]++;↵
}↵
↵
for(int i=1;i<=n;i++)↵
{↵
if(indg[i]==0) q.push(i);↵
}↵
↵
vector<int> order;↵
↵
while(!q.empty())↵
{↵
int f=q.front();↵
q.pop();↵
popped[f]=true;↵
order.push_back(f);↵
↵
for(auto nbr:adj[f]) ↵
{↵
indg[nbr]--;↵
if(indg[nbr]==0) q.push(nbr);↵
}↵
}↵
↵
if((int)order.size() < n)↵
{↵
printf("%d\n",-1);↵
return;↵
}↵
↵
vector<int> ans(n+1);↵
for(int i=0;i<n;i++) ans[order[i]]=i+1;↵
↵
for(int i=1;i<=n;i++) printf("%d ",ans[i]);↵
printf("\n");↵
}↵
↵
signed main()↵
{↵
int t; cin>>t;↵
while(t--) solve();↵
}↵
```↵
</spoiler>↵
↵
[tutorial:105064B]↵
Setter: [user:33_arsenic_75,2024-04-01], Preparation: [user:islingr,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include "bits/stdc++.h"↵
↵
using namespace std;↵
↵
int solve() {↵
int n, x;↵
cin >> n >> x;↵
↵
const int msb = x >> 10 & 1;↵
↵
if (msb == (n & 1)) return 10 * n;↵
return 10 * (n - 1) + 9;↵
}↵
↵
int main() {↵
cin.tie(nullptr)->sync_with_stdio(false);↵
↵
int t;↵
cin >> t;↵
while (t--) cout << solve() << '\n';↵
}↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064C]↵
Setter: [user:sahilkumar_1,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
↵
ll rotate(ll x,ll base,vector <ll> & info){↵
if(x<base) return x;↵
int k=0;↵
for(int i=0;i<info.size();i++){↵
if(info[i]<=x&&info[i+1]>x){↵
k=i;↵
break;↵
}↵
}↵
return (info[k]*(x%base)+(x/base));↵
}↵
↵
ll min_possible(ll x, ll base,vector <ll> & info){↵
if(x<base) return x;↵
ll ans=x;↵
for(int i=0;i<64;i++){↵
x=rotate(x,base,info);↵
ans=min(ans,x);↵
}↵
return ans;↵
}↵
↵
void solve(vector <vector <ll>> & vect){↵
int n;↵
cin >> n;↵
ll sum=0;↵
for(int i=0;i<n;i++){↵
ll x;↵
cin>>x;↵
sum+=min_possible(x,i+3,vect[i+3]);↵
}↵
cout<<sum<<endl;↵
}↵
↵
int main(){↵
int t;↵
cin >> t;↵
vector <vector <ll>> vect(1e5+3);↵
for(int i=3;i<=1e5+2;i++){↵
ll cur=1;↵
while(true){↵
vect[i].push_back(cur);↵
if(cur>1e9) break;↵
cur*=i;↵
}↵
}↵
while(t--) solve(vect);↵
}↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064D]↵
Setter: [user:ajmeraraghav99,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main()↵
{↵
long long int n,i,j;↵
cin>>n;↵
long long int marks[n+1];↵
int check[n+1];↵
for(i=1;i<=n;i++)↵
{↵
check[i]=0;↵
}↵
vector<int> v;↵
i=1;↵
while(i<=n)↵
{↵
if(v.size()==0)↵
{↵
v.push_back(i);↵
i++;↵
}↵
else↵
{↵
cout<<"? "<<v[v.size()-1]<<" "<<i<<endl;↵
fflush(stdout);↵
long long int x;↵
cin>>x;↵
marks[i]=abs(x);↵
check[i]=1;↵
if(x>0)↵
{↵
v.push_back(i);↵
}↵
else↵
{↵
v.pop_back();↵
}↵
i++;↵
↵
}↵
}↵
int honest_index=v[v.size()-1];↵
vector<pair<long long,long long>> first_half;↵
for(i=1;i<=n;i++)↵
{↵
if(i!=honest_index)↵
{↵
if(check[i])↵
{↵
first_half.push_back({-marks[i],i});↵
}↵
else↵
{↵
cout<<"? "<<honest_index<<" "<<i<<endl;↵
fflush(stdout);↵
long long int dum;↵
cin>>dum;↵
marks[i]=abs(dum);↵
check[i]=1;↵
first_half.push_back({-marks[i],i});↵
↵
}↵
}↵
}↵
sort(first_half.begin(),first_half.end());↵
int index=-1;↵
for(i=0;i<(n+1)/2;i++)↵
{↵
int dum_indx=first_half[i].second;↵
cout<<"? "<<honest_index<<" "<<dum_indx<<endl;↵
fflush(stdout);↵
long long int dum_marks;↵
cin>>dum_marks;↵
if(dum_marks>0)↵
{↵
index=dum_indx;↵
marks[index]=dum_marks;↵
break;↵
}↵
}↵
cout<<"? "<<index<<" "<<honest_index<<endl;↵
fflush(stdout);↵
long long smth;↵
cin>>smth;↵
marks[honest_index]=smth;↵
if(marks[honest_index]>marks[index])↵
{↵
↵
cout<<"! "<<honest_index<<endl;↵
}↵
else↵
{↵
↵
cout<<"! "<<index<<endl;↵
}↵
↵
↵
↵
↵
return 0;↵
} ↵
↵
```↵
</spoiler>↵
↵
[tutorial:105064E]↵
Setter: [user:Azm1t,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include "bits/stdc++.h"↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>↵
↵
void solve(){↵
↵
int n, q; cin >> n >> q;↵
↵
vector<int> c(n);↵
for(int &x: c) cin >> x, x--;↵
↵
vector<vector<int>> adj(n);↵
for(int i = 0; i < n-1; i++){↵
int u, v; cin >> u >> v; ↵
u--; v--;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
↵
ordered_set os[n];↵
vector<int> tin(n, 0), tout(n, 0);↵
int time = 0;↵
↵
function<void(int, int)> dfs = [&](int v, int p){↵
tin[v] = time++;↵
for(int child: adj[v]){↵
if(child != p) dfs(child, v);↵
}↵
tout[v] = time++;↵
os[c[v]].insert({tin[v], v});↵
};↵
↵
dfs(0, -1);↵
↵
while(q--){↵
↵
int type, v, x; cin >> type >> v >> x;↵
v--; x--;↵
↵
if(type == 1){↵
os[c[v]].erase({tin[v], v});↵
c[v] = x;↵
os[c[v]].insert({tin[v], v});↵
}↵
else{↵
auto firstit = os[x].order_of_key({tin[v], -1});↵
auto lastit = os[x].order_of_key({tout[v], n+1});↵
cout << lastit - firstit << '\n';↵
}↵
↵
}↵
↵
}↵
↵
↵
signed main(){↵
↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int t = 1;↵
cin >> t;↵
while(t--) solve();↵
} ↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064F]↵
Setter: [user:Proelectro444,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define endl '\n'↵
↵
const int LOCATION = 4020;↵
const int MAXP = 1001;↵
const int SHIFT = 1010;↵
long long dp[MAXP][LOCATION];↵
↵
int main(){↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n, q;↵
cin >> n >> q;↵
vector<int> a(n), p(n);↵
for(int i = 0; i < n; i++){↵
cin >> a[i];↵
}↵
for(int i = 0; i < n; i++){↵
cin >> p[i];↵
}↵
for(int i = 0; i < n; i++){↵
dp[p[i]][a[i] + SHIFT] += 1ll;↵
if(p[i] != 0)↵
dp[p[i] — 1][a[i] + SHIFT] += 1ll;↵
}↵
for(int s = MAXP — 2; s >= 0; s--){↵
for(int i = 1; i < LOCATION — 1; i++){↵
dp[s][i] += dp[s + 1][i — 1] + dp[s + 1][i + 1] — (s + 2 < MAXP ? dp[s + 2][i] : 0);↵
}↵
}↵
for(int i = 0; i < MAXP; i++){↵
for(int j = 1; j < LOCATION; j++){↵
dp[i][j] += dp[i][j — 1];↵
}↵
}↵
while(q--){↵
int l, r, s;↵
cin >> l >> r >> s;↵
l += SHIFT;↵
r += SHIFT;↵
cout << dp[s][r] — dp[s][l — 1] << endl;↵
}↵
↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064G]↵
Idea:[user:Proelectro444,2024-04-01] , [user:BladeRunner,2024-04-01] Preparation: [user:Proelectro444,2024-04-01]↵
↵
<spoiler summary="code">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define endl '\n'↵
↵
bool solve(int s, int n, int k, int a[], int p[]){↵
vector<pair<int, int>> interval;↵
for (int i = 0; i < n; i++)↵
{↵
if (p[i] — s >= 0)↵
{↵
int left = a[i] — p[i] + s;↵
int right = a[i] + p[i] — s;↵
interval.push_back({left, 1});↵
interval.push_back({right + 1, -1});↵
}↵
}↵
sort(interval.begin(), interval.end());↵
int m = 0, sm = 0;↵
for (auto [_, v] : interval)↵
{↵
sm += v;↵
m = max(m, sm);↵
}↵
↵
return m <= k;↵
}↵
↵
int main(){↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int t;↵
cin >> t;↵
while (t--)↵
{↵
int n, k;↵
cin >> n >> k;↵
int a[n], p[n];↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
for (int i = 0; i < n; i++)↵
cin >> p[i];↵
int l = 0, r = 1e9 + 10;↵
while (l <= r){↵
int mid = (l + r) / 2;↵
if (solve(mid, n, k, a, p))↵
r = mid — 1;↵
else↵
l = mid + 1;↵
}↵
cout << l << endl;↵
}↵
}↵
↵
```↵
</spoiler>↵
↵
[tutorial:105064H]↵
Setter: [user:islingr,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
#define rep(i, a, b) for (auto i{a}; i < (b); ++i)↵
#define per(i, a, b) for (auto i{b}; i-- > (a); )↵
#define sz(x) (int)(x).size()↵
#define all(x) (x).begin(), (x).end()↵
#define rall(x) (x).rbegin(), (x).rend()↵
↵
template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }↵
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }↵
↵
using ll = long long;↵
using poly = vector<ll>;↵
↵
constexpr int mod = 998'244'353, root = 62;↵
↵
int modpow(ll a, int b) {↵
ll res = 1;↵
for (; b; a = a * a % mod, b /= 2)↵
if (b & 1) res = res * a % mod;↵
return res;↵
}↵
↵
void ntt(poly &a) {↵
int n = sz(a), L = 31 — __builtin_clz(n);↵
static poly rt(2, 1);↵
for (static int k = 2, s = 2; k < n; k *= 2, s++) {↵
rt.resize(n);↵
ll z[] = {1, modpow(root, mod >> s)};↵
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;↵
}↵
vector<int> rev(n);↵
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;↵
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);↵
for (int k = 1; k < n; k *= 2)↵
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {↵
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];↵
a[i + j + k] = ai — z + (z > ai ? mod : 0);↵
ai += (ai + z >= mod ? z — mod : z);↵
}↵
}↵
poly conv(const poly &a, const poly &b) {↵
if (a.empty() || b.empty()) return {};↵
int s = sz(a) + sz(b) — 1, B = 32 — __builtin_clz(s),↵
n = 1 << B;↵
int inv = modpow(n, mod — 2);↵
poly L(a), R(b), out(n);↵
L.resize(n), R.resize(n);↵
ntt(L), ntt(R);↵
rep(i,0,n)↵
out[-i & (n — 1)] = (ll)L[i] * R[i] % mod * inv % mod;↵
ntt(out);↵
return {out.begin(), out.begin() + s};↵
}↵
↵
↵
poly operator*(const poly& a, const poly& b) {↵
return conv(a, b);↵
}↵
↵
constexpr int N = 2e5 + 10;↵
ll fac[N];↵
↵
ll mul(ll x, ll y) { return x * y % mod; }↵
↵
int main() {↵
cin.tie(nullptr)->sync_with_stdio(false);↵
↵
fac[0] = 1;↵
rep(i, 1, N) fac[i] = mul(i, fac[i - 1]);↵
↵
int n;↵
cin >> n;↵
↵
vector<ll> a(n);↵
for (auto& x : a) cin >> x;↵
↵
poly T(n);↵
for (int s = 1; s < n; ++s)↵
T[s] = mul(fac[s - 1], fac[n - s - 1]);↵
↵
vector<ll> score(n);↵
↵
auto rec = [&](const auto& self, int l, int r, const poly& T) -> poly {↵
if (r - l == 1) {↵
poly P;↵
if (l == n - 1) P = {0, 1};↵
else P = {1, a[l + 1]};↵
score[l] = (T[0] * P[0] + T[1] * P[1]) % mod;↵
return P;↵
}↵
↵
const int mid = l + (r - l) / 2;↵
↵
const poly Tr(T.begin(), T.begin() + (r - mid + 1));↵
auto Pr = self(self, mid, r, Tr);↵
↵
reverse(all(Pr));↵
auto Tl = Pr * T;↵
Tl.erase(Tl.begin(), Tl.begin() + (r - mid));↵
reverse(all(Pr));↵
↵
const auto Pl = self(self, l, mid, Tl);↵
↵
return Pl * Pr;↵
};↵
rec(rec, 1, n, T);↵
↵
const auto to_div = modpow(fac[n - 1], mod - 2);↵
rep(i, 1, n) score[i] = mul(to_div, mul(i, mul(a[i], score[i])));↵
↵
score[0] = 1;↵
for (auto x : a) score[0] = mul(score[0], x);↵
↵
rep(i, 0, n) cout << score[i] << " \n"[i == n - 1];↵
}↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064I]↵
Setter: [user:Surver,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n, k, m;↵
cin >> n >> k >> m;↵
vector<int> v(n);↵
for (int i = 0; i < n; i++) {↵
cin >> v[i];↵
}↵
vector<pair<int, int>> q(m);↵
for (int i = 0; i < m; i++) {↵
cin >> q[i].first >> q[i].second;↵
}↵
vector<int> ans(m);↵
auto calc = [&] () {↵
vector<vector<int>> suf(n + 1, vector<int>(k + 1));↵
for (int i = n — 1; i >= 0; i--) {↵
suf[i] = suf[i + 1];↵
int cost = 0, sum = 0;↵
for (int j = i; j < n; j++) {↵
cost += (v[j] > 0);↵
sum -= abs(v[j]);↵
if (cost <= k) {↵
suf[i][cost] = min(suf[i][cost], sum);↵
}↵
}↵
for (int j = 1; j <= k; j++) {↵
suf[i][j] = min(suf[i][j], suf[i][j — 1]);↵
}↵
}↵
vector<int> dp(n + 1, 1);↵
vector<int> h(n + 1, k + 1);↵
h[0] = 0;↵
for (int i = 0; i <= n; i++) {↵
if (i > 0) {↵
int cost = 0, sum = 0;↵
for (int j = i — 1; j >= 0; j--) {↵
cost += (v[j] < 0);↵
sum += abs(v[j]);↵
h[sum] = min(h[sum], cost);↵
}↵
}↵
for (int j = 0; j <= n; j++) {↵
if (h[j] <= k) {↵
dp[j] = min(dp[j], suf[i][k — h[j]]);↵
}↵
}↵
}↵
for (int i = 0; i < m; i++){↵
for (int j = 0; j <= n; j++){↵
if (dp[j] <= 0){↵
ans[i] = max(ans[i], q[i].first * j — q[i].second * dp[j]);↵
}↵
}↵
}↵
};↵
calc();↵
reverse(v.begin(), v.end());↵
calc();↵
for (int i = 0; i < m; i++){↵
cout << ans[i] << " \n"[i == m — 1];↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
[tutorial:105064J]↵
Setter: [user:BladeRunner,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include<bits/stdc++.h>↵
#define int long long↵
using namespace std;↵
↵
const int N=1e6+100;↵
const int mod = 1e9+7;↵
vector<int> fact(N+1);↵
vector<int> ifact(N+1);↵
↵
int binexp(int a,int n)↵
{↵
if(n==0) return 1;↵
else↵
{↵
int res=binexp(a,n/2);↵
res=(res*res)%mod;↵
if(n&1) res=(res*a)%mod;↵
return res;↵
}↵
}↵
↵
int ncr(int n,int r)↵
{↵
if(r>n || r<0 || n<0) return 0;↵
int ans=(fact[n]*ifact[r])%mod;↵
ans=(ans*ifact[n-r])%mod;↵
return ans;↵
}↵
↵
void solve()↵
{↵
int n,x,y; cin>>n>>x>>y;↵
int dif=abs(x-y);↵
cout<<ncr(n-2,dif-1)<<'\n';↵
}↵
↵
signed main()↵
{↵
int t; cin>>t;↵
↵
fact[0]=1;↵
for(int i=1;i<=N;i++) fact[i]=(fact[i-1]*i)%mod;↵
ifact[N]=binexp(fact[N],mod-2);↵
for(int i=N-1;i>=0;i--) ifact[i]=(ifact[i+1]*(i+1))%mod;↵
↵
while(t--) solve();↵
}↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064K]↵
Setter: [user:MridulAhi,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
#define rep(i, a, b) for (auto i{a}; i < (b); ++i)↵
#define per(i, a, b) for (auto i{b}; i-- > (a); )↵
#define sz(x) (int)(x).size()↵
#define all(x) (x).begin(), (x).end()↵
#define rall(x) (x).rbegin(), (x).rend()↵
↵
template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }↵
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }↵
↵
using ll = long long;↵
↵
using U = uint32_t;↵
using poly = vector<ll>;↵
↵
constexpr int mod = 998'244'353, root = 62;↵
↵
int modpow(ll a, int b) {↵
ll res = 1;↵
for (; b; a = a * a % mod, b /= 2)↵
if (b & 1) res = res * a % mod;↵
return res;↵
}↵
↵
void ntt(poly &a) {↵
int n = sz(a), L = 31 — __builtin_clz(n);↵
static poly rt(2, 1);↵
for (static int k = 2, s = 2; k < n; k *= 2, s++) {↵
rt.resize(n);↵
ll z[] = {1, modpow(root, mod >> s)};↵
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;↵
}↵
vector<int> rev(n);↵
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;↵
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);↵
for (int k = 1; k < n; k *= 2)↵
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {↵
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];↵
a[i + j + k] = ai — z + (z > ai ? mod : 0);↵
ai += (ai + z >= mod ? z — mod : z);↵
}↵
}↵
poly conv(const poly &a, const poly &b) {↵
if (a.empty() || b.empty()) return {};↵
int s = sz(a) + sz(b) — 1, B = 32 — __builtin_clz(s),↵
n = 1 << B;↵
int inv = modpow(n, mod — 2);↵
poly L(a), R(b), out(n);↵
L.resize(n), R.resize(n);↵
ntt(L), ntt(R);↵
rep(i,0,n)↵
out[-i & (n — 1)] = (ll)L[i] * R[i] % mod * inv % mod;↵
ntt(out);↵
return {out.begin(), out.begin() + s};↵
}↵
↵
constexpr int N = 1e5;↵
↵
ll mul(ll x, ll y) { return x * y % mod; }↵
↵
int fac[N], ifac[N];↵
int C(int n, int r) { return mul(fac[n], mul(ifac[r], ifac[n — r])); }↵
↵
int solve() {↵
int n, m, k;↵
cin >> n >> m >> k;↵
↵
vector<vector<int>> g(k);↵
rep(e, 0, m) {↵
char a, b;↵
cin >> a >> b;↵
const int u = a - 'a', v = b - 'a';↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
↵
vector Q(k + 1, poly(n + 1, 0));↵
for (int t = 1; t <= k; ++t)↵
for (int r = t; r <= n; ++r)↵
Q[t][r] = mul(ifac[r], C(r - 1, t - 1));↵
↵
auto merge = [&](const poly& a, const poly& b) {↵
auto c = conv(a, b);↵
c.resize(n + 1, 0);↵
return c;↵
};↵
↵
ll res = 0;↵
vector<poly> f(1 << k);↵
f[0].assign(n + 1, 0);↵
f[0][0] = 1;↵
rep(S, 1u, 1u << k) {↵
const auto root = 31 ^ __builtin_clz(S);↵
assert(S >> root & 1);↵
↵
U T = 0;↵
{↵
auto dfs = [&](const auto& self, int u) -> void {↵
T |= 1u << u;↵
for (auto v : g[u])↵
if ((~T & S) >> v & 1)↵
self(self, v);↵
};↵
dfs(dfs, root);↵
}↵
↵
const int t = popcount(T);↵
f[S] = merge(f[S ^ T], Q[t]);↵
res += f[S][n];↵
}↵
return mul(res % mod, fac[n]);↵
}↵
↵
int main() {↵
cin.tie(nullptr)->sync_with_stdio(false);↵
↵
fac[0] = 1;↵
rep(i, 1, N) fac[i] = mul(i, fac[i - 1]);↵
ifac[N - 1] = modpow(fac[N - 1], mod - 2);↵
per(i, 1, N) ifac[i - 1] = mul(i, ifac[i]);↵
↵
int t;↵
cin >> t;↵
while (t--) cout << solve() << '\n';↵
}↵
```↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Top 15">↵
1. HR se puuch ke batayenge: [user:rivalq,2024-03-31], [user:magga,2024-03-31], [user:Kira_1234,2024-03-31]↵
↵
2. nulllösungssatz: [user:Dominater069,2024-03-31], [user:aryanc403,2024-03-31], [user:IceKnight1093,2024-03-31]↵
↵
3. 4C3: [user:koderkushy,2024-03-31], [user:piyush_pransukhka,2024-03-31], [user:kingmessi,2024-03-31]↵
↵
4. tbd: [user:keyurchd_11,2024-03-31], [user:shiven,2024-03-31], [user:GenghizKhan,2024-03-31]↵
↵
5. ElDiablo: [user:ElDiablo,2024-03-31]↵
↵
6. rng: [user:Atekichan,2024-03-31], [user:sv1shan,2024-03-31]↵
↵
7. SmolBrain: [user:SmolBrain,2024-03-31] ↵
↵
8. Pols_Station: [user:Pols_Agyi_Pols,2024-03-31]↵
↵
9. PalindORme: [user:the_hyp0cr1t3,2024-03-31], [user:JeevanJyot,2024-03-31], [user:ExplodingFreeze,2024-03-31]↵
↵
10. Team: [user:jtnydv25,2024-03-31] ↵
↵
11. Cult Council: [user:AKSLEGION,2024-03-31], [user:D1orite,2024-03-31], [user:shorya1835,2024-03-31]↵
↵
12. IDK: [user:ha___il,2024-03-31], [user:JadeReaper,2024-03-31], [user:akcube,2024-03-31]↵
↵
13. ThreeMusketeers: [user:gakshat468,2024-03-31], [user:sg0071729,2024-03-31], [user:21cs01033,2024-03-31] ↵
↵
14. cns_lena_chahiye_tha: [user:dhruvsomani,2024-03-31], [user:vikram108,2024-03-31], [user:ParadigmShift,2024-03-31]↵
↵
15. 3CoOks: [user:thirdcook,2024-03-31], [user:a_garg,2024-03-31], [user:Rayquaza,2024-03-31]↵
</spoiler>↵
↵
<spoiler summary="IITD Top 3">↵
1. ElDiablo: [user:ElDiablo,2024-03-31]↵
↵
2. Team: [user:jtnydv25,2024-03-31] ↵
↵
3. monoid: [user:htnaver,2024-03-31], [user:kayou81,2024-03-31], [user:atimanas,2024-03-31]↵
↵
4. No clue: [user:Beelzebub_blue,2024-04-01]↵
↵
5. Death Valley: [user:1729_prism,2024-04-01], [user:Abhishek_821023,2024-04-01], [user:dark_ethics,2024-04-01]↵
↵
We'll give prizes to the next 3 IITD teams not in the top 15.↵
</spoiler>↵
↵
↵
<spoiler summary="First Solves">↵
A: ThreeMusketeers: [user:gakshat468,2024-04-01], [user:sg0071729,2024-04-01], [user:21cs01033,2024-04-01]↵
↵
↵
B: No clue: [user:Beelzebub_blue,2024-04-01]↵
↵
↵
C: nulllösungssatz: [user:Dominater069,2024-04-01], [user:aryanc403,2024-04-01], [user:IceKnight1093,2024-04-01]↵
↵
↵
D: HR se puuch ke batayenge: [user:rivalq,2024-04-01], [user:magga,2024-04-01], [user:Kira_1234,2024-04-01]↵
↵
↵
E: nulllösungssatz: [user:Dominater069,2024-04-01], [user:aryanc403,2024-04-01], [user:IceKnight1093,2024-04-01]↵
↵
↵
F: tbd: [user:keyurchd_11,2024-04-01], [user:shiven,2024-04-01], [user:GenghizKhan,2024-04-01]↵
↵
↵
G: unforgettable playz: [user:noobcodur,2024-04-01], [user:oviyan_gandhi,2024-04-01], [user:unforgettablepl,2024-04-01]↵
↵
↵
H: HR se puuch ke batayenge: [user:rivalq,2024-04-01], [user:magga,2024-04-01], [user:Kira_1234,2024-04-01]↵
↵
↵
I: OverShadow: [user:Coder_Nayak,2024-04-01], [user:Krypto_Ray,2024-04-01], [user:sloppy_coder,2024-04-01]↵
↵
↵
J: nulllösungssatz: [user:Dominater069,2024-04-01], [user:aryanc403,2024-04-01], [user:IceKnight1093,2024-04-01]↵
↵
↵
K: nulllösungssatz: [user:Dominater069,2024-04-01], [user:aryanc403,2024-04-01], [user:IceKnight1093,2024-04-01]↵
↵
</spoiler>↵
↵
[tutorial:105064A]↵
Setter: [user:BladeRunner,2024-04-01]↵
↵
<spoiler summary="code">↵
```↵
//solution to Highly Constrained Permutation↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve()↵
{↵
int n; cin>>n;↵
vector<int> a(n+1),b(n+1);↵
↵
for(int i=1;i<=n;i++) cin>>a[i];↵
for(int i=1;i<=n;i++) cin>>b[i];↵
↵
vector<vector<int>> adj(n+1);↵
↵
//make graph in the forward direction first↵
vector<int> last(n+1);↵
for(int i=1;i<=n;i++)↵
{↵
//deal with last[a[i]-1] case↵
if(a[i]!=1)↵
{↵
if(last[a[i]-1]==0)↵
{↵
cout<<-1<<'\n';↵
return;↵
}↵
else adj[last[a[i]-1]].push_back(i);↵
}↵
//deal with the last[a[i]] case↵
if(last[a[i]] != 0) adj[i].push_back(last[a[i]]);↵
last[a[i]]=i;↵
}↵
↵
//now in the backward direction↵
vector<int> next(n+1);↵
for(int i=n;i>=1;i--)↵
{↵
//deal with next[b[i]-1] case↵
if(b[i]!=1)↵
{↵
if(next[b[i]-1]==0)↵
{↵
cout<<-1<<'\n';↵
return;↵
}↵
else adj[i].push_back(next[b[i]-1]);↵
}↵
//deal with the next[b[i]] case↵
if(next[b[i]] != 0) adj[next[b[i]]].push_back(i);↵
next[b[i]]=i;↵
}↵
↵
//so now toposort this graph↵
vector<bool> popped(n+1,false);↵
vector<int> indg(n+1);↵
queue<int> q;↵
↵
// for(int i=1;i<=n;i++)↵
// {↵
// cout<<i<<'\n';↵
// for(auto j:adj[i]) cout<<j<<' ';↵
// cout<<'\n';↵
// }↵
↵
for(int i=1;i<=n;i++)↵
{↵
for(auto j:adj[i]) indg[j]++;↵
}↵
↵
for(int i=1;i<=n;i++)↵
{↵
if(indg[i]==0) q.push(i);↵
}↵
↵
vector<int> order;↵
↵
while(!q.empty())↵
{↵
int f=q.front();↵
q.pop();↵
popped[f]=true;↵
order.push_back(f);↵
↵
for(auto nbr:adj[f]) ↵
{↵
indg[nbr]--;↵
if(indg[nbr]==0) q.push(nbr);↵
}↵
}↵
↵
if((int)order.size() < n)↵
{↵
printf("%d\n",-1);↵
return;↵
}↵
↵
vector<int> ans(n+1);↵
for(int i=0;i<n;i++) ans[order[i]]=i+1;↵
↵
for(int i=1;i<=n;i++) printf("%d ",ans[i]);↵
printf("\n");↵
}↵
↵
signed main()↵
{↵
int t; cin>>t;↵
while(t--) solve();↵
}↵
```↵
</spoiler>↵
↵
[tutorial:105064B]↵
Setter: [user:33_arsenic_75,2024-04-01], Preparation: [user:islingr,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include "bits/stdc++.h"↵
↵
using namespace std;↵
↵
int solve() {↵
int n, x;↵
cin >> n >> x;↵
↵
const int msb = x >> 10 & 1;↵
↵
if (msb == (n & 1)) return 10 * n;↵
return 10 * (n - 1) + 9;↵
}↵
↵
int main() {↵
cin.tie(nullptr)->sync_with_stdio(false);↵
↵
int t;↵
cin >> t;↵
while (t--) cout << solve() << '\n';↵
}↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064C]↵
Setter: [user:sahilkumar_1,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
↵
ll rotate(ll x,ll base,vector <ll> & info){↵
if(x<base) return x;↵
int k=0;↵
for(int i=0;i<info.size();i++){↵
if(info[i]<=x&&info[i+1]>x){↵
k=i;↵
break;↵
}↵
}↵
return (info[k]*(x%base)+(x/base));↵
}↵
↵
ll min_possible(ll x, ll base,vector <ll> & info){↵
if(x<base) return x;↵
ll ans=x;↵
for(int i=0;i<64;i++){↵
x=rotate(x,base,info);↵
ans=min(ans,x);↵
}↵
return ans;↵
}↵
↵
void solve(vector <vector <ll>> & vect){↵
int n;↵
cin >> n;↵
ll sum=0;↵
for(int i=0;i<n;i++){↵
ll x;↵
cin>>x;↵
sum+=min_possible(x,i+3,vect[i+3]);↵
}↵
cout<<sum<<endl;↵
}↵
↵
int main(){↵
int t;↵
cin >> t;↵
vector <vector <ll>> vect(1e5+3);↵
for(int i=3;i<=1e5+2;i++){↵
ll cur=1;↵
while(true){↵
vect[i].push_back(cur);↵
if(cur>1e9) break;↵
cur*=i;↵
}↵
}↵
while(t--) solve(vect);↵
}↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064D]↵
Setter: [user:ajmeraraghav99,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main()↵
{↵
long long int n,i,j;↵
cin>>n;↵
long long int marks[n+1];↵
int check[n+1];↵
for(i=1;i<=n;i++)↵
{↵
check[i]=0;↵
}↵
vector<int> v;↵
i=1;↵
while(i<=n)↵
{↵
if(v.size()==0)↵
{↵
v.push_back(i);↵
i++;↵
}↵
else↵
{↵
cout<<"? "<<v[v.size()-1]<<" "<<i<<endl;↵
fflush(stdout);↵
long long int x;↵
cin>>x;↵
marks[i]=abs(x);↵
check[i]=1;↵
if(x>0)↵
{↵
v.push_back(i);↵
}↵
else↵
{↵
v.pop_back();↵
}↵
i++;↵
↵
}↵
}↵
int honest_index=v[v.size()-1];↵
vector<pair<long long,long long>> first_half;↵
for(i=1;i<=n;i++)↵
{↵
if(i!=honest_index)↵
{↵
if(check[i])↵
{↵
first_half.push_back({-marks[i],i});↵
}↵
else↵
{↵
cout<<"? "<<honest_index<<" "<<i<<endl;↵
fflush(stdout);↵
long long int dum;↵
cin>>dum;↵
marks[i]=abs(dum);↵
check[i]=1;↵
first_half.push_back({-marks[i],i});↵
↵
}↵
}↵
}↵
sort(first_half.begin(),first_half.end());↵
int index=-1;↵
for(i=0;i<(n+1)/2;i++)↵
{↵
int dum_indx=first_half[i].second;↵
cout<<"? "<<honest_index<<" "<<dum_indx<<endl;↵
fflush(stdout);↵
long long int dum_marks;↵
cin>>dum_marks;↵
if(dum_marks>0)↵
{↵
index=dum_indx;↵
marks[index]=dum_marks;↵
break;↵
}↵
}↵
cout<<"? "<<index<<" "<<honest_index<<endl;↵
fflush(stdout);↵
long long smth;↵
cin>>smth;↵
marks[honest_index]=smth;↵
if(marks[honest_index]>marks[index])↵
{↵
↵
cout<<"! "<<honest_index<<endl;↵
}↵
else↵
{↵
↵
cout<<"! "<<index<<endl;↵
}↵
↵
↵
↵
↵
return 0;↵
} ↵
↵
```↵
</spoiler>↵
↵
[tutorial:105064E]↵
Setter: [user:Azm1t,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include "bits/stdc++.h"↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>↵
↵
void solve(){↵
↵
int n, q; cin >> n >> q;↵
↵
vector<int> c(n);↵
for(int &x: c) cin >> x, x--;↵
↵
vector<vector<int>> adj(n);↵
for(int i = 0; i < n-1; i++){↵
int u, v; cin >> u >> v; ↵
u--; v--;↵
adj[u].push_back(v);↵
adj[v].push_back(u);↵
}↵
↵
ordered_set os[n];↵
vector<int> tin(n, 0), tout(n, 0);↵
int time = 0;↵
↵
function<void(int, int)> dfs = [&](int v, int p){↵
tin[v] = time++;↵
for(int child: adj[v]){↵
if(child != p) dfs(child, v);↵
}↵
tout[v] = time++;↵
os[c[v]].insert({tin[v], v});↵
};↵
↵
dfs(0, -1);↵
↵
while(q--){↵
↵
int type, v, x; cin >> type >> v >> x;↵
v--; x--;↵
↵
if(type == 1){↵
os[c[v]].erase({tin[v], v});↵
c[v] = x;↵
os[c[v]].insert({tin[v], v});↵
}↵
else{↵
auto firstit = os[x].order_of_key({tin[v], -1});↵
auto lastit = os[x].order_of_key({tout[v], n+1});↵
cout << lastit - firstit << '\n';↵
}↵
↵
}↵
↵
}↵
↵
↵
signed main(){↵
↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int t = 1;↵
cin >> t;↵
while(t--) solve();↵
} ↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064F]↵
Setter: [user:Proelectro444,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define endl '\n'↵
↵
const int LOCATION = 4020;↵
const int MAXP = 1001;↵
const int SHIFT = 1010;↵
long long dp[MAXP][LOCATION];↵
↵
int main(){↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n, q;↵
cin >> n >> q;↵
vector<int> a(n), p(n);↵
for(int i = 0; i < n; i++){↵
cin >> a[i];↵
}↵
for(int i = 0; i < n; i++){↵
cin >> p[i];↵
}↵
for(int i = 0; i < n; i++){↵
dp[p[i]][a[i] + SHIFT] += 1ll;↵
if(p[i] != 0)↵
dp[p[i] — 1][a[i] + SHIFT] += 1ll;↵
}↵
for(int s = MAXP — 2; s >= 0; s--){↵
for(int i = 1; i < LOCATION — 1; i++){↵
dp[s][i] += dp[s + 1][i — 1] + dp[s + 1][i + 1] — (s + 2 < MAXP ? dp[s + 2][i] : 0);↵
}↵
}↵
for(int i = 0; i < MAXP; i++){↵
for(int j = 1; j < LOCATION; j++){↵
dp[i][j] += dp[i][j — 1];↵
}↵
}↵
while(q--){↵
int l, r, s;↵
cin >> l >> r >> s;↵
l += SHIFT;↵
r += SHIFT;↵
cout << dp[s][r] — dp[s][l — 1] << endl;↵
}↵
↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064G]↵
Idea:[user:Proelectro444,2024-04-01] , [user:BladeRunner,2024-04-01] Preparation: [user:Proelectro444,2024-04-01]↵
↵
<spoiler summary="code">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define endl '\n'↵
↵
bool solve(int s, int n, int k, int a[], int p[]){↵
vector<pair<int, int>> interval;↵
for (int i = 0; i < n; i++)↵
{↵
if (p[i] — s >= 0)↵
{↵
int left = a[i] — p[i] + s;↵
int right = a[i] + p[i] — s;↵
interval.push_back({left, 1});↵
interval.push_back({right + 1, -1});↵
}↵
}↵
sort(interval.begin(), interval.end());↵
int m = 0, sm = 0;↵
for (auto [_, v] : interval)↵
{↵
sm += v;↵
m = max(m, sm);↵
}↵
↵
return m <= k;↵
}↵
↵
int main(){↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int t;↵
cin >> t;↵
while (t--)↵
{↵
int n, k;↵
cin >> n >> k;↵
int a[n], p[n];↵
for (int i = 0; i < n; i++)↵
cin >> a[i];↵
for (int i = 0; i < n; i++)↵
cin >> p[i];↵
int l = 0, r = 1e9 + 10;↵
while (l <= r){↵
int mid = (l + r) / 2;↵
if (solve(mid, n, k, a, p))↵
r = mid — 1;↵
else↵
l = mid + 1;↵
}↵
cout << l << endl;↵
}↵
}↵
↵
```↵
</spoiler>↵
↵
[tutorial:105064H]↵
Setter: [user:islingr,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
#define rep(i, a, b) for (auto i{a}; i < (b); ++i)↵
#define per(i, a, b) for (auto i{b}; i-- > (a); )↵
#define sz(x) (int)(x).size()↵
#define all(x) (x).begin(), (x).end()↵
#define rall(x) (x).rbegin(), (x).rend()↵
↵
template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }↵
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }↵
↵
using ll = long long;↵
using poly = vector<ll>;↵
↵
constexpr int mod = 998'244'353, root = 62;↵
↵
int modpow(ll a, int b) {↵
ll res = 1;↵
for (; b; a = a * a % mod, b /= 2)↵
if (b & 1) res = res * a % mod;↵
return res;↵
}↵
↵
void ntt(poly &a) {↵
int n = sz(a), L = 31 — __builtin_clz(n);↵
static poly rt(2, 1);↵
for (static int k = 2, s = 2; k < n; k *= 2, s++) {↵
rt.resize(n);↵
ll z[] = {1, modpow(root, mod >> s)};↵
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;↵
}↵
vector<int> rev(n);↵
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;↵
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);↵
for (int k = 1; k < n; k *= 2)↵
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {↵
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];↵
a[i + j + k] = ai — z + (z > ai ? mod : 0);↵
ai += (ai + z >= mod ? z — mod : z);↵
}↵
}↵
poly conv(const poly &a, const poly &b) {↵
if (a.empty() || b.empty()) return {};↵
int s = sz(a) + sz(b) — 1, B = 32 — __builtin_clz(s),↵
n = 1 << B;↵
int inv = modpow(n, mod — 2);↵
poly L(a), R(b), out(n);↵
L.resize(n), R.resize(n);↵
ntt(L), ntt(R);↵
rep(i,0,n)↵
out[-i & (n — 1)] = (ll)L[i] * R[i] % mod * inv % mod;↵
ntt(out);↵
return {out.begin(), out.begin() + s};↵
}↵
↵
↵
poly operator*(const poly& a, const poly& b) {↵
return conv(a, b);↵
}↵
↵
constexpr int N = 2e5 + 10;↵
ll fac[N];↵
↵
ll mul(ll x, ll y) { return x * y % mod; }↵
↵
int main() {↵
cin.tie(nullptr)->sync_with_stdio(false);↵
↵
fac[0] = 1;↵
rep(i, 1, N) fac[i] = mul(i, fac[i - 1]);↵
↵
int n;↵
cin >> n;↵
↵
vector<ll> a(n);↵
for (auto& x : a) cin >> x;↵
↵
poly T(n);↵
for (int s = 1; s < n; ++s)↵
T[s] = mul(fac[s - 1], fac[n - s - 1]);↵
↵
vector<ll> score(n);↵
↵
auto rec = [&](const auto& self, int l, int r, const poly& T) -> poly {↵
if (r - l == 1) {↵
poly P;↵
if (l == n - 1) P = {0, 1};↵
else P = {1, a[l + 1]};↵
score[l] = (T[0] * P[0] + T[1] * P[1]) % mod;↵
return P;↵
}↵
↵
const int mid = l + (r - l) / 2;↵
↵
const poly Tr(T.begin(), T.begin() + (r - mid + 1));↵
auto Pr = self(self, mid, r, Tr);↵
↵
reverse(all(Pr));↵
auto Tl = Pr * T;↵
Tl.erase(Tl.begin(), Tl.begin() + (r - mid));↵
reverse(all(Pr));↵
↵
const auto Pl = self(self, l, mid, Tl);↵
↵
return Pl * Pr;↵
};↵
rec(rec, 1, n, T);↵
↵
const auto to_div = modpow(fac[n - 1], mod - 2);↵
rep(i, 1, n) score[i] = mul(to_div, mul(i, mul(a[i], score[i])));↵
↵
score[0] = 1;↵
for (auto x : a) score[0] = mul(score[0], x);↵
↵
rep(i, 0, n) cout << score[i] << " \n"[i == n - 1];↵
}↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064I]↵
Setter: [user:Surver,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n, k, m;↵
cin >> n >> k >> m;↵
vector<int> v(n);↵
for (int i = 0; i < n; i++) {↵
cin >> v[i];↵
}↵
vector<pair<int, int>> q(m);↵
for (int i = 0; i < m; i++) {↵
cin >> q[i].first >> q[i].second;↵
}↵
vector<int> ans(m);↵
auto calc = [&] () {↵
vector<vector<int>> suf(n + 1, vector<int>(k + 1));↵
for (int i = n — 1; i >= 0; i--) {↵
suf[i] = suf[i + 1];↵
int cost = 0, sum = 0;↵
for (int j = i; j < n; j++) {↵
cost += (v[j] > 0);↵
sum -= abs(v[j]);↵
if (cost <= k) {↵
suf[i][cost] = min(suf[i][cost], sum);↵
}↵
}↵
for (int j = 1; j <= k; j++) {↵
suf[i][j] = min(suf[i][j], suf[i][j — 1]);↵
}↵
}↵
vector<int> dp(n + 1, 1);↵
vector<int> h(n + 1, k + 1);↵
h[0] = 0;↵
for (int i = 0; i <= n; i++) {↵
if (i > 0) {↵
int cost = 0, sum = 0;↵
for (int j = i — 1; j >= 0; j--) {↵
cost += (v[j] < 0);↵
sum += abs(v[j]);↵
h[sum] = min(h[sum], cost);↵
}↵
}↵
for (int j = 0; j <= n; j++) {↵
if (h[j] <= k) {↵
dp[j] = min(dp[j], suf[i][k — h[j]]);↵
}↵
}↵
}↵
for (int i = 0; i < m; i++){↵
for (int j = 0; j <= n; j++){↵
if (dp[j] <= 0){↵
ans[i] = max(ans[i], q[i].first * j — q[i].second * dp[j]);↵
}↵
}↵
}↵
};↵
calc();↵
reverse(v.begin(), v.end());↵
calc();↵
for (int i = 0; i < m; i++){↵
cout << ans[i] << " \n"[i == m — 1];↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
[tutorial:105064J]↵
Setter: [user:BladeRunner,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include<bits/stdc++.h>↵
#define int long long↵
using namespace std;↵
↵
const int N=1e6+100;↵
const int mod = 1e9+7;↵
vector<int> fact(N+1);↵
vector<int> ifact(N+1);↵
↵
int binexp(int a,int n)↵
{↵
if(n==0) return 1;↵
else↵
{↵
int res=binexp(a,n/2);↵
res=(res*res)%mod;↵
if(n&1) res=(res*a)%mod;↵
return res;↵
}↵
}↵
↵
int ncr(int n,int r)↵
{↵
if(r>n || r<0 || n<0) return 0;↵
int ans=(fact[n]*ifact[r])%mod;↵
ans=(ans*ifact[n-r])%mod;↵
return ans;↵
}↵
↵
void solve()↵
{↵
int n,x,y; cin>>n>>x>>y;↵
int dif=abs(x-y);↵
cout<<ncr(n-2,dif-1)<<'\n';↵
}↵
↵
signed main()↵
{↵
int t; cin>>t;↵
↵
fact[0]=1;↵
for(int i=1;i<=N;i++) fact[i]=(fact[i-1]*i)%mod;↵
ifact[N]=binexp(fact[N],mod-2);↵
for(int i=N-1;i>=0;i--) ifact[i]=(ifact[i+1]*(i+1))%mod;↵
↵
while(t--) solve();↵
}↵
```↵
↵
</spoiler>↵
↵
[tutorial:105064K]↵
Setter: [user:MridulAhi,2024-04-01]↵
↵
<spoiler summary="code">↵
↵
```↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
#define rep(i, a, b) for (auto i{a}; i < (b); ++i)↵
#define per(i, a, b) for (auto i{b}; i-- > (a); )↵
#define sz(x) (int)(x).size()↵
#define all(x) (x).begin(), (x).end()↵
#define rall(x) (x).rbegin(), (x).rend()↵
↵
template <class T> bool uin(T& a, const T& b) { return a > b ? a = b, true : false; }↵
template <class T> bool uax(T& a, const T& b) { return a < b ? a = b, true : false; }↵
↵
using ll = long long;↵
↵
using U = uint32_t;↵
using poly = vector<ll>;↵
↵
constexpr int mod = 998'244'353, root = 62;↵
↵
int modpow(ll a, int b) {↵
ll res = 1;↵
for (; b; a = a * a % mod, b /= 2)↵
if (b & 1) res = res * a % mod;↵
return res;↵
}↵
↵
void ntt(poly &a) {↵
int n = sz(a), L = 31 — __builtin_clz(n);↵
static poly rt(2, 1);↵
for (static int k = 2, s = 2; k < n; k *= 2, s++) {↵
rt.resize(n);↵
ll z[] = {1, modpow(root, mod >> s)};↵
rep(i,k,2*k) rt[i] = rt[i / 2] * z[i & 1] % mod;↵
}↵
vector<int> rev(n);↵
rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;↵
rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);↵
for (int k = 1; k < n; k *= 2)↵
for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {↵
ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];↵
a[i + j + k] = ai — z + (z > ai ? mod : 0);↵
ai += (ai + z >= mod ? z — mod : z);↵
}↵
}↵
poly conv(const poly &a, const poly &b) {↵
if (a.empty() || b.empty()) return {};↵
int s = sz(a) + sz(b) — 1, B = 32 — __builtin_clz(s),↵
n = 1 << B;↵
int inv = modpow(n, mod — 2);↵
poly L(a), R(b), out(n);↵
L.resize(n), R.resize(n);↵
ntt(L), ntt(R);↵
rep(i,0,n)↵
out[-i & (n — 1)] = (ll)L[i] * R[i] % mod * inv % mod;↵
ntt(out);↵
return {out.begin(), out.begin() + s};↵
}↵
↵
constexpr int N = 1e5;↵
↵
ll mul(ll x, ll y) { return x * y % mod; }↵
↵
int fac[N], ifac[N];↵
int C(int n, int r) { return mul(fac[n], mul(ifac[r], ifac[n — r])); }↵
↵
int solve() {↵
int n, m, k;↵
cin >> n >> m >> k;↵
↵
vector<vector<int>> g(k);↵
rep(e, 0, m) {↵
char a, b;↵
cin >> a >> b;↵
const int u = a - 'a', v = b - 'a';↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
↵
vector Q(k + 1, poly(n + 1, 0));↵
for (int t = 1; t <= k; ++t)↵
for (int r = t; r <= n; ++r)↵
Q[t][r] = mul(ifac[r], C(r - 1, t - 1));↵
↵
auto merge = [&](const poly& a, const poly& b) {↵
auto c = conv(a, b);↵
c.resize(n + 1, 0);↵
return c;↵
};↵
↵
ll res = 0;↵
vector<poly> f(1 << k);↵
f[0].assign(n + 1, 0);↵
f[0][0] = 1;↵
rep(S, 1u, 1u << k) {↵
const auto root = 31 ^ __builtin_clz(S);↵
assert(S >> root & 1);↵
↵
U T = 0;↵
{↵
auto dfs = [&](const auto& self, int u) -> void {↵
T |= 1u << u;↵
for (auto v : g[u])↵
if ((~T & S) >> v & 1)↵
self(self, v);↵
};↵
dfs(dfs, root);↵
}↵
↵
const int t = popcount(T);↵
f[S] = merge(f[S ^ T], Q[t]);↵
res += f[S][n];↵
}↵
return mul(res % mod, fac[n]);↵
}↵
↵
int main() {↵
cin.tie(nullptr)->sync_with_stdio(false);↵
↵
fac[0] = 1;↵
rep(i, 1, N) fac[i] = mul(i, fac[i - 1]);↵
ifac[N - 1] = modpow(fac[N - 1], mod - 2);↵
per(i, 1, N) ifac[i - 1] = mul(i, ifac[i]);↵
↵
int t;↵
cin >> t;↵
while (t--) cout << solve() << '\n';↵
}↵
```↵
↵
</spoiler>↵
↵
