link

D - Same GCDs

Description

给出a,ma, m，求有多少个x∈[0,m)x \in[0, m)满足gcd(a,m)=gcd(a+x,m)\gcd(a, m) = \gcd(a + x, m)

a<m≤1010a < m \le 10^{10}

Solution

以下(a,b)(a, b)均表示gcd(a,b)\gcd(a, b)

考场降智...

题意可以转化为求有多少个x′∈[a,a+m)x'\in[a, a + m)，满足(a,m)=(x′,m)(a, m) = (x', m)

又因为(a,b)=(a−b,b)(a, b) = (a - b, b)，所以当x′∈[m,a+m)x'\in[m, a + m)时，(x′,m)=(x′−m,m)(x', m) = (x' - m, m)

所以转化为求有多少 x′∈[0,m)x'\in[0, m)，满足(a,m)=(x′,m)(a, m) = (x', m)

答案即为φ(m(a,m))\varphi(\frac{m}{(a, m)})

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 1e5;

LL a, M;

inline LL get_phi (LL n)
{
	LL ans = n;
	for (LL i = 2; i * i <= n; ++i) if (!(n % i))
	{
		while (!(n % i)) n /= i;
		ans = ans / i * (i - 1);
	}
	if (n > 1) ans = ans / n * (n - 1);
	return ans;
}

inline void Solve ()
{
	printf("%lld\n", get_phi (M / __gcd (a, M)));
}

inline void Input ()
{
	a = read<LL>(), M = read<LL>();
}

int main ()
{

#ifdef hk_cnyali
	freopen("D.in", "r", stdin);
	freopen("D.out", "w", stdout);
#endif

	int Te = read<int>();

	while (Te--)
	{
		Input ();
		Solve ();
	}

	return 0;
}

E. Permutation Separation

Description

20-2-5-1

Solution

枚举最后答案中左半边集合元素的最大值xx, 维护一个数组sis_i表示当前如果从ii处切开所花费的代价。

考虑左半边集合元素的最大值从x−1x - 1变化到xx时，sis_i会怎样变化

显然是在[1,x−1][1, x - 1]加上aia_i，在[x,n)[x, n)减去aia_i

线段树维护最小值，区间加即可

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 2e5;

int N, P[MAXN + 5], A[MAXN + 5];

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls o << 1
#define rs o << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
	const int MAXN = ::MAXN * 4;

	struct info
	{
		LL val, tag;
	} node[MAXN + 5];

	inline void push_up (int o) { node[o].val = min (node[ls].val, node[rs].val); }

	inline void push_down (int o)
	{
		if (!node[o].tag) return ;
		LL &tag = node[o].tag;
		node[ls].val += tag, node[ls].tag += tag;
		node[rs].val += tag, node[rs].tag += tag;
		tag = 0;
	}

	inline void update (int o, int l, int r, int x, int y, LL val)
	{
		if (x > y) return ;
		if (x <= l && r <= y)
		{
			node[o].val += val, node[o].tag += val;
			return ;
		}
		push_down (o);
		if (x <= mid) update (lson, x, y, val);
		if (y > mid) update (rson, x, y, val);
		push_up (o);
	}

	inline LL query () { return node[1].val; }
#undef mid
}

int Pos[MAXN + 5];

inline void Solve ()
{
	LL sum = 0;
	for (int i = 1; i <= N; ++i) 
	{
		sum += A[i];
		SEG :: update (1, 1, N - 1, i, i, sum);
	}

	LL ans = LLONG_MAX;
	for (int i = 1; i <= N; ++i)
	{
		int p = Pos[i];
		if (p == 1 || p == N) Chkmin(ans, (LL) A[p]);
		SEG :: update (1, 1, N - 1, 1, p - 1, A[p]);
		SEG :: update (1, 1, N - 1, p, N - 1, -A[p]);
		Chkmin (ans, SEG :: query ());
	}

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>();
	for (int i = 1; i <= N; ++i) Pos[P[i] = read<int>()] = i;
	for (int i = 1; i <= N; ++i) A[i] = read<int>();
}

