- LibreOJ NOI Round #2 Day 2
LibreOJ NOI Round #2 Day 2参考代码
-
刘昱宏 (dwliuyuhong)
LV 6
@
2024-8-30 11:41:49
签到游戏
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
#ifdef __WIN32
#define LLFORMAT "I64"
#define Rand() ((rand() << 15) | rand())
#else
#define LLFORMAT "ll"
#define Rand() (rand())
#endif
template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
struct node
{
int sum;
node *c[2];
void update()
{
sum = 0;
REP(i, 0, 2) sum = __gcd(sum, c[i]->sum);
}
};
const int maxn = 100100;
int n, qn;
int a[maxn + 5];
const int max0 = 100000;
node *nd_pool;
int nd_res = 0;
inline node *newnode()
{
if (!nd_res) nd_pool = new node[max0], nd_res = max0;
return nd_pool + (--nd_res);
}
void build(node *&rt, int l, int r)
{
rt = newnode();
if (r - l <= 1)
{
rt->sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(rt->c[0], l, mid);
build(rt->c[1], mid, r);
rt->update();
}
int seg_x, seg_y;
void modify(node *rt, int l, int r)
{
if (r - l <= 1)
{
rt->sum = seg_y;
return;
}
int mid = (l + r) >> 1;
if (seg_x < mid)
{
modify(rt->c[0], l, mid);
}
else
{
modify(rt->c[1], mid, r);
}
rt->update();
}
inline int get_midpoint(node *rt, int l, int r, int le = 0, int ri = 0)
{
if (r - l <= 1) return r;
int mid = (l + r) >> 1;
if (__gcd(le, rt->c[0]->sum) > __gcd(ri, rt->c[1]->sum))
return get_midpoint(rt->c[1], mid, r, __gcd(le, rt->c[0]->sum), ri);
else
return get_midpoint(rt->c[0], l, mid, le, __gcd(ri, rt->c[1]->sum));
}
int seg_cur = 0;
LL seg_ret = 0;
inline void get_suml(node *rt, int l, int r)
{
if (r - l <= 1)
{
seg_ret += seg_cur;
seg_cur = __gcd(seg_cur, rt->sum);
return;
}
if (seg_x <= l && r <= seg_y)
{
if (seg_cur != 0 && rt->sum % seg_cur == 0)
{
seg_ret += (LL)seg_cur * (r - l);
return;
}
}
int mid = (l + r) >> 1;
if (seg_x < mid)
{
get_suml(rt->c[0], l, mid);
}
else seg_cur = __gcd(seg_cur, rt->c[0]->sum);
if (mid < seg_y)
{
get_suml(rt->c[1], mid, r);
}
}
inline void get_sumr(node *rt, int l, int r)
{
if (r - l <= 1)
{
seg_cur = __gcd(seg_cur, rt->sum);
seg_ret += seg_cur;
return;
}
if (seg_x <= l && r <= seg_y)
{
if (seg_cur != 0 && rt->sum % seg_cur == 0)
{
seg_ret += (LL)seg_cur * (r - l);
return;
}
}
int mid = (l + r) >> 1;
if (mid < seg_y)
{
get_sumr(rt->c[1], mid, r);
}
else seg_cur = __gcd(seg_cur, rt->c[1]->sum);
if (seg_x < mid)
{
get_sumr(rt->c[0], l, mid);
}
}
node *rt;
int main()
{
#ifdef matthew99
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d%d", &n, &qn);
REP(i, 0, n) scanf("%d", a + i);
rt = NULL;
build(rt, 0, n);
REP(i, 0, qn)
{
int x, y;
scanf("%d%d", &x, &y), --x;
seg_x = x, seg_y = y;
modify(rt, 0, n);
int mid = get_midpoint(rt, 0, n);
seg_ret = 0;
if (0 < mid)
{
seg_x = 0, seg_y = mid;
seg_cur = 0;
get_sumr(rt, 0, n);
}
if (mid < n)
{
seg_x = mid, seg_y = n;
seg_cur = 0;
get_suml(rt, 0, n);
}
printf("%" LLFORMAT "d\n", seg_ret);
}
return 0;
}
简单算术
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
#ifdef __WIN32
#define LLFORMAT "I64"
#define Rand() ((rand() << 15) | rand())
#else
#define LLFORMAT "ll"
#define Rand() (rand())
#endif
template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
inline int fpm(int b, int e, int m)
{
b %= m;
int t = 1;
for ( ; e; e >>= 1, (b *= b) %= m)
if (e & 1) (t *= b) %= m;
return t;
}
const int maxn = 55;
const int maxp = 55;
int Mod;
int n;
int a[maxn + 5];
int C[maxp + 5][maxp + 5];
int fac[maxp + 5], ifac[maxp + 5];
inline void prepare()
{
REP(i, 0, maxp)
{
C[i][0] = 1;
REP(j, 1, i + 1)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % Mod;
}
fac[0] = 1;
REP(i, 0, Mod - 1) fac[i + 1] = fac[i] * (i + 1) % Mod;
ifac[Mod - 1] = fpm(fac[Mod - 1], Mod - 2, Mod);
for (int i = Mod - 2; i >= 0; --i) ifac[i] = ifac[i + 1] * (i + 1) % Mod;
}
int dp[maxn + 5][maxp + 5][maxp * maxn + 5];
int f[maxp + 5][maxp * maxn + 5];
int g[maxn + 5];
int main()
{
#ifdef matthew99
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d%d", &n, &Mod);
++n;
prepare();
REP(i, 0, n) scanf("%d", a + i);
memset(dp, 0, sizeof dp);
dp[0][0][0] = 1;
REP(i, 0, n) REP(j, 0, Mod) REP(k, 0, j * (i - 1) + 1)
if (dp[i][j][k])
{
int tmp = 1;
REP(l, 0, Mod - j)
{
(dp[i + 1][j + l][k + l * i] += dp[i][j][k] * ifac[l] % Mod * tmp % Mod) %= Mod;
tmp = tmp * a[i] % Mod;
}
}
memset(f, 0, sizeof f);
REP(i, 0, Mod) REP(j, 0, i * (n - 1) + 1)
if (dp[n][i][j])
{
f[i][j] = dp[n][i][j] * fac[i] % Mod;
}
int T;
scanf("%d", &T);
while (T--)
{
LL m, K;
scanf("%" LLFORMAT "d%" LLFORMAT "d", &m, &K);
memset(g, 0, sizeof g);
g[0] = 1;
while (m)
{
int mm = m % Mod, kk = K % Mod;
static int tmp[maxn + 5];
memset(tmp, 0, sizeof tmp);
REP(i, 0, mm * (n - 1) + 1)
{
if (f[mm][i])
{
for (int j = ((kk - i) % Mod + Mod) % Mod; j < n; j += Mod)
if (g[j]) (tmp[(i + j) / Mod] += f[mm][i] * g[j] % Mod) %= Mod;
}
}
m /= Mod, K /= Mod;
memcpy(g, tmp, sizeof g);
}
int ans = g[K];
(ans += Mod) %= Mod;
printf("%d\n", ans);
}
return 0;
}
小球进洞
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
#ifdef __WIN32
#define LLFORMAT "I64"
#define Rand() ((rand() << 15) | rand())
#else
#define LLFORMAT "ll"
#define Rand() (rand())
#endif
template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int __buffsize = 100000;
char __buff[__buffsize];
char *__buffs, *__buffe;
#define getc() (__buffs == __buffe ? fread(__buff, 1, __buffsize, stdin), __buffe = __buff + __buffsize, *((__buffs = __buff)++) : *(__buffs++))
template<typename T> inline T &Read(T &x)
{
static char c;
while (1)
{
c = getc();
if (c == '-' || (c >= '0' && c <= '9')) break;
}
bool flag = c == '-';
x = flag ? 0 : c - '0';
while (1)
{
c = getc();
if (c < '0' || c > '9') break;
(x *= 10) += c - '0';
}
if (flag) x = -x;
return x;
}
#undef getc
const int maxabs = 2.01e5;
struct node
{
int Min;
int sz;
int label;
LL sumlr, sumrl;
node *c[2];
node(): Min(0), sz(0), label(0), sumlr(0), sumrl(0) { }
void update()
{
Min = oo;
REP(i, 0, 2)
{
chkmin(Min, c[i]->Min);
}
}
void flag_label(int _label)
{
label += _label;
Min += _label;
}
void push_down()
{
if (label)
{
REP(i, 0, 2) c[i]->flag_label(label);
label = 0;
}
}
};
const int max0 = 100000;
node *nd_pool;
int nd_res = 0;
inline node *newnode()
{
if (!nd_res) nd_pool = new node[max0], nd_res = max0;
return nd_pool + (--nd_res);
}
void build(node *&rt, int l, int r)
{
rt = newnode();
if (r - l <= 1)
{
rt->Min = l;
return;
}
int mid = (l + r) >> 1;
build(rt->c[0], l, mid);
build(rt->c[1], mid, r);
rt->sumlr = 0;
rt->sumrl = LL(l + mid + 1) * (mid - l) >> 1;
rt->update();
}
int seg_x, seg_y, seg_z, seg_ret;
void change_sz(node *rt, int l, int r)
{
rt->sz += seg_z;
if (r - l <= 1)
{
return;
}
int mid = (l + r) >> 1;
if (seg_x < mid) change_sz(rt->c[0], l, mid);
else change_sz(rt->c[1], mid, r);
}
int go_x, go_y;
int seg_cur;
inline LL golr(node *rt, int l, int r)
{
if (r - l <= 1)
{
LL ret = (LL)l * max(0, seg_cur - rt->Min);
chkmin(seg_cur, rt->Min);
return ret;
}
rt->push_down();
int mid = (l + r) >> 1;
if (go_x <= l && r <= go_y)
{
if (seg_cur > rt->c[0]->Min)
{
LL ret = golr(rt->c[0], l, mid) + rt->sumlr;
chkmin(seg_cur, rt->c[1]->Min);
return ret;
}
else return golr(rt->c[1], mid, r);
}
LL ret = 0;
if (go_x < mid) ret += golr(rt->c[0], l, mid);
if (go_y > mid) ret += golr(rt->c[1], mid, r);
return ret;
}
inline LL gorl(node *rt, int l, int r)
{
if (r - l <= 1)
{
LL ret = (l + 1) * (rt->Min < seg_cur);
chkmin(seg_cur, rt->Min);
return ret;
}
rt->push_down();
int mid = (l + r) >> 1;
if (go_x <= l && r <= go_y)
{
if (seg_cur > rt->c[1]->Min)
{
LL ret = gorl(rt->c[1], mid, r) + rt->sumrl;
chkmin(seg_cur, rt->c[0]->Min);
return ret;
}
else return gorl(rt->c[0], l, mid);
}
LL ret = 0;
if (go_y > mid) ret += gorl(rt->c[1], mid, r);
if (go_x < mid) ret += gorl(rt->c[0], l, mid);
return ret;
}
void modify(node *rt, int l, int r)
{
if (seg_x <= l && r <= seg_y)
{
rt->flag_label(-seg_z);
return;
}
rt->push_down();
int mid = (l + r) >> 1;
if (seg_x < mid) modify(rt->c[0], l, mid);
if (seg_y > mid) modify(rt->c[1], mid, r);
seg_cur = rt->c[0]->Min;
rt->sumlr = golr(rt->c[1], mid, r);
seg_cur = rt->c[1]->Min;
rt->sumrl = gorl(rt->c[0], l, mid);
rt->update();
}
void query_sz(node *rt, int l, int r)
{
if (seg_x <= l && r <= seg_y)
{
seg_ret += rt->sz;
return;
}
int mid = (l + r) >> 1;
if (seg_x < mid) query_sz(rt->c[0], l, mid);
if (seg_y > mid) query_sz(rt->c[1], mid, r);
}
void query_Min(node *rt, int l, int r)
{
if (seg_x <= l && r <= seg_y)
{
chkmin(seg_ret, rt->Min);
return;
}
rt->push_down();
int mid = (l + r) >> 1;
if (seg_x < mid) query_Min(rt->c[0], l, mid);
if (seg_y > mid) query_Min(rt->c[1], mid, r);
}
const int maxn = 100100;
node *rt;
int n, qn;
int a[maxn + 5];
int main()
{
#ifdef matthew99
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
Read(n), Read(qn);
build(rt, 0, maxabs);
REP(i, 0, n)
{
Read(a[i]);
seg_x = a[i], seg_y = maxabs, seg_z = 1;
go_x = 0, go_y = maxabs;
change_sz(rt, 0, maxabs);
modify(rt, 0, maxabs);
}
REP(i, 0, qn)
{
int ty;
Read(ty);
if (ty == 1)
{
int x, y;
Read(x), Read(y), --x;
seg_x = a[x], seg_y = maxabs, seg_z = -1;
go_x = 0, go_y = maxabs;
change_sz(rt, 0, maxabs);
modify(rt, 0, maxabs);
a[x] = y;
seg_x = a[x], seg_y = maxabs, seg_z = 1;
go_x = 0, go_y = maxabs;
change_sz(rt, 0, maxabs);
modify(rt, 0, maxabs);
}
else if (ty == 2)
{
int l, r;
Read(l), Read(r);
seg_x = 0, seg_y = l, seg_ret = 0;
query_sz(rt, 0, maxabs);
int Max = l - seg_ret;
if (l < r)
{
seg_x = l, seg_y = r, seg_ret = oo;
query_Min(rt, 0, maxabs);
chkmin(Max, seg_ret);
}
seg_x = r, seg_y = maxabs, seg_ret = oo;
query_Min(rt, 0, maxabs);
int Min = seg_ret;
if (Max <= Min) printf("0\n");
else
{
LL ans = 0;
go_x = 0, go_y = l;
seg_cur = Max;
ans += gorl(rt, 0, maxabs);
seg_cur = Min;
ans -= gorl(rt, 0, maxabs);
go_x = r, go_y = maxabs;
seg_cur = Max;
ans += golr(rt, 0, maxabs);
printf("%" LLFORMAT "d\n", ans);
}
}
}
return 0;
}
0 条评论
目前还没有评论...