Skip to content

Instantly share code, notes, and snippets.

@pwqbot

pwqbot/a.cpp Secret

Last active October 27, 2021 12:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save pwqbot/a5298aabd57a1dd05c796b184d59cc56 to your computer and use it in GitHub Desktop.
Save pwqbot/a5298aabd57a1dd05c796b184d59cc56 to your computer and use it in GitHub Desktop.
Download ZIP
eoj 2021.10 monthly
Raw
a.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=400010,OFFSET=100000;
struct TRI {
int x,y,z;
TRI (int a=0,int b=0,int c=0) {x=a,y=b,z=c;}
}ob[MAXN],le[4*MAXN];
int m,cnt,tim[4*MAXN],sum[4*MAXN];
ll ans;
vector <TRI> v[MAXN];
set < pair<int,int> > s;
bool cmp (TRI a,TRI b) {return a.x<b.x;}
bool cmp2 (TRI a,TRI b) {return a.y<b.y;}
void addsquare (int x,int y,int z) {
le[++cnt]=TRI(x+y,y-x,z-x);
le[++cnt]=TRI(x+z,z-x,y-x);
return;
}
void modify (int p,int l,int r,int xl,int xr,int v) {
if (xr<l||r<xl) {return;}
if (xl<=l&&r<=xr) {
if (v==1) {tim[p]++,sum[p]=r-l+1;}
else {tim[p]--,sum[p]=(tim[p]?r-l+1:sum[p<<1]+sum[(p<<1)|1]);}
return;
}
int mid=(l+r+1000000000)/2-500000000;
modify(p<<1,l,mid,xl,xr,v);
modify((p<<1)|1,mid+1,r,xl,xr,v);
sum[p]=(tim[p]?r-l+1:sum[p<<1]+sum[(p<<1)|1]);
return;
}
int main () {
scanf("%d",&m);
for (int i=1;i<=m;i++) {scanf("%d%d%d",&ob[i].x,&ob[i].y,&ob[i].z);}
for (int i=1;i<=m;i++) {v[ob[i].x].push_back(TRI(1,ob[i].y,ob[i].z));}
for (int i=OFFSET;i>=0;i--) {
int len=v[i].size();
for (int j=0;j<len;j++) {
TRI tmp=v[i][j];
if (tmp.x==0) {s.erase(make_pair(tmp.y-(OFFSET-i),tmp.z+(OFFSET-i)));}
else {
set < pair<int,int> >::iterator it1,it2,it;
it1=s.lower_bound(make_pair(tmp.y-(OFFSET-i),0));
it2=s.upper_bound(make_pair(tmp.z-(OFFSET-i),1e9));
if (it1!=s.begin()) {
it=it1;
--it;
if ((*it).second-(OFFSET-i)>=tmp.y) {tmp.y=(*it).first+(OFFSET-i);it1=it;}
}
if (it2!=s.begin()) {
it=it2;
--it;
if ((*it).first+(OFFSET-i)<=tmp.z) {
tmp.z=max(tmp.z,(*it).second-(OFFSET-i));
}
}
s.erase(it1,it2);
s.insert(make_pair(tmp.y-(OFFSET-i),tmp.z+(OFFSET-i)));
addsquare(i,tmp.y,tmp.z);
int tmpp=i-(tmp.z-tmp.y)/2;
if (tmpp>=0) {v[tmpp].push_back(TRI(0,(tmp.y+tmp.z)/2,(tmp.y+tmp.z)/2));}
}
}
v[i].clear();
}
s.clear();
for (int i=1;i<=m;i++) {v[ob[i].x].push_back(TRI(1,ob[i].y,ob[i].z));}
for (int i=0;i<=OFFSET;i++) {
int len=v[i].size();
for (int j=0;j<len;j++) {
TRI tmp=v[i][j];
if (tmp.x==0) {s.erase(make_pair(tmp.y-i,tmp.z+i));}
else {
set < pair<int,int> >::iterator it1,it2,it;
it1=s.lower_bound(make_pair(tmp.y-i,0));
it2=s.upper_bound(make_pair(tmp.z-i,1e9));
if (it1!=s.begin()) {
it=it1;
--it;
if ((*it).second-i>=tmp.y) {tmp.y=(*it).first+i;it1=it;}
}
if (it2!=s.begin()) {
it=it2;
--it;
if ((*it).first+i<=tmp.z) {
tmp.z=max(tmp.z,(*it).second-i);
}
}
s.erase(it1,it2);
s.insert(make_pair(tmp.y-i,tmp.z+i));
addsquare(i,tmp.y,tmp.z);
int tmpp=i+(tmp.z-tmp.y)/2;
if (tmpp<=OFFSET) {v[tmpp].push_back(TRI(0,(tmp.y+tmp.z)/2,(tmp.y+tmp.z)/2));}
}
}
v[i].clear();
}
sort(le+1,le+cnt+1,cmp);
for (int i=1;i<=cnt;i++) {
if (i>1) {ans+=1ll*sum[1]*(le[i].x-le[i-1].x);}
if (le[i].y<le[i].z) {modify(1,-OFFSET,OFFSET,le[i].y,le[i].z-1,1);}
else {modify(1,-OFFSET,OFFSET,le[i].z,le[i].y-1,-1);}
}
if (ans%2==0) {printf("%lld.00\n",ans/2);}
else {printf("%lld.50\n",ans/2);}
return 0;
}
Raw
c.cpp
/*
* ===---------------------------------------------------------=== *
* @Author qwqbot
* @Github github.com/pwqbot
* @Date 2021-10-17 19:50:12
* @LastEditTime 2021-10-21 22:00:12
*
* @Description
* ===---------------------------------------------------------=== *
*/
#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize(2)
#define QWQ1
const int INF = 0x3f3f3f3f;
const long long INF64 = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
typedef long long ll;
typedef double db;
typedef long double lb;
typedef complex<double> cb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef std::priority_queue<int, vector<int>, greater<int>> small_pq; // small
typedef std::priority_queue<int, vector<int>, less<int>> big_pq; // small
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
!is_same<T_container, string>::value,
typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
os << '{';
string sep;
for (const T &x : v) os << sep << x, sep = ", ";
return os << '}';
}
void dbg_out() {}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
cerr << " " << H;
if (sizeof...(T) > 0) {
cerr << " ,";
}
dbg_out(T...);
}
void dbg_name(const string &s) {
string ss = s;
replace(ss.begin(), ss.end(), ',', ' ');
cerr << " ( " << ss << " ) ";
}
#ifdef QWQ
#ifdef _WIN64
#define dbg(...) \
cerr << "\t\t\t"; \
cerr << __func__ << "_" << __LINE__ << " ->\t"; \
dbg_name(#__VA_ARGS__); \
cerr << "["; \
dbg_out(__VA_ARGS__); \
cerr << " ]" << endl;
#else
#define dbg(...) \
cerr << "\t\t"; \
cerr << "\e[32m" << __func__ << "_" << __LINE__ << "\e[32m ->\t"; \
cerr << "\e[0m"; \
dbg_name(#__VA_ARGS__); \
cerr << "\e[35m["; \
dbg_out(__VA_ARGS__); \
cerr << " ]\e[0m" << endl;
#endif
#else
#define dbg(...)
#endif
#define LOG(qwq...) fprintf(stderr, qwq)
#define rep(x, y, z) for (int(x) = int(y); int(x) <= int(z); x++)
#define per(x, y, z) for (int(x) = int(y); int(x) >= int(z); x--)
#define lowbit(x) ((-(x)) & (x))
template <typename T>
inline void setmin(T &a, const T &b) {
if (b < a) a = b;
}
template <typename T>
inline void setmax(T &a, const T &b) {
if (b > a) a = b;
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<long long, int, custom_hash> safe_map;
gp_hash_table<long long, int, custom_hash> safe_hash_table;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());
#ifdef QWQ
const int N = 2e6 + 5;
#else
const int N = 2e5 + 5;
#endif
const int MOD = 998244353;
inline int mul(int x, int y) { return 1ll * x * y % MOD; }
inline int add(int x, int y) { return (x + y) >= MOD ? x + y - MOD : x + y; }
inline int sub(int x, int y) { return (x - y) < 0 ? x - y + MOD : x - y; }
int qpow(int a, int b) {
ll ans = 1;
while (b) {
if (b & 1) ans = mul(ans, a);
a = mul(a, a);
b /= 2;
}
return ans;
}
namespace polynomial {
typedef vector<int> Poly;
namespace fast_fourier_transform {
typedef complex<double> cb;
const int N = 1000000;
int pos[N];
cb W[2][N];
void Dft(cb *a, int k, int flag) {
rep(i, 0, k - 1) {
if (i < pos[i]) swap(a[i], a[pos[i]]);
}
for (int h = 2, t = k >> 1; h <= k; h <<= 1, t >>= 1) {
// cb wn = exp(cb(0, 2 * PI * flag / h));
for (int i = 0; i < k; i += h) {
cb *w = W[flag];
for (int j = i; j < i + h / 2; j++, w += t) {
cb u = a[j];
cb v = *w * a[j + h / 2];
a[j] = u + v;
a[j + h / 2] = u - v;
}
}
}
}
int Init(int len) {
int k = 1, l = 0;
while (k <= len) {
k *= 2, l++;
}
rep(i, 0, k - 1) { pos[i] = (pos[i >> 1] >> 1 | (i & 1) << (l - 1)); }
// 预处理单位根
rep(i, 0, k - 1) {
W[0][i] = W[1][(k - i) & (k - 1)] =
cb(cos(2 * PI * i / k), sin(2 * PI * i / k));
}
return k;
}
Poly FFT(const Poly &a, const Poly &b) {
if (min(a.size(), b.size()) < 128) {
Poly c(a.size() + b.size() - 1);
rep(i, 0, a.size() - 1) {
rep(j, 0, b.size() - 1) { c[i + j] += (a[i] * b[j]); }
}
return c;
}
int len = a.size() + b.size() - 1;
int k = Init(len);
static cb A[N], B[N];
fill(A, A + k, 0);
fill(B, B + k, 0);
rep(i, 0, a.size() - 1) A[i].real(a[i]);
rep(i, 0, b.size() - 1) B[i].real(b[i]);
Dft(A, k, 0), Dft(B, k, 0);
rep(i, 0, k - 1) A[i] *= B[i];
Dft(A, k, 1);
Poly c(len);
rep(i, 0, len - 1) c[i] = (int)(A[i].real() / k + 0.5);
return c;
}
// 优化两次dft / 可能有精度问题
Poly FFT2(const Poly &a, const Poly &b) {
if (min(a.size(), b.size()) < 128) {
Poly c(a.size() + b.size() - 1);
rep(i, 0, a.size() - 1) {
rep(j, 0, b.size() - 1) c[i + j] += (a[i] * b[j]);
}
return c;
}
int len = (a.size() + b.size() - 1);
int k = Init(len);
static cb A[N];
fill(A, A + k, 0);
rep(i, 0, a.size() - 1) A[i].real(a[i]);
rep(i, 0, b.size() - 1) A[i].imag(b[i]);
Dft(A, k, 0);
rep(i, 0, k - 1) A[i] *= A[i];
Dft(A, k, 1);
Poly c(len);
rep(i, 0, len - 1) c[i] = (int)(A[i].imag() / 2 / k + 0.5);
return c;
}
// 任意模数 NTT/ 拆系数法
Poly MTT(const Poly &a, const Poly &b) {
int len = a.size() + b.size() - 1;
int k = Init(len);
static cb A[N], B[N], C[N], D[N];
rep(i, 0, a.size() - 1) A[i] = cb(a[i] & 32767, a[i] >> 15);
fill(A + a.size(), A + k, 0);
rep(i, 0, b.size() - 1) B[i] = cb(b[i] & 32767, b[i] >> 15);
fill(B + b.size(), B + k, 0);
Dft(A, k, 0), Dft(B, k, 0);
rep(i, 0, k - 1) {
int j = (k - i) & (k - 1);
C[i] = (A[i] + conj(A[j])) * 0.5 * B[i];
D[i] =
cb(A[i].imag() + A[j].imag(), A[j].real() - A[i].real()) * 0.5 * B[i];
}
Dft(C, k, 1), Dft(D, k, 1);
Poly ans(len);
rep(i, 0, len - 1) {
ll u = llround(C[i].real() / k) % MOD, v = llround(C[i].imag() / k) % MOD;
ll x = llround(D[i].real() / k) % MOD, y = llround(D[i].imag() / k) % MOD;
ans[i] = (u + ((v + x) << 15) % MOD + (y << 30)) % MOD;
}
return ans;
}
}; // namespace fast_fourier_transform
namespace number_theoretic_transform {
const int N = 1000000;
const int g1 = 3;
int pos[N];
int g[N];
void Dft(int *a, int k) {
rep(i, 0, k - 1) {
if (i < pos[i]) swap(a[i], a[pos[i]]);
}
for (int h = 1; h < k; h <<= 1) {
for (int i = 0; i < k; i += h * 2) {
for (int j = i; j < i + h; j++) {
int u = a[j];
int v = mul(g[j + h - i], a[j + h]);
a[j] = add(u, v);
a[j + h] = sub(u, v);
}
}
}
}
void IDft(int *a, int k) {
reverse(a + 1, a + k);
Dft(a, k);
int inv_k = qpow(k, MOD - 2);
rep(i, 0, k - 1) a[i] = mul(a[i], inv_k);
}
int Init(int len) {
int k = 1, l = 0;
while (k <= len) {
k *= 2, l++;
}
rep(i, 0, k - 1) pos[i] = (pos[i >> 1] >> 1 | (i & 1) << (l - 1));
// 预处理原根
int gv = qpow(g1, (MOD - 1) / k);
g[k >> 1] = 1;
for (int i = (k >> 1) + 1; i <= k; i++) {
g[i] = mul(g[i - 1], gv);
}
for (int i = (k >> 1) - 1; i; i--) {
g[i] = g[i << 1];
}
return k;
}
Poly NTT(const Poly &a, const Poly &b) {
if (min(a.size(), b.size()) < 128) {
Poly c(a.size() + b.size() - 1);
rep(i, 0, a.size() - 1) rep(j, 0, b.size() - 1) c[i + j] =
add(c[i + j], mul(a[i], b[j]));
return c;
}
int len = (a.size() + b.size() - 1);
int k = Init(len);
static int A[N], B[N];
std::copy_n(a.begin(), a.size(), A);
fill(A + a.size(), A + k, 0);
std::copy_n(b.begin(), b.size(), B);
fill(B + b.size(), B + k, 0);
Dft(A, k);
Dft(B, k);
rep(i, 0, k - 1) A[i] = mul(A[i], B[i]);
IDft(A, k);
Poly ans(len);
std::copy_n(A, len, ans.begin());
return ans;
}
}; // namespace number_theoretic_transform
Poly operator*(const Poly &a, const Poly &b) {
Poly ans = number_theoretic_transform::NTT(a, b);
return ans;
}
Poly operator+(const Poly &a, const Poly &b) {
Poly ans(max(a.size(), b.size()));
rep(i, 0, a.size() - 1) ans[i] = a[i];
rep(i, 0, b.size() - 1) ans[i] = add(ans[i], b[i]);
return ans;
}
Poly operator-(const Poly &a, const Poly &b) {
Poly ans(max(a.size(), b.size()));
rep(i, 0, a.size() - 1) ans[i] = a[i];
rep(i, 0, b.size() - 1) ans[i] = sub(ans[i], b[i]);
return ans;
}
} // namespace polynomial
namespace polynomial {
Poly Inverse(const Poly &a) {
assert(a[0] != 0);
Poly b(1, qpow(a[0], MOD - 2));
int n = a.size() << 1;
for (int i = 2; i < n; i <<= 1) {
Poly c(a);
c.resize(i);
b = (Poly(1, 2) - c * b) * b;
b.resize(i);
}
b.resize(a.size());
return b;
}
Poly Deriv(const Poly &a) {
Poly ans(a.size() - 1);
rep(i, 0, a.size() - 2) ans[i] = mul(a[i + 1], i + 1);
return ans;
}
Poly Integral(const Poly &a) {
Poly ans(a.size() + 1);
rep(i, 1, a.size()) ans[i] = mul(a[i - 1], qpow(i, MOD - 2));
return ans;
}
pair<Poly, Poly> operator/(const Poly &a, const Poly &b) {
assert(a.size() >= b.size());
Poly A(a), B(b);
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
int len = a.size() - b.size() + 1; // mod n - m + 1
A.resize(len), B.resize(len);
Poly Q = A * Inverse(B);
Q.resize(len);
reverse(Q.begin(), Q.end());
Poly R = a - b * Q;
R.resize(b.size() - 1);
return {Q, R};
}
// b(x) = 积分(a'(x) / a(x))
Poly Ln(const Poly &a) {
assert(a[0] == 1);
Poly ans = Integral(Inverse(a) * Deriv(a));
ans.resize(a.size());
return ans;
}
// b(x) = b(x0)(1 - ln(b(x0)) + a) (mod x^n)
Poly Exp(const Poly &a) {
assert(a[0] == 0);
Poly b(1, 1);
int n = a.size() << 1;
for (int i = 2; i < n; i <<= 1) {
Poly c(a);
c.resize(i);
b.resize(i);
b = b * (Poly(1, 1) - Ln(b) + c);
}
b.resize(a.size());
return b;
}
// 多项式取模是对MOD取模, 不是扩展欧拉定理的 phi(MOD) 取模
// 只适用于 a[0] = 1的情况
Poly Qpow1(const Poly &a, int k) {
Poly ans(1, 1), b(a);
int n = a.size();
while (k) {
if (k & 1) {
ans = ans * b;
ans.resize(n);
}
k >>= 1;
b = b * b;
b.resize(n);
}
return ans;
}
// 适用于 a[0] = 1
Poly Qpow2(const Poly &a, ll k) {
Poly b = Ln(a);
rep(i, 0, b.size() - 1) b[i] = mul(b[i], k);
return Exp(b);
}
// exp(kln(a))
// 适用任意 a[0]
Poly Qpow2(const Poly &a, const string &K) {
int n = a.size();
ll k1 = 0, k2 = 0, k3 = 0, flag = 0;
rep(i, 0, K.size() - 1) {
k1 = k1 * 10 + K[i] - '0'; // 多项式的指数取的模
k2 = k2 * 10 + K[i] - '0'; // a[shift]的指数取的模
if (k3 < n) {
k3 = k3 * 10 + K[i] - '0';
}
k1 %= MOD;
k2 %= MOD - 1;
}
int shift = n;
rep(i, 0, n - 1) {
if (a[i]) {
shift = i;
break;
}
}
if (shift * k3 >= n) {
return Poly(n);
}
int inv_a0 = qpow(a[shift], MOD - 2), a0 = qpow(a[shift], k2);
Poly b = {a.begin() + shift, a.end()};
rep(i, 0, b.size() - 1) b[i] = mul(b[i], inv_a0);
b = Ln(b);
rep(i, 0, b.size() - 1) b[i] = mul(b[i], k1);
b = Exp(b);
Poly ans(n);
shift *= k1;
rep(i, shift, n - 1) ans[i] = mul(b[i - shift], a0);
return ans;
}
} // namespace polynomial
int main(int argc, char *argv[]) {
#ifdef QWQ
freopen(argv[1], "r", stdin);
char *lastExt = strrchr(argv[1], '.');
*lastExt = '\0';
char *out = strcat(argv[1], ".ans");
freopen(out, "w", stdout);
// freopen("test/random_7120.in", "r", stdin);
int st_cl = clock();
#endif
#ifndef QWQ
ios::sync_with_stdio(false);
cin.tie(0);
#endif
using namespace polynomial;
vector<int> fac(N + 1);
fac[0] = 1;
rep(i, 1, N) { fac[i] = mul(fac[i - 1], i); }
int n, m;
cin >> n >> m;
vector<int> a(m + 1);
Poly g(n + 1);
Poly h(n + 1);
vector<int> cnt(n + 1);
rep(i, 1, m) {
cin >> a[i];
cnt[a[i]]++;
// g[a[i]] = add(g[a[i]], qpow(a[i], MOD - 2));
// g[0]++;
}
// g = h * g;
vector<int> inv(n + 1);
rep(i, 1, n) { inv[i] = qpow(i, MOD - 2); }
rep(i, 1, n) {
for (int j = i; j <= n; j += i) {
h[j] = add(h[j], mul(cnt[i], inv[j]));
}
}
Poly ans = Exp(h);
cout << mul(ans[n], fac[n]) << endl;
#ifdef QWQ
LOG("Time: %dms\n", int((clock() - st_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
return 0;
}
Raw
d.cpp
#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define QWQ1
const int INF = 0x3f3f3f3f;
const long long INF64 = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
typedef long long ll;
typedef double db;
typedef long double lb;
typedef complex<double> cb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef std::priority_queue<int, vector<int>, greater<int>> small_pq; // small
typedef std::priority_queue<int, vector<int>, less<int>> big_pq; // small
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
!is_same<T_container, string>::value,
typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
os << '{';
string sep;
for (const T &x : v) os << sep << x, sep = ", ";
return os << '}';
}
void dbg_out() {}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
cerr << " " << H;
if (sizeof...(T) > 0) {
cerr << " ,";
}
dbg_out(T...);
}
void dbg_name(const string &s) {
string ss = s;
replace(ss.begin(), ss.end(), ',', ' ');
cerr << " ( " << ss << " ) ";
}
#ifdef QWQ
#ifdef _WIN64
#define dbg(...) \
cerr << "\t\t\t"; \
cerr << __func__ << "_" << __LINE__ << " ->\t"; \
dbg_name(#__VA_ARGS__); \
cerr << "["; \
dbg_out(__VA_ARGS__); \
cerr << " ]" << endl;
#else
#define dbg(...) \
cerr << "\t\t"; \
cerr << "\e[32m" << __func__ << "_" << __LINE__ << "\e[32m ->\t"; \
cerr << "\e[0m"; \
dbg_name(#__VA_ARGS__); \
cerr << "\e[35m["; \
dbg_out(__VA_ARGS__); \
cerr << " ]\e[0m" << endl;
#endif
#else
#define dbg(...)
#endif
#define LOG(qwq...) fprintf(stderr, qwq)
#define rep(x, y, z) for (int(x) = int(y); int(x) <= int(z); x++)
#define per(x, y, z) for (int(x) = int(y); int(x) >= int(z); x--)
#define lowbit(x) ((-(x)) & (x))
template <typename T>
inline void setmin(T &a, const T &b) {
if (b < a) a = b;
}
template <typename T>
inline void setmax(T &a, const T &b) {
if (b > a) a = b;
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<long long, int, custom_hash> safe_map;
gp_hash_table<long long, int, custom_hash> safe_hash_table;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());
#ifdef QWQ
const int N = 2e3 + 5;
#else
const int N = 5e3 + 5;
#endif
const int MOD = 998244353;
inline int mul(int x, int y) { return 1ll * x * y % MOD; }
inline int add(int x, int y) { return (x + y) >= MOD ? x + y - MOD : x + y; }
inline int sub(int x, int y) { return (x - y) < 0 ? x - y + MOD : x - y; }
int qpow(int a, int b) {
ll ans = 1;
while (b) {
if (b & 1) ans = mul(ans, a);
a = mul(a, a);
b /= 2;
}
return ans;
}
double dp[N][N];
double dfs(int n, int m) {
if (n > m) return 0;
if (n == 0 && m == 0) return 1;
if (dp[n][m] > 0) return dp[n][m];
double ans = 0;
if (n) {
ans += 1.0 * n / (m + n) * dfs(n - 1, m);
}
if (m) {
ans += 1.0 * m / (m + n) * dfs(n, m - 1);
}
return dp[n][m] = ans;
}
int main(int argc, char *argv[]) {
#ifdef QWQ
freopen(argv[1], "r", stdin);
char *lastExt = strrchr(argv[1], '.');
*lastExt = '\0';
char *out = strcat(argv[1], ".ans");
freopen(out, "w", stdout);
int st_cl = clock();
#endif
#ifndef QWQ
ios::sync_with_stdio(false);
cin.tie(0);
#endif
int n;
cin >> n;
rep(i, 0, n) {
rep(j, 0, n) { dp[i][j] = -1; }
}
cout << fixed << setprecision(6) << 1 - dfs(n, n) << endl;
#ifdef QWQ
LOG("Time: %dms\n", int((clock() - st_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
return 0;
}
Raw
e.cpp
#include <bits/extc++.h>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define QWQ1
const int INF = 0x3f3f3f3f;
const long long INF64 = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
typedef long long ll;
typedef double db;
typedef long double lb;
typedef complex<double> cb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef std::priority_queue<int, vector<int>, greater<int>> small_pq; // small
typedef std::priority_queue<int, vector<int>, less<int>> big_pq; // small
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
!is_same<T_container, string>::value,
typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
os << '{';
string sep;
for (const T &x : v) os << sep << x, sep = ", ";
return os << '}';
}
void dbg_out() {}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
cerr << " " << H;
if (sizeof...(T) > 0) {
cerr << " ,";
}
dbg_out(T...);
}
void dbg_name(const string &s) {
string ss = s;
replace(ss.begin(), ss.end(), ',', ' ');
cerr << " ( " << ss << " ) ";
}
#ifdef QWQ
#ifdef _WIN64
#define dbg(...) \
cerr << "\t\t\t"; \
cerr << __func__ << "_" << __LINE__ << " ->\t"; \
dbg_name(#__VA_ARGS__); \
cerr << "["; \
dbg_out(__VA_ARGS__); \
cerr << " ]" << endl;
#else
#define dbg(...) \
cerr << "\t\t"; \
cerr << "\e[32m" << __func__ << "_" << __LINE__ << "\e[32m ->\t"; \
cerr << "\e[0m"; \
dbg_name(#__VA_ARGS__); \
cerr << "\e[35m["; \
dbg_out(__VA_ARGS__); \
cerr << " ]\e[0m" << endl;
#endif
#else
#define dbg(...)
#endif
#define LOG(qwq...) fprintf(stderr, qwq)
#define rep(x, y, z) for (int(x) = int(y); int(x) <= int(z); x++)
#define per(x, y, z) for (int(x) = int(y); int(x) >= int(z); x--)
#define lowbit(x) ((-(x)) & (x))
template <typename T>
inline void setmin(T &a, const T &b) {
if (b < a) a = b;
}
template <typename T>
inline void setmax(T &a, const T &b) {
if (b > a) a = b;
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<long long, int, custom_hash> safe_map;
gp_hash_table<long long, int, custom_hash> safe_hash_table;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());
#ifdef QWQ
const int N = 2e3 + 5;
#else
const int N = 2e6 + 5;
#endif
const int MOD = 998244353;
inline int mul(int x, int y) { return 1ll * x * y % MOD; }
inline int add(int x, int y) { return (x + y) >= MOD ? x + y - MOD : x + y; }
inline int sub(int x, int y) { return (x - y) < 0 ? x - y + MOD : x - y; }
int qpow(int a, int b) {
ll ans = 1;
while (b) {
if (b & 1) ans = mul(ans, a);
a = mul(a, a);
b /= 2;
}
return ans;
}
vector<int> g[N];
int a[N];
std::priority_queue<pii, vector<pii>, less<pii>> pq;
struct DicTree {
int tid[N * 10];
int trie[N * 10][2];
int num[N * 10];
int cnt;
int Insert(int x, int p) {
int root = tid[p];
int now = ++cnt;
for (int i = 30; i >= 0; i--) {
int ch = (x >> i) & 1;
num[cnt] = num[root] + 1;
trie[cnt][ch] = cnt + 1;
trie[cnt][!ch] = trie[root][!ch];
root = trie[root][ch];
cnt++;
}
num[cnt] = num[root] + 1;
return now;
}
int Query(int x, int k, int p) {
int root = tid[p];
int val = 0;
for (int i = 30; i >= 0; i--) {
int ch = (x >> i) & 1;
if (num[trie[root][!ch]] >= k) {
root = trie[root][!ch];
val |= (1 << i);
} else {
k -= num[trie[root][!ch]];
root = trie[root][ch];
}
}
return val;
}
} tr;
int fa[N];
int dep[N], cnt[N];
void dfs(int x, int p) {
dep[x] = dep[p] + 1;
if (dep[x] > 1) {
pq.push({tr.Query(a[x], 1, p), x});
}
tr.tid[x] = tr.Insert(a[x], p);
fa[x] = p;
for (auto v : g[x]) {
if (v == p) {
continue;
}
dfs(v, x);
}
}
int main() {
#ifdef QWQ
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int st_cl = clock();
#endif
#ifndef QWQ
ios::sync_with_stdio(false);
cin.tie(0);
#endif
int n, k;
scanf("%d %d", &n, &k);
rep(i, 1, n - 1) {
int u, v;
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
rep(i, 1, n) { scanf("%d", a + i); }
dfs(1, 0);
vector<int> ans(k);
rep(i, 0, k - 1) {
auto x = pq.top();
pq.pop();
ans[i] = x.first;
if (cnt[x.second] + 2 < dep[x.second]) {
cnt[x.second]++;
pq.push(
{tr.Query(a[x.second], cnt[x.second] + 1, fa[x.second]), x.second});
}
}
for (auto to : ans) {
printf("%d\n", to);
}
#ifdef QWQ
LOG("Time: %dms\n", int((clock() - st_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
return 0;
}
Raw
f.cpp
/*
* ===---------------------------------------------------------=== *
* @Author qwqbot
* @Github github.com/pwqbot
* @Date 2021-10-17 16:07:40
* @LastEditTime 2021-10-22 22:32:58
*
* @Description
* ===---------------------------------------------------------=== *
*/
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Ask(int x, int y) {
cout << "? " << x << " " << y << endl;
cout.flush();
int ans;
cin >> ans;
return ans;
}
int main() {
int n;
cin >> n;
// cerr << "n input" << endl;
// cerr << n << endl;
int p = -1;
int vp = -1;
for (int i = 0;; i++) {
int x = rnd() % n + 1;
int y = rnd() % n + 1;
while (x == y) {
y = rnd() % n + 1;
}
int val = Ask(x, y);
if (val > 9 * n / 10) {
p = x;
vp = val;
// cerr << x << " " << y << " " << val << endl;
break;
}
}
// if (n == 292307) {
// p = 7;
// vp = 253752;
// }
// cerr << "$ " << vp << " " << p << endl << flush;
vector<vector<int>> v(n + 1);
for (int i = 1; i <= n; i++) {
if (i == p) {
continue;
}
int val = Ask(i, p);
v[val].push_back(i);
}
vector<int> ans(n + 1);
for (int i = 1; i <= n; i++) {
if (i == vp) {
ans[p] = vp;
continue;
}
if (v[i].size() == 1) {
ans[v[i][0]] = i;
} else if (v[i].size() == 2) {
int val = Ask(v[i][0], v[i][1]);
if (val == i) {
ans[v[i][0]] = i;
ans[v[i][1]] = vp + i;
} else {
ans[v[i][0]] = vp + i;
ans[v[i][1]] = i;
}
} else if (v[i].size() > 2) {
assert(false);
}
}
cout << "! ";
for (int i = 1; i <= n; i++) {
cout << ans[i] << " ";
}
cout << endl;
cout.flush();
return 0;
}
@a180285
Copy link

a180285 commented Oct 26, 2021

求A题标程,一直 WA

@pwqbot
Copy link
Author

pwqbot commented Oct 27, 2021

求A题标程,一直 WA

已经更新

@a180285
Copy link

a180285 commented Oct 27, 2021

求A题标程,一直 WA

已经更新

Thank you~

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment