首页 > 其他分享 >20240118

20240118

时间：2024-01-18 20:23:33浏览次数：22  
标签：cnt return int st 20240118 MOD define

该卷卷啦 再摆烂不能要了

A. 游戏

其实我10月份做过这道题 自己做了忘了 再做还读错30min题

容易想到，操作次数之和最后一个不为其它数倍数的数的位置有关

那么，先考虑筛法把所有这样的数找出来，设共有 \(x\) 个

然后显然就可以枚举最后一个的位置，然后组合

更强的结论为

\[\frac{x}{x+1}(n+1)! \]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
	if (a > b)
		return a;
	return b;
}
int min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e7 + 10;

// bool st;
int l, r;
int n;
int fac[N];
bool vis[N];
vector<int> vec;
int cnt = 0;
// bool en;

int fct[10000009], divfct[10000009];
int qpow(int a, int b)
{
	int ans = 1;
	while (b)
	{
		if (b & 1)
			ans = (ans * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return ans;
}
void init()
{
	fct[0] = 1;
	for (int i = 1; i <= 10000000; i++)
		fct[i] = (fct[i - 1] * i) % MOD;
	divfct[10000000] = qpow(fct[10000000], MOD - 2);
	for (int i = 10000000 - 1; i >= 0; i--)
		divfct[i] = (divfct[i + 1] * (i + 1)) % MOD;
}
int C(int x, int y)
{
	if (x < 0 || y < 0 || x < y)
		return 0;
	if (x == y || y == 0)
		return 1;
	else
		return fct[x] * divfct[x - y] % MOD * divfct[y] % MOD;
}

void solve()
{
	cin >> l >> r;
	init();
	n = r - l + 1;
	fac[0] = 1;
	rep(i, 1, n) fac[i] = fac[i - 1] * i % MOD;
	rep(i, l, r)
	{
		if (!vis[i])
		{
			cnt++;
			vec.push_back(i);
		}
		for (int x = i; x <= r; x += i)
		{
			vis[x] = true;
		}
	}
	// cerr << cnt << endl;
	int res = 0;
	rep(i, cnt, n)
	{
		(res += i * C(i - 1, cnt - 1) % MOD * fct[cnt] % MOD * fct[n - cnt] % MOD) %= MOD;
		// cerr << res << endl;
	}
	cout << res << endl;
}

signed main()
{
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	// cerr<<(&en-&st)/1024.0/1024.0<<endl;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
	return 0;
}

挖个坑 不会证

B. 最短路

感觉很典的题(可能吧 为什么感觉别人都没见过呢)

很容易想到对于每个点单独算贡献

求出到一个点用 \(k\) 步，\(t=0\) 时的最小距离 \(b\) 是容易的

这样，其实相当于对于每个点，给定若干个 \(y=kx+b\) 的一次函数，求 \(\sum\limits_{x=0}^m \min{(f(x))}\)

明显可以凸包维护

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)
{
	if (a > b)
		return a;
	return b;
}
int min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2500 + 10;
const int M = 5000 + 10;
const int inv2 = 500000004;

// bool st;
int n, m, t;
vector<pii> g[N];
int dis[N][M];
pii st[M];
int top = 0;
// bool en;

void solve()
{
	cin >> n >> m >> t;
	rep(i, 1, m)
	{
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	memset(dis, 0x3f, sizeof(dis));
	dis[1][0] = 0;
	int res = 0;
	rep(st, 0, m - 1)
	{
		rep(x, 1, n)
		{
			for (auto [v, w] : g[x])
			{
				if (dis[v][st + 1] > dis[x][st] + w)
				{
					dis[v][st + 1] = dis[x][st] + w;
				}
			}
		}
	}
	// int res = 0;
	rep(i, 2, n)
	{
		top = 0;
		// cerr << i << endl;
		per(j, m, 1)
		{
			// cerr << dis[i][j] << ' ';
			while (top > 1 && (__int128)(st[top].second - st[top - 1].second) * (__int128)(j - st[top].first) < (__int128)(dis[i][j] - st[top].second) * (__int128)(st[top].first - st[top - 1].first))
				top--;
			st[++top] = {j, dis[i][j]};
		}
		// cerr << endl;
		// cerr << top << endl;
		// rep(i, 1, top) cerr << st[i].first << ' ' << st[i].second << endl;
		// reverse(st + 1, st + top + 1);
		int l = 0, r;
		rep(j, 1, top)
		{
			if (l > t)
				break;
			if (j != top)
				r = (st[j + 1].second - st[j].second) / (st[j].first - st[j + 1].first);
			else
				r = INF;
			while (j != top && st[j].first * r + st[j].second <= st[j + 1].first * r + st[j + 1].second)
				r++;
			r--;
			r = min(r, t);
			if (r < l)
				continue;
			res = (res + (l * st[j].first % MOD + st[j].second + r * st[j].first % MOD + st[j].second) % MOD * (r - l + 1) % MOD * inv2 % MOD) % MOD;
			l = r + 1;
		}
		// int p = 1;
		// rep(j, 0, t)
		// {
		// 	while (p < top && st[p].first * j + st[p].second >= st[p + 1].first * j + st[p + 1].second)
		// 		p++;
		// 	(res += st[p].first * j % MOD + st[p].second) %= MOD;
		// }
	}
	cout << res << endl;
}

signed main()
{
	// freopen("a.in", "r", stdin);
	// freopen("a.out", "w", stdout);
	// cerr<<(&en-&st)/1024.0/1024.0<<endl;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
	return 0;
}

C. 移动箱子

结论1：当前堆有 \(y\) 个，\(lim=k\) 的时候，这一堆产生的贡献是

\[t=\lfloor\frac{y}{k}\rfloor\\ f_y(k)=yt-k\binom{t+1}{2} \]

结论2：当存在 \((x_i,y_i),(x_{i+1},y_{i+1})\) 使得从 \(x_i\) 出发向后铺会延伸到 \(x_{i+1}\) ，这两堆等价于 \((x_i,y_i+y_{i+1})\) ， 可以直接合并

从大到小枚举 \(lim\)， 每次用链表合并，更新代价

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 998244353;
const int N = 2e5 + 10;

// bool st;
int n, m;
pii p[N];
int nxt[N], pre[N];
int x[N], y[N], z[N];
vector<int> vec[N];
bool vis[N];
int s[N], t[N];
int cnt;
// bool en;

int binom(int x) {
    x = (x % MOD + MOD) % MOD;
    return x * (x + 1) / 2 % MOD;
}

void add(int &x, int y) { x = ((x % MOD + (y % MOD + MOD) % MOD) % MOD + MOD) % MOD; }

void solve() {
    cin >> n >> m;
    cnt = n;
    rep(i, 1, n) cin >> p[i].first >> p[i].second;
    sort(p + 1, p + n + 1);
    nxt[0] = 1;
    rep(i, 1, n) {
        nxt[i] = i + 1;
        pre[i] = i - 1;
    }
    nxt[n] = 0;
    rep(i, 1, n) {
        x[i] = p[i].first;
        y[i] = p[i].second;
    }
    rep(i, 1, n) { vec[y[i]].push_back(i); }
    per(i, m, 1) {
        for (auto v : vec[i]) {
            if (vis[v])
                continue;
            add(s[i], -(z[v] % MOD) * (y[v] % MOD) % MOD);
            add(t[i], -binom(z[v]));
            z[v] = y[v] / i;
            if (y[v] / (z[v] + 1))
                vec[y[v] / (z[v] + 1)].push_back(v);
            add(s[i], (z[v] % MOD) * (y[v] % MOD) % MOD);
            add(t[i], binom(z[v]));
        }
        for (auto v : vec[i]) {
            if (vis[v])
                continue;
            for (int k = nxt[v]; k && x[v] + z[v] >= x[k]; k = nxt[v]) {
                add(s[i], -(z[v] % MOD) * (y[v] % MOD) % MOD);
                add(t[i], -binom(z[v]));
                add(s[i], -(z[k] % MOD) * (y[k] % MOD) % MOD);
                add(t[i], -binom(z[k]));
                cnt++;
                x[cnt] = x[v];
                y[cnt] = y[v] + y[k];
                z[cnt] = y[cnt] / i;
                add(s[i], (z[cnt] % MOD) * (y[cnt] % MOD) % MOD);
                add(t[i], binom(z[cnt]));
                add(s[i], -(y[k] % MOD) * ((x[k] - x[v]) % MOD) % MOD);
                if (y[cnt] / (z[cnt] + 1))
                    vec[y[cnt] / (z[cnt] + 1)].push_back(cnt);
                vis[v] = vis[k] = true;
                nxt[pre[v]] = cnt;
                pre[nxt[k]] = cnt;
                pre[cnt] = pre[v];
                nxt[cnt] = nxt[k];
                v = cnt;
            }
        }
        vec[i].clear();
    }
    per(i, m, 1) {
        add(s[i], s[i + 1]);
        add(t[i], t[i + 1]);
    }
    rep(i, 1, m) { cout << ((s[i] + MOD - t[i] * i % MOD) % MOD + MOD) % MOD << ' '; }
}

signed main() {
    freopen("boxes.in", "r", stdin);
    freopen("boxes.out", "w", stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--) solve();
    return 0;
}

被卡常了 还 TLE 这呢qwq

我与凸包不共戴天！太难调了qwq

标签：cnt,return,int,st,20240118,MOD,define
From： https://www.cnblogs.com/xiaruize/p/17973277

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99