We want to mention [user:BamiTorabi,2020-11-18] and [user:amoo_safar,2020-11-18] who we thank for helping us with translating the problems and writing the tutorials.and we want to apologize for div1 A2 and B hopefully you will forgive us :( .↵
↵
[tutorial:1440A]↵
Prepared by [user:Mohammad.H915,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
// In The Name Of Allah↵
#include <bits/stdc++.h>↵
#define ss second↵
#define ff first↵
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)↵
#define ret(n) return cout << n, 0↵
#define se(n) cout << setprecision(n) << fixed↵
#define pb push_back↵
#define ll long long↵
#define ld long double↵
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
using namespace std; ↵
↵
const int N = 3e5 + 100, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;↵
typedef pair <int, int> pii;↵
↵
void solve() {↵
int n, c0, c1, t;↵
string s;↵
cin >> n >> c0 >> c1 >> t >> s;↵
int ans = 0;↵
for(auto u : s) {↵
if(u == '0') ↵
ans += min(c0, c1 + t);↵
else ↵
ans += min(c1, c0 + t);↵
}↵
cout << ans << endl;↵
}↵
↵
int32_t main() {↵
int t;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1440B]↵
Prepared by [user:Mohammad.H915,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
typedef long long int ll;↵
typedef long double ld;↵
#define pb push_back↵
#define pii pair < int , int >↵
#define F first↵
#define S second↵
#define endl '\n'↵
#define int long long↵
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)↵
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")↵
#define kill(x) return cout<<x<<'\n', 0;↵
using namespace std;↵
const int N=2e5+100;↵
ll a[N];↵
int Main(){↵
ll n, k;↵
cin >> k >> n;↵
for (int i=1;i<=n*k;i++){↵
cin >> a[i];↵
}↵
ll x=(k+1)/2 - 1;↵
x = k - x;↵
ll z=n*k+1;↵
ll ans=0;↵
while(n--){↵
z-=x;↵
if (z<=0) break;↵
ans+=a[z];↵
}↵
cout << ans << endl;↵
}↵
int32_t main(){↵
ll t;↵
cin >> t;↵
while(t--){↵
Main();↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1439A2]↵
Prepared by [user:Mohammad.H915,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
// In The Name Of Allah↵
#include <bits/stdc++.h>↵
#define ss second↵
#define ff first↵
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)↵
#define ret(n) return cout << n, 0↵
#define se(n) cout << setprecision(n) << fixed↵
#define pb push_back↵
#define ll long long↵
#define ld long double↵
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")↵
#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
using namespace std; ↵
↵
const int N = 200, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;↵
typedef pair <int, int> pii;↵
char c[N][N];↵
bool cnt[N][N];↵
↵
struct node {int x1, y1, x2, y2, x3, y3;} p[5];↵
vector <node> v;↵
↵
void upd(int x, int y, int tp, bool is) {↵
if(is)↵
v.pb({x + p[tp].x1, y + p[tp].y1, x + p[tp].x2, y + p[tp].y2, x + p[tp].x3, y + p[tp].y3});↵
else ↵
cnt[x + p[tp].x1][y + p[tp].y1] ^= 1, cnt[x + p[tp].x2][y + p[tp].y2] ^= 1, cnt[x + p[tp].x3][y + p[tp].y3] ^= 1;↵
}↵
↵
void solve() {↵
int n, m, od = 0;↵
v.clear();↵
cin >> n >> m;↵
for(int i = 1; i <= n; i++) {↵
for(int j = 1; j <= m; j++) {↵
cin >> c[i][j];↵
if(c[i][j] == '1')↵
od++, cnt[i][j] = true;↵
else↵
cnt[i][j] = false;↵
}↵
}↵
if(od == 0) {↵
cout << 0 << endl;↵
return;↵
}↵
if(n == 1 || m == 1) {↵
cout << -1 << endl;↵
return;↵
}↵
for(int i = 1; i <= n - 2; i++) {↵
for(int j = 1; j <= m; j++) {↵
if(cnt[i][j]) {↵
if(j != m) {↵
v.pb({i, j, i + 1, j, i + 1, j + 1});↵
cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j + 1] ^= 1;↵
} ↵
else {↵
v.pb({i, j, i + 1, j, i + 1, j - 1});↵
cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j - 1] ^= 1;↵
}↵
}↵
}↵
}↵
for(int i = 1; i <= m - 2; i++) {↵
if(cnt[n - 1][i]) {↵
v.pb({n - 1, i, n - 1, i + 1, n, i + 1});↵
cnt[n - 1][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; ↵
}↵
if(cnt[n][i]) {↵
v.pb({n, i, n - 1, i + 1, n, i + 1});↵
cnt[n][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; ↵
}↵
}↵
for(int msk = 0; msk < (1 << 4); msk++) {↵
for(int j = 0; j < 4; j++) ↵
if(msk & (1 << j))↵
upd(n - 1, m - 1, j, 0);↵
if(!cnt[n - 1][m - 1] && !cnt[n - 1][m] && !cnt[n][m - 1] && !cnt[n][m]) {↵
for(int j = 0; j < 4; j++) ↵
if(msk & (1 << j))↵
upd(n - 1, m - 1, j, 1);↵
break;↵
}↵
for(int j = 0; j < 4; j++)↵
if(msk & (1 << j))↵
upd(n - 1, m - 1, j, 0);↵
}↵
cout << (int)v.size() << endl;↵
for(auto u : v)↵
cout << u.x1 << " " << u.y1 << " " << u.x2 << " " << u.y2 << " " << u.x3 << " " << u.y3 << endl;↵
}↵
↵
int32_t main(){↵
use_fast;↵
p[0] = {0, 0, 0, 1, 1, 0}, p[1] = {0, 1, 0, 0, 1, 1}, p[2] = {1, 0, 1, 1, 0, 0}, p[3] = {1, 1, 0, 1, 1, 0};↵
int t;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1439B]↵
Prepared by [user:Alishahali1382,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
// In The Name Of Allah ↵
#include <bits/stdc++.h>↵
#define ss second↵
#define ff first↵
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)↵
#define se(n) cout << setprecision(n) << fixed↵
#define pb push_back↵
//#define int long long↵
#define ld long double↵
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")↵
#pragma GCC optimize("no-stack-protector,fast-math")↵
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
using namespace std; ↵
const int N = 1e5 + 100, OO = 1e9 + 7, T = 22, M = 1e9 + 7, P = 6151, SQ = 1300, lg = 22;↵
typedef pair <int, int> pii;↵
int mark[N], deg[N], ct[N];↵
bool ans[N], can[N];↵
vector <int> v[N], A;↵
vector <pii> ch[N];↵
bool cmp(int x, int y) {↵
return mark[x] < mark[y];↵
}↵
↵
void solve() {↵
int n, m, k;↵
cin >> n >> m >> k;↵
A.clear();↵
for(int i = 0; i <= n; i++)↵
v[i].clear(), ch[i].clear(), mark[i] = deg[i] = ct[i] = 0, ans[i] = can[i] = false;↵
for(int i = 0; i < m; i++) {↵
int x, y;↵
cin >> x >> y;↵
v[x].pb(y);↵
v[y].pb(x);↵
}↵
if(k > 500) {↵
cout << -1 << endl;↵
return;↵
}↵
set <pii> st;↵
for(int i = 1; i <= n; i++)↵
st.insert({deg[i] = (int)v[i].size(), i});↵
int cnt = 1;↵
while((int)st.size()) {↵
pii p = *st.begin();↵
if(p.ff >= k) {↵
cout << 1 << " " << (int)st.size() << endl;↵
for(auto u : st)↵
cout << u.ss << " ";↵
cout << endl;↵
return;↵
}↵
else {↵
st.erase(p);↵
mark[p.ss] = cnt;↵
for(auto u : v[p.ss])↵
if(!mark[u])↵
st.erase({deg[u], u}), st.insert({--deg[u], u});↵
A.pb(p.ss);↵
}↵
cnt++;↵
}↵
for(auto i : A) {↵
int nxt = 0;↵
for(auto u : v[i]) ↵
if(mark[u] > mark[i])↵
ct[nxt++] = u, can[u] = true;↵
for(auto u : ch[i]) ↵
if(!can[u.ff])↵
ans[u.ss] = false;↵
for(int j = 0; j < nxt; j++)↵
can[ct[j]] = false;↵
if(nxt != k - 1)↵
continue;↵
ans[i] = true;↵
sort(ct, ct + nxt, cmp);↵
for(int j = 0; j < nxt; j++)↵
for(int k = j + 1; k < nxt; k++)↵
ch[ct[j]].pb({ct[k], i});↵
}↵
for(auto i : A) {↵
if(!ans[i])↵
continue;↵
cout << 2 << endl;↵
cout << i << " ";↵
for(auto u : v[i])↵
if(mark[u] > mark[i])↵
cout << u << " ";↵
cout << endl;↵
return;↵
}↵
cout << -1 << endl;↵
return;↵
}↵
↵
int32_t main() {↵
use_fast;↵
int t;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
[tutorial:1439C]↵
prepared by [user:Mehrdad_sohrabi,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
↵
using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵
↵
const int inf=1000000010;↵
const ll INF=10000000000000010LL;↵
const int mod=1000000007;↵
const int MAXN=200010, LOG=20;↵
↵
ll n, m, k, u, v, x, y, t, a, b, ans;↵
ll A[MAXN];↵
ll seg[MAXN<<2], lazy[MAXN<<2];↵
int Mn[MAXN<<2], Mx[MAXN<<2];↵
↵
void Build(int id, int tl, int tr){↵
if (tr-tl==1){↵
Mn[id]=Mx[id]=seg[id]=A[tl];↵
return ;↵
}↵
int mid=(tl+tr)>>1;↵
Build(id<<1, tl, mid);↵
Build(id<<1 | 1, mid, tr);↵
Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);↵
Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);↵
seg[id]=seg[id<<1] + seg[id<<1 | 1]; ↵
}↵
inline void add_lazy(int id, int len, ll val){↵
Mn[id]=val;↵
Mx[id]=val;↵
lazy[id]=val;↵
seg[id]=len*val;↵
}↵
inline void shift(int id, int tl, int tr){↵
if (!lazy[id]) return ;↵
int mid=(tl+tr)>>1;↵
add_lazy(id<<1, mid-tl, lazy[id]);↵
add_lazy(id<<1 | 1, tr-mid, lazy[id]);↵
lazy[id]=0;↵
}↵
void Maximize(int id, int tl, int tr, int pos, ll val){↵
if (pos<=tl || val<=Mn[id]) return ;↵
if (tr<=pos && Mx[id]<=val){↵
add_lazy(id, tr-tl, val);↵
return ;↵
}↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1;↵
Maximize(id<<1, tl, mid, pos, val);↵
Maximize(id<<1 | 1, mid, tr, pos, val);↵
Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);↵
Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);↵
seg[id]=seg[id<<1] + seg[id<<1 | 1];↵
}↵
int BS1(int id, int tl, int tr, int pos, ll val){↵
if (tr<=pos || val<Mn[id]) return tr;↵
if (tr-tl==1) return tl;↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1, tmp=BS1(id<<1, tl, mid, pos, val);↵
if (tmp==mid) return BS1(id<<1 | 1, mid, tr, pos, val);↵
return tmp;↵
}↵
int BS2(int id, int tl, int tr, ll val){↵
if (seg[id]<=val) return tr;↵
if (tr-tl==1) return tl;↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1, tmp=BS2(id<<1, tl, mid, val);↵
if (tmp<mid) return tmp;↵
return BS2(id<<1 | 1, mid, tr, val-seg[id<<1]);↵
}↵
ll Get(int id, int tl, int tr, int l, int r){↵
if (r<=tl || tr<=l) return 0;↵
if (l<=tl && tr<=r) return seg[id];↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1;↵
return Get(id<<1, tl, mid, l, r) + Get(id<<1 | 1, mid, tr, l, r);↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
cin>>n>>m;↵
for (int i=1; i<=n; i++) cin>>A[i];↵
Build(1, 1, n+1);↵
while (m--){↵
cin>>t>>x>>y;↵
if (t==1) Maximize(1, 1, n+1, x+1, y);↵
else{↵
ans=0;↵
while (1){↵
x=BS1(1, 1, n+1, x, y);↵
if (x==n+1) break ;↵
ll val=y+Get(1, 1, n+1, 1, x);↵
int xx=BS2(1, 1, n+1, val);↵
// buy [x, xx)↵
ans+=xx-x;↵
y-=Get(1, 1, n+1, x, xx);↵
x=xx;↵
}↵
cout<<ans<<"\n";↵
}↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:1439D]↵
prepared by [user:Mehrdad_sohrabi,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
↵
using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵
↵
const ld eps=1e-7;↵
const int inf=1000000010;↵
const ll INF=10000000000000010LL;↵
const int MAXN=505, LOG=20;↵
↵
ll n, m, k, u, v, x, y, t, a, b, ans, mod;↵
ll dp1[MAXN], dp2[MAXN];↵
ll dp3[MAXN][MAXN], dp4[MAXN][MAXN];↵
ll C[MAXN][MAXN];↵
↵
int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
cin>>n>>m>>mod;↵
↵
for (int i=0; i<MAXN; i++){↵
C[i][0]=C[i][i]=1;↵
for (int j=1; j<i; j++) C[i][j]=(C[i-1][j] + C[i-1][j-1])%mod;↵
}↵
dp1[0]=1;↵
for (int n=1; n<MAXN; n++){↵
for (int i=1; i<=n; i++) dp1[n]=(dp1[n] + dp1[i-1]*dp1[n-i]%mod*C[n-1][i-1])%mod;↵
dp1[n]=(n+1)*dp1[n]%mod;↵
for (int i=1; i<=n; i++){↵
dp2[n]=(dp2[n] + (n+1)*C[n-1][i-1]%mod*((dp1[i-1]*dp2[n-i] + dp2[i-1]*dp1[n-i])%mod))%mod;↵
dp2[n]=(dp2[n] + C[n-1][i-1]*dp1[i-1]%mod*dp1[n-i]%mod*((i*(i-1)/2+(n-i)*(n-i+1)/2)%mod))%mod;↵
}↵
}↵
↵
dp3[0][0]=1;↵
for (int n=1; n<MAXN; n++){↵
for (int m=0; m<n; m++){↵
dp3[n][m]=dp3[n-1][m];↵
dp4[n][m]=dp4[n-1][m];↵
for (int i=1; i<=m; i++){↵
dp3[n][m]=(dp3[n][m] + dp3[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;↵
dp4[n][m]=(dp4[n][m] + dp3[n-i-1][m-i]*dp2[i]%mod*C[m][i])%mod;↵
dp4[n][m]=(dp4[n][m] + dp4[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;↵
}↵
}↵
dp3[n][n]=dp1[n];↵
dp4[n][n]=dp2[n];↵
}↵
↵
cout<<dp4[n][m]<<"\n"; ↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="O(n2) solution">↵
↵
~~~~~↵
// And you curse yourself for things you never done↵
// Shayan.P 2020-08-29↵
↵
#include<bits/stdc++.h>↵
↵
#define F first↵
#define S second↵
#define PB push_back↵
#define sz(s) int((s).size())↵
#define bit(n,k) (((n)>>(k))&1)↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int,int> pii;↵
↵
const int maxn = 510, inf = 1e9 + 10, mod=1e9+7;↵
↵
ll n, m;↵
↵
ll Pow(ll a, ll b){↵
b = (b + (mod-1)) % (mod-1); // to handle b == -1↵
int ans=1;↵
for(; b; b>>=1, a=a*a%mod) if (b&1) ans=ans*a%mod;↵
return ans;↵
}↵
inline void add(ll &a, ll b){↵
a = (a + b) % mod;↵
}↵
↵
ll fac[maxn], ifac[maxn];↵
↵
ll C(ll n, ll k){↵
if (n<k || k<0) return 0;↵
return fac[n]*ifac[k]%mod*ifac[n-k]%mod;↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();↵
↵
fac[0] = 1;↵
for(int i = 1; i < maxn; i++) fac[i]=fac[i-1]*i%mod;↵
ifac[maxn-1] = Pow(fac[maxn-1], mod-2);↵
for(int i = maxn-2; i >= 0; i--) ifac[i]=ifac[i+1]*(i+1)%mod;↵
↵
cin >> n >> m;↵
++n; //!↵
↵
int ans = 0;↵
for(ll bef = 0; bef < m; bef++){↵
for(ll w = 1; w + bef < m; w++){ // corner case : bef == 0↵
ll cnt1=Pow(w+1, w-1)*Pow(2, w)%mod;↵
ll cnt2=Pow(n-w-1, bef-1)*Pow(2, bef)%mod*(n-w-1-bef)%mod;↵
ll cnt=cnt1*cnt2%mod*C(w+bef, bef)%mod;↵
ll score=w*(w+1)%mod*n%mod;↵
ll after=Pow(n, m-bef-w-1)*Pow(2, m-bef-w-1) % mod;↵
ans=(ans + cnt*score%mod*after) % mod;↵
}↵
} ↵
cout << 1ll * (n-m) * ans % mod * Pow(n, -1) % mod << "\n";↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:1439E]↵
will be ready soon.↵
↵
Prepared by [user:Alishahali1382,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
↵
using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵
↵
const ld eps=1e-7;↵
const int inf=1000000010;↵
const ll INF=10000000000000010LL;↵
const int mod=1000000007;↵
const int MAXN=400010, LOG=30;↵
↵
int n, m, k, u, v, x, y, t, a, b, root, ans;↵
pii A[MAXN], V[MAXN];↵
int par[MAXN], sum[MAXN];↵
bool is[MAXN];↵
vector<int> G[MAXN], grundy;↵
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵
↵
inline int GetH(pii p){ return p.first+p.second;}↵
inline pii GetPar(pii p, int k){↵
int x=p.first, y=p.second;↵
while (k){↵
int xx=(x&-x), yy=(y&-y);↵
if (!xx) xx=2*inf;↵
if (!yy) yy=2*inf;↵
int tmp=min(k, min(xx, yy));↵
k-=tmp;↵
if (xx<yy) x-=tmp;↵
else y-=tmp;↵
}↵
return {x, y};↵
}↵
inline int Zone(pii p, int n){↵
if (p.first&(1<<(n-1))) return 2;↵
if (p.second&(1<<(n-1))) return 1;↵
return 0;↵
}↵
void dfs_order(vector<pii> &vec, int n=LOG) {↵
if (n==0 || vec.size()==0) return ;↵
vector<pii> v[3];↵
for (pii p:vec) {↵
int z=Zone(p, n);↵
p.first&=(1<<(n-1))-1;↵
p.second&=(1<<(n-1))-1;↵
v[z].pb(p);↵
}↵
vec.clear();↵
for (int i:{0, 1, 2}) dfs_order(v[i], n-1);↵
for (pii p:v[0]) if (!p.first) vec.pb(p);↵
for (pii p:v[1]) vec.pb({p.first, p.second|(1<<(n-1))});↵
for (pii p:v[0]) if (p.first) vec.pb(p);↵
for (pii p:v[2]) vec.pb({p.first|(1<<(n-1)), p.second});↵
}↵
pii Lca(pii u, pii v, int n=LOG) {↵
if (n==0) return {0, 0};↵
int zu = Zone(u, n), zv = Zone(v, n);↵
if (zu > zv) swap(u, v), swap(zu, zv);↵
u.first&=(1<<(n-1))-1;↵
u.second&=(1<<(n-1))-1;↵
v.first&=(1<<(n-1))-1;↵
v.second&=(1<<(n-1))-1;↵
if (zu == 1 && zv == 2) return {0, 0};↵
if (zu == 2 && zv == 2){↵
pii A = Lca(u, v, n-1);↵
return {A.first+(1<<(n-1)), A.second};↵
}↵
if (zu == 1 && zv == 1) {↵
pii A = Lca(u, v, n-1);↵
return {A.first, A.second+(1<<(n-1))};↵
}↵
if (zv == 1) return Lca(u, {0, (1<<(n-1))-1}, n-1);↵
if (zv == 2) return Lca(u, {(1<<(n-1))-1, 0}, n-1);↵
return Lca(u, v, n-1);↵
}↵
inline int GetId(pii p){↵
return lower_bound(V, V+n, p)-V;↵
}↵
inline bool IsPar(pii u, pii v){↵
if (GetH(u)>GetH(v)) return 0;↵
return GetPar(v, GetH(v)-GetH(u))==u;↵
}↵
int dfs(int node){↵
for (int v:G[node]) sum[node]+=dfs(v);↵
return sum[node];↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
vector<pii> vec;↵
cin>>m;↵
for (int i=0; i<2*m; i++) cin>>A[i].first>>A[i].second, vec.pb(A[i]);↵
sort(all(vec));↵
vec.resize(unique(all(vec))-vec.begin());↵
dfs_order(vec);↵
for (int i=vec.size()-1; i; i--) vec.pb(Lca(vec[i], vec[i-1]));↵
sort(all(vec));↵
vec.resize(unique(all(vec))-vec.begin());↵
dfs_order(vec);↵
n=vec.size();↵
↵
debug("sorted")↵
↵
for (int i=0; i<n; i++) V[i]=vec[i];↵
sort(V, V+n);↵
vector<int> stk={root=GetId(vec[0])};↵
for (int i=1; i<n; i++){↵
int v=GetId(vec[i]);↵
while (!IsPar(V[stk.back()], V[v])) stk.pop_back();↵
par[v]=stk.back();↵
G[stk.back()].pb(v);↵
stk.pb(v); ↵
}↵
↵
for (int i=0; i<2*m; i+=2){↵
int u=GetId(A[i]), v=GetId(A[i+1]), lca=GetId(Lca(A[i], A[i+1]));↵
sum[u]++;↵
sum[v]++;↵
sum[lca]-=2;↵
is[lca]=1;↵
}↵
dfs(root);↵
for (int v=0; v<n; v++){↵
if (sum[v]){↵
grundy.pb(GetH(V[par[v]])+1);↵
grundy.pb(GetH(V[v])+1);↵
}↵
else if (is[v]){↵
grundy.pb(GetH(V[v]));↵
grundy.pb(GetH(V[v])+1);↵
}↵
}↵
sort(all(grundy));↵
vec.clear();↵
int last=-1;↵
for (int x:grundy){↵
if (last==-1){↵
if (vec.empty() || vec.back().second<x) last=x;↵
else{↵
last=vec.back().first;↵
vec.pop_back();↵
}↵
}↵
else{↵
if (last<x) vec.pb({last, x});↵
last=-1;↵
}↵
}↵
ans=2*vec.size();↵
if (ans && vec[0].first==0) ans--;↵
cout<<ans<<"\n";↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
[tutorial:1440A]↵
Prepared by [user:Mohammad.H915,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
// In The Name Of Allah↵
#include <bits/stdc++.h>↵
#define ss second↵
#define ff first↵
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)↵
#define ret(n) return cout << n, 0↵
#define se(n) cout << setprecision(n) << fixed↵
#define pb push_back↵
#define ll long long↵
#define ld long double↵
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
using namespace std; ↵
↵
const int N = 3e5 + 100, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;↵
typedef pair <int, int> pii;↵
↵
void solve() {↵
int n, c0, c1, t;↵
string s;↵
cin >> n >> c0 >> c1 >> t >> s;↵
int ans = 0;↵
for(auto u : s) {↵
if(u == '0') ↵
ans += min(c0, c1 + t);↵
else ↵
ans += min(c1, c0 + t);↵
}↵
cout << ans << endl;↵
}↵
↵
int32_t main() {↵
int t;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1440B]↵
Prepared by [user:Mohammad.H915,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
typedef long long int ll;↵
typedef long double ld;↵
#define pb push_back↵
#define pii pair < int , int >↵
#define F first↵
#define S second↵
#define endl '\n'↵
#define int long long↵
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)↵
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")↵
#define kill(x) return cout<<x<<'\n', 0;↵
using namespace std;↵
const int N=2e5+100;↵
ll a[N];↵
int Main(){↵
ll n, k;↵
cin >> k >> n;↵
for (int i=1;i<=n*k;i++){↵
cin >> a[i];↵
}↵
ll x=(k+1)/2 - 1;↵
x = k - x;↵
ll z=n*k+1;↵
ll ans=0;↵
while(n--){↵
z-=x;↵
if (z<=0) break;↵
ans+=a[z];↵
}↵
cout << ans << endl;↵
}↵
int32_t main(){↵
ll t;↵
cin >> t;↵
while(t--){↵
Main();↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1439A2]↵
Prepared by [user:Mohammad.H915,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
// In The Name Of Allah↵
#include <bits/stdc++.h>↵
#define ss second↵
#define ff first↵
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)↵
#define ret(n) return cout << n, 0↵
#define se(n) cout << setprecision(n) << fixed↵
#define pb push_back↵
#define ll long long↵
#define ld long double↵
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")↵
#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
using namespace std; ↵
↵
const int N = 200, OO = 1e9 + 7, T = 50, M = 1e9 + 7, P = 6151, SQ = 280, lg = 20;↵
typedef pair <int, int> pii;↵
char c[N][N];↵
bool cnt[N][N];↵
↵
struct node {int x1, y1, x2, y2, x3, y3;} p[5];↵
vector <node> v;↵
↵
void upd(int x, int y, int tp, bool is) {↵
if(is)↵
v.pb({x + p[tp].x1, y + p[tp].y1, x + p[tp].x2, y + p[tp].y2, x + p[tp].x3, y + p[tp].y3});↵
else ↵
cnt[x + p[tp].x1][y + p[tp].y1] ^= 1, cnt[x + p[tp].x2][y + p[tp].y2] ^= 1, cnt[x + p[tp].x3][y + p[tp].y3] ^= 1;↵
}↵
↵
void solve() {↵
int n, m, od = 0;↵
v.clear();↵
cin >> n >> m;↵
for(int i = 1; i <= n; i++) {↵
for(int j = 1; j <= m; j++) {↵
cin >> c[i][j];↵
if(c[i][j] == '1')↵
od++, cnt[i][j] = true;↵
else↵
cnt[i][j] = false;↵
}↵
}↵
if(od == 0) {↵
cout << 0 << endl;↵
return;↵
}↵
if(n == 1 || m == 1) {↵
cout << -1 << endl;↵
return;↵
}↵
for(int i = 1; i <= n - 2; i++) {↵
for(int j = 1; j <= m; j++) {↵
if(cnt[i][j]) {↵
if(j != m) {↵
v.pb({i, j, i + 1, j, i + 1, j + 1});↵
cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j + 1] ^= 1;↵
} ↵
else {↵
v.pb({i, j, i + 1, j, i + 1, j - 1});↵
cnt[i][j] ^= 1, cnt[i + 1][j] ^= 1, cnt[i + 1][j - 1] ^= 1;↵
}↵
}↵
}↵
}↵
for(int i = 1; i <= m - 2; i++) {↵
if(cnt[n - 1][i]) {↵
v.pb({n - 1, i, n - 1, i + 1, n, i + 1});↵
cnt[n - 1][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; ↵
}↵
if(cnt[n][i]) {↵
v.pb({n, i, n - 1, i + 1, n, i + 1});↵
cnt[n][i] ^= 1, cnt[n - 1][i + 1] ^= 1, cnt[n][i + 1] ^= 1; ↵
}↵
}↵
for(int msk = 0; msk < (1 << 4); msk++) {↵
for(int j = 0; j < 4; j++) ↵
if(msk & (1 << j))↵
upd(n - 1, m - 1, j, 0);↵
if(!cnt[n - 1][m - 1] && !cnt[n - 1][m] && !cnt[n][m - 1] && !cnt[n][m]) {↵
for(int j = 0; j < 4; j++) ↵
if(msk & (1 << j))↵
upd(n - 1, m - 1, j, 1);↵
break;↵
}↵
for(int j = 0; j < 4; j++)↵
if(msk & (1 << j))↵
upd(n - 1, m - 1, j, 0);↵
}↵
cout << (int)v.size() << endl;↵
for(auto u : v)↵
cout << u.x1 << " " << u.y1 << " " << u.x2 << " " << u.y2 << " " << u.x3 << " " << u.y3 << endl;↵
}↵
↵
int32_t main(){↵
use_fast;↵
p[0] = {0, 0, 0, 1, 1, 0}, p[1] = {0, 1, 0, 0, 1, 1}, p[2] = {1, 0, 1, 1, 0, 0}, p[3] = {1, 1, 0, 1, 1, 0};↵
int t;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
[tutorial:1439B]↵
Prepared by [user:Alishahali1382,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
// In The Name Of Allah ↵
#include <bits/stdc++.h>↵
#define ss second↵
#define ff first↵
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)↵
#define se(n) cout << setprecision(n) << fixed↵
#define pb push_back↵
//#define int long long↵
#define ld long double↵
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")↵
#pragma GCC optimize("no-stack-protector,fast-math")↵
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
using namespace std; ↵
const int N = 1e5 + 100, OO = 1e9 + 7, T = 22, M = 1e9 + 7, P = 6151, SQ = 1300, lg = 22;↵
typedef pair <int, int> pii;↵
int mark[N], deg[N], ct[N];↵
bool ans[N], can[N];↵
vector <int> v[N], A;↵
vector <pii> ch[N];↵
bool cmp(int x, int y) {↵
return mark[x] < mark[y];↵
}↵
↵
void solve() {↵
int n, m, k;↵
cin >> n >> m >> k;↵
A.clear();↵
for(int i = 0; i <= n; i++)↵
v[i].clear(), ch[i].clear(), mark[i] = deg[i] = ct[i] = 0, ans[i] = can[i] = false;↵
for(int i = 0; i < m; i++) {↵
int x, y;↵
cin >> x >> y;↵
v[x].pb(y);↵
v[y].pb(x);↵
}↵
if(k > 500) {↵
cout << -1 << endl;↵
return;↵
}↵
set <pii> st;↵
for(int i = 1; i <= n; i++)↵
st.insert({deg[i] = (int)v[i].size(), i});↵
int cnt = 1;↵
while((int)st.size()) {↵
pii p = *st.begin();↵
if(p.ff >= k) {↵
cout << 1 << " " << (int)st.size() << endl;↵
for(auto u : st)↵
cout << u.ss << " ";↵
cout << endl;↵
return;↵
}↵
else {↵
st.erase(p);↵
mark[p.ss] = cnt;↵
for(auto u : v[p.ss])↵
if(!mark[u])↵
st.erase({deg[u], u}), st.insert({--deg[u], u});↵
A.pb(p.ss);↵
}↵
cnt++;↵
}↵
for(auto i : A) {↵
int nxt = 0;↵
for(auto u : v[i]) ↵
if(mark[u] > mark[i])↵
ct[nxt++] = u, can[u] = true;↵
for(auto u : ch[i]) ↵
if(!can[u.ff])↵
ans[u.ss] = false;↵
for(int j = 0; j < nxt; j++)↵
can[ct[j]] = false;↵
if(nxt != k - 1)↵
continue;↵
ans[i] = true;↵
sort(ct, ct + nxt, cmp);↵
for(int j = 0; j < nxt; j++)↵
for(int k = j + 1; k < nxt; k++)↵
ch[ct[j]].pb({ct[k], i});↵
}↵
for(auto i : A) {↵
if(!ans[i])↵
continue;↵
cout << 2 << endl;↵
cout << i << " ";↵
for(auto u : v[i])↵
if(mark[u] > mark[i])↵
cout << u << " ";↵
cout << endl;↵
return;↵
}↵
cout << -1 << endl;↵
return;↵
}↵
↵
int32_t main() {↵
use_fast;↵
int t;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
[tutorial:1439C]↵
prepared by [user:Mehrdad_sohrabi,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
↵
using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵
↵
const int inf=1000000010;↵
const ll INF=10000000000000010LL;↵
const int mod=1000000007;↵
const int MAXN=200010, LOG=20;↵
↵
ll n, m, k, u, v, x, y, t, a, b, ans;↵
ll A[MAXN];↵
ll seg[MAXN<<2], lazy[MAXN<<2];↵
int Mn[MAXN<<2], Mx[MAXN<<2];↵
↵
void Build(int id, int tl, int tr){↵
if (tr-tl==1){↵
Mn[id]=Mx[id]=seg[id]=A[tl];↵
return ;↵
}↵
int mid=(tl+tr)>>1;↵
Build(id<<1, tl, mid);↵
Build(id<<1 | 1, mid, tr);↵
Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);↵
Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);↵
seg[id]=seg[id<<1] + seg[id<<1 | 1]; ↵
}↵
inline void add_lazy(int id, int len, ll val){↵
Mn[id]=val;↵
Mx[id]=val;↵
lazy[id]=val;↵
seg[id]=len*val;↵
}↵
inline void shift(int id, int tl, int tr){↵
if (!lazy[id]) return ;↵
int mid=(tl+tr)>>1;↵
add_lazy(id<<1, mid-tl, lazy[id]);↵
add_lazy(id<<1 | 1, tr-mid, lazy[id]);↵
lazy[id]=0;↵
}↵
void Maximize(int id, int tl, int tr, int pos, ll val){↵
if (pos<=tl || val<=Mn[id]) return ;↵
if (tr<=pos && Mx[id]<=val){↵
add_lazy(id, tr-tl, val);↵
return ;↵
}↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1;↵
Maximize(id<<1, tl, mid, pos, val);↵
Maximize(id<<1 | 1, mid, tr, pos, val);↵
Mn[id]=min(Mn[id<<1], Mn[id<<1 | 1]);↵
Mx[id]=max(Mx[id<<1], Mx[id<<1 | 1]);↵
seg[id]=seg[id<<1] + seg[id<<1 | 1];↵
}↵
int BS1(int id, int tl, int tr, int pos, ll val){↵
if (tr<=pos || val<Mn[id]) return tr;↵
if (tr-tl==1) return tl;↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1, tmp=BS1(id<<1, tl, mid, pos, val);↵
if (tmp==mid) return BS1(id<<1 | 1, mid, tr, pos, val);↵
return tmp;↵
}↵
int BS2(int id, int tl, int tr, ll val){↵
if (seg[id]<=val) return tr;↵
if (tr-tl==1) return tl;↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1, tmp=BS2(id<<1, tl, mid, val);↵
if (tmp<mid) return tmp;↵
return BS2(id<<1 | 1, mid, tr, val-seg[id<<1]);↵
}↵
ll Get(int id, int tl, int tr, int l, int r){↵
if (r<=tl || tr<=l) return 0;↵
if (l<=tl && tr<=r) return seg[id];↵
shift(id, tl, tr);↵
int mid=(tl+tr)>>1;↵
return Get(id<<1, tl, mid, l, r) + Get(id<<1 | 1, mid, tr, l, r);↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
cin>>n>>m;↵
for (int i=1; i<=n; i++) cin>>A[i];↵
Build(1, 1, n+1);↵
while (m--){↵
cin>>t>>x>>y;↵
if (t==1) Maximize(1, 1, n+1, x+1, y);↵
else{↵
ans=0;↵
while (1){↵
x=BS1(1, 1, n+1, x, y);↵
if (x==n+1) break ;↵
ll val=y+Get(1, 1, n+1, 1, x);↵
int xx=BS2(1, 1, n+1, val);↵
// buy [x, xx)↵
ans+=xx-x;↵
y-=Get(1, 1, n+1, x, xx);↵
x=xx;↵
}↵
cout<<ans<<"\n";↵
}↵
}↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:1439D]↵
prepared by [user:Mehrdad_sohrabi,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
↵
using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵
↵
const ld eps=1e-7;↵
const int inf=1000000010;↵
const ll INF=10000000000000010LL;↵
const int MAXN=505, LOG=20;↵
↵
ll n, m, k, u, v, x, y, t, a, b, ans, mod;↵
ll dp1[MAXN], dp2[MAXN];↵
ll dp3[MAXN][MAXN], dp4[MAXN][MAXN];↵
ll C[MAXN][MAXN];↵
↵
int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
cin>>n>>m>>mod;↵
↵
for (int i=0; i<MAXN; i++){↵
C[i][0]=C[i][i]=1;↵
for (int j=1; j<i; j++) C[i][j]=(C[i-1][j] + C[i-1][j-1])%mod;↵
}↵
dp1[0]=1;↵
for (int n=1; n<MAXN; n++){↵
for (int i=1; i<=n; i++) dp1[n]=(dp1[n] + dp1[i-1]*dp1[n-i]%mod*C[n-1][i-1])%mod;↵
dp1[n]=(n+1)*dp1[n]%mod;↵
for (int i=1; i<=n; i++){↵
dp2[n]=(dp2[n] + (n+1)*C[n-1][i-1]%mod*((dp1[i-1]*dp2[n-i] + dp2[i-1]*dp1[n-i])%mod))%mod;↵
dp2[n]=(dp2[n] + C[n-1][i-1]*dp1[i-1]%mod*dp1[n-i]%mod*((i*(i-1)/2+(n-i)*(n-i+1)/2)%mod))%mod;↵
}↵
}↵
↵
dp3[0][0]=1;↵
for (int n=1; n<MAXN; n++){↵
for (int m=0; m<n; m++){↵
dp3[n][m]=dp3[n-1][m];↵
dp4[n][m]=dp4[n-1][m];↵
for (int i=1; i<=m; i++){↵
dp3[n][m]=(dp3[n][m] + dp3[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;↵
dp4[n][m]=(dp4[n][m] + dp3[n-i-1][m-i]*dp2[i]%mod*C[m][i])%mod;↵
dp4[n][m]=(dp4[n][m] + dp4[n-i-1][m-i]*dp1[i]%mod*C[m][i])%mod;↵
}↵
}↵
dp3[n][n]=dp1[n];↵
dp4[n][n]=dp2[n];↵
}↵
↵
cout<<dp4[n][m]<<"\n"; ↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="O(n2) solution">↵
↵
~~~~~↵
// And you curse yourself for things you never done↵
// Shayan.P 2020-08-29↵
↵
#include<bits/stdc++.h>↵
↵
#define F first↵
#define S second↵
#define PB push_back↵
#define sz(s) int((s).size())↵
#define bit(n,k) (((n)>>(k))&1)↵
↵
using namespace std;↵
↵
typedef long long ll;↵
typedef pair<int,int> pii;↵
↵
const int maxn = 510, inf = 1e9 + 10, mod=1e9+7;↵
↵
ll n, m;↵
↵
ll Pow(ll a, ll b){↵
b = (b + (mod-1)) % (mod-1); // to handle b == -1↵
int ans=1;↵
for(; b; b>>=1, a=a*a%mod) if (b&1) ans=ans*a%mod;↵
return ans;↵
}↵
inline void add(ll &a, ll b){↵
a = (a + b) % mod;↵
}↵
↵
ll fac[maxn], ifac[maxn];↵
↵
ll C(ll n, ll k){↵
if (n<k || k<0) return 0;↵
return fac[n]*ifac[k]%mod*ifac[n-k]%mod;↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();↵
↵
fac[0] = 1;↵
for(int i = 1; i < maxn; i++) fac[i]=fac[i-1]*i%mod;↵
ifac[maxn-1] = Pow(fac[maxn-1], mod-2);↵
for(int i = maxn-2; i >= 0; i--) ifac[i]=ifac[i+1]*(i+1)%mod;↵
↵
cin >> n >> m;↵
++n; //!↵
↵
int ans = 0;↵
for(ll bef = 0; bef < m; bef++){↵
for(ll w = 1; w + bef < m; w++){ // corner case : bef == 0↵
ll cnt1=Pow(w+1, w-1)*Pow(2, w)%mod;↵
ll cnt2=Pow(n-w-1, bef-1)*Pow(2, bef)%mod*(n-w-1-bef)%mod;↵
ll cnt=cnt1*cnt2%mod*C(w+bef, bef)%mod;↵
ll score=w*(w+1)%mod*n%mod;↵
ll after=Pow(n, m-bef-w-1)*Pow(2, m-bef-w-1) % mod;↵
ans=(ans + cnt*score%mod*after) % mod;↵
}↵
} ↵
cout << 1ll * (n-m) * ans % mod * Pow(n, -1) % mod << "\n";↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[tutorial:1439E]↵
will be ready soon.↵
↵
Prepared by [user:Alishahali1382,2020-11-18]↵
↵
<spoiler summary="official solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#pragma GCC optimize ("O2,unroll-loops")↵
//#pragma GCC optimize("no-stack-protector,fast-math")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")↵
↵
using namespace std;↵
typedef long long ll;↵
typedef long double ld;↵
typedef pair<int, int> pii;↵
typedef pair<pii, int> piii;↵
typedef pair<ll, ll> pll;↵
#define debug(x) cerr<<#x<<'='<<(x)<<endl;↵
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;↵
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;↵
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}↵
#define all(x) x.begin(), x.end()↵
#define pb push_back↵
#define kill(x) return cout<<x<<'\n', 0;↵
↵
const ld eps=1e-7;↵
const int inf=1000000010;↵
const ll INF=10000000000000010LL;↵
const int mod=1000000007;↵
const int MAXN=400010, LOG=30;↵
↵
int n, m, k, u, v, x, y, t, a, b, root, ans;↵
pii A[MAXN], V[MAXN];↵
int par[MAXN], sum[MAXN];↵
bool is[MAXN];↵
vector<int> G[MAXN], grundy;↵
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵
↵
inline int GetH(pii p){ return p.first+p.second;}↵
inline pii GetPar(pii p, int k){↵
int x=p.first, y=p.second;↵
while (k){↵
int xx=(x&-x), yy=(y&-y);↵
if (!xx) xx=2*inf;↵
if (!yy) yy=2*inf;↵
int tmp=min(k, min(xx, yy));↵
k-=tmp;↵
if (xx<yy) x-=tmp;↵
else y-=tmp;↵
}↵
return {x, y};↵
}↵
inline int Zone(pii p, int n){↵
if (p.first&(1<<(n-1))) return 2;↵
if (p.second&(1<<(n-1))) return 1;↵
return 0;↵
}↵
void dfs_order(vector<pii> &vec, int n=LOG) {↵
if (n==0 || vec.size()==0) return ;↵
vector<pii> v[3];↵
for (pii p:vec) {↵
int z=Zone(p, n);↵
p.first&=(1<<(n-1))-1;↵
p.second&=(1<<(n-1))-1;↵
v[z].pb(p);↵
}↵
vec.clear();↵
for (int i:{0, 1, 2}) dfs_order(v[i], n-1);↵
for (pii p:v[0]) if (!p.first) vec.pb(p);↵
for (pii p:v[1]) vec.pb({p.first, p.second|(1<<(n-1))});↵
for (pii p:v[0]) if (p.first) vec.pb(p);↵
for (pii p:v[2]) vec.pb({p.first|(1<<(n-1)), p.second});↵
}↵
pii Lca(pii u, pii v, int n=LOG) {↵
if (n==0) return {0, 0};↵
int zu = Zone(u, n), zv = Zone(v, n);↵
if (zu > zv) swap(u, v), swap(zu, zv);↵
u.first&=(1<<(n-1))-1;↵
u.second&=(1<<(n-1))-1;↵
v.first&=(1<<(n-1))-1;↵
v.second&=(1<<(n-1))-1;↵
if (zu == 1 && zv == 2) return {0, 0};↵
if (zu == 2 && zv == 2){↵
pii A = Lca(u, v, n-1);↵
return {A.first+(1<<(n-1)), A.second};↵
}↵
if (zu == 1 && zv == 1) {↵
pii A = Lca(u, v, n-1);↵
return {A.first, A.second+(1<<(n-1))};↵
}↵
if (zv == 1) return Lca(u, {0, (1<<(n-1))-1}, n-1);↵
if (zv == 2) return Lca(u, {(1<<(n-1))-1, 0}, n-1);↵
return Lca(u, v, n-1);↵
}↵
inline int GetId(pii p){↵
return lower_bound(V, V+n, p)-V;↵
}↵
inline bool IsPar(pii u, pii v){↵
if (GetH(u)>GetH(v)) return 0;↵
return GetPar(v, GetH(v)-GetH(u))==u;↵
}↵
int dfs(int node){↵
for (int v:G[node]) sum[node]+=dfs(v);↵
return sum[node];↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
//freopen("input.txt", "r", stdin);↵
//freopen("output.txt", "w", stdout);↵
vector<pii> vec;↵
cin>>m;↵
for (int i=0; i<2*m; i++) cin>>A[i].first>>A[i].second, vec.pb(A[i]);↵
sort(all(vec));↵
vec.resize(unique(all(vec))-vec.begin());↵
dfs_order(vec);↵
for (int i=vec.size()-1; i; i--) vec.pb(Lca(vec[i], vec[i-1]));↵
sort(all(vec));↵
vec.resize(unique(all(vec))-vec.begin());↵
dfs_order(vec);↵
n=vec.size();↵
↵
debug("sorted")↵
↵
for (int i=0; i<n; i++) V[i]=vec[i];↵
sort(V, V+n);↵
vector<int> stk={root=GetId(vec[0])};↵
for (int i=1; i<n; i++){↵
int v=GetId(vec[i]);↵
while (!IsPar(V[stk.back()], V[v])) stk.pop_back();↵
par[v]=stk.back();↵
G[stk.back()].pb(v);↵
stk.pb(v); ↵
}↵
↵
for (int i=0; i<2*m; i+=2){↵
int u=GetId(A[i]), v=GetId(A[i+1]), lca=GetId(Lca(A[i], A[i+1]));↵
sum[u]++;↵
sum[v]++;↵
sum[lca]-=2;↵
is[lca]=1;↵
}↵
dfs(root);↵
for (int v=0; v<n; v++){↵
if (sum[v]){↵
grundy.pb(GetH(V[par[v]])+1);↵
grundy.pb(GetH(V[v])+1);↵
}↵
else if (is[v]){↵
grundy.pb(GetH(V[v]));↵
grundy.pb(GetH(V[v])+1);↵
}↵
}↵
sort(all(grundy));↵
vec.clear();↵
int last=-1;↵
for (int x:grundy){↵
if (last==-1){↵
if (vec.empty() || vec.back().second<x) last=x;↵
else{↵
last=vec.back().first;↵
vec.pop_back();↵
}↵
}↵
else{↵
if (last<x) vec.pb({last, x});↵
last=-1;↵
}↵
}↵
ans=2*vec.size();↵
if (ans && vec[0].first==0) ans--;↵
cout<<ans<<"\n";↵
↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