int main ()
{

#ifdef hk_cnyali
	freopen("E.in", "r", stdin);
	freopen("E.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}

F. Good Contest

Description

给你nn个数，第ii个数的取值为i_i到rir_i中等概率随机的整数

求产生的序列单调不上升的概率

n≤50,li,ri≤998244351n\le 50, l_i, r_i\le 998244351

Solution

因为是整数，所以可以先求方案再除总方案数

暴力dp是设f[i][j]f[i][j]表示到第ii个数，其取值为jj的方案。因为权值范围很大，考虑优化。

发现题目所给的区间把值域劈成了若干个值域连续段，因为权值必须不增，考虑设f[i][j]f[i][j]表示从大到小考虑到第ii个段，已经填完了jj个数的方案数，枚举下一段填多少个数转移。

转移时要保证填上去的数从大到小依次排列，即固定了顺序，且值可以相同。于是变成了球相同，盒不同，允许空盒的放球问题，插板法算下方案即可

转移方程:

f[i][j]∗(len+k−1k)→f[i+1][j+k] f[i][j] * \binom{len + k - 1}{k} \rightarrow f[i + 1][j + k]

其中lenlen表示第ii段的值域长度

组合数O(k)O(k)暴力计算，总复杂度O(n4)O(n^4)

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 100;
const int MAXM = MAXN * 2;
const int MOD = 998244353;

namespace MATH
{
	int fac[MAXN + 5], ifac[MAXN + 5], inv[MAXN + 5];

	inline void ADD (int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

	inline int Pow (int a, int b)
	{
		int ans = 1;
		for (int i = b; i; i >>= 1, a = (LL) a * a % MOD) if (i & 1) ans = (LL) ans * a % MOD;
		return ans;
	}

	inline void init (int n = MAXN + 1)
	{
		fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = (LL) fac[i - 1] * i % MOD;
		ifac[n] = Pow (fac[n], MOD - 2); for (int i = n - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % MOD;
		for (int i = 0; i < n; ++i) inv[i + 1] = (LL) fac[i] * ifac[i + 1] % MOD;
	}

	inline int C (int n, int m)
	{
		if (n < m || n < 0 || m < 0) return 0;
		if (m == 0) return 1;
		if (m == 1) return n;
		return (LL) C (n, m - 1) * (n - m + 1) % MOD * inv[m] % MOD;
	}
}

using namespace MATH;

int N;
int L[MAXN + 5], R[MAXN + 5]; 
int Hash[MAXM + 5], M;

inline void Init ()
{
	sort (Hash + 1, Hash + M + 1);
	M = unique (Hash + 1, Hash + M + 1) - Hash - 1;
	for (int i = 1; i <= N; ++i)
	{
		L[i] = lower_bound (Hash + 1, Hash + M + 1, L[i]) - Hash;
		R[i] = lower_bound (Hash + 1, Hash + M + 1, R[i]) - Hash;
	}
}

int f[MAXM + 5][MAXN + 5];

inline int check (int x, int k)
{
	if (x == 0) return 1;
	if (Hash[L[x]] <= Hash[k - 1] + 1 && Hash[k] <= Hash[R[x]]) return 1;
	return 0;
}

int sum = 1;

inline void Solve ()
{
	Init ();
	f[M + 1][0] = 1;

	for (int i = M + 1; i >= 2; --i) for (int j = 0; j <= N; ++j) if (f[i][j])
	{
		int len = Hash[i - 1] - Hash[i - 2];
		ADD (f[i - 1][j], f[i][j]);
		for (int k = 1; j + k <= N && check (j + k, i - 1); ++k)
			ADD (f[i - 1][j + k], (LL) f[i][j] * C (len + k - 1, k) % MOD);
	}

	cout << (LL) f[1][N] * Pow (sum, MOD - 2) % MOD << endl;
}

inline void Input ()
{
	N = read<int>();
	for (int i = 1; i <= N; ++i)
	{
		L[i] = read<int>(), R[i] = read<int>();
		Hash[++M] = L[i], Hash[++M] = L[i] - 1, Hash[++M] = R[i];
		sum = (LL) sum * (R[i] - L[i] + 1) % MOD;
	}
}

int main ()
{

#ifdef hk_cnyali
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	MATH :: init ();
	Input ();
	Solve ();

	return 0;
}