-
-
Save pwqbot/a5298aabd57a1dd05c796b184d59cc56 to your computer and use it in GitHub Desktop.
eoj 2021.10 monthly
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* ===---------------------------------------------------------=== * | |
* @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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* ===---------------------------------------------------------=== * | |
* @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; | |
} |
求A题标程,一直 WA
已经更新
求A题标程,一直 WA
已经更新
Thank you~
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
求A题标程,一直 WA