BreakFast:2021HDU暑期多校训练营1
Replay
Problem A. Mod, Or and Everything
题目大意
组输入，每组一个整数 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} ，求 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (n \; mod \; 1) \; OR \; (n \; mod \; 2) \; OR \; \cdots \; OR \; (n \; mod \; n)} .
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1 \leq T \leq 5000, 1 \leq n \leq 10^{12}} .
分析
分析个啥，直接打表找规律.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e5;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
void work()
{
// for(int i = 1; i <= 100; ++i)
// {
// int s = 0;
// for(int j = 1; j <= i; ++j) s |= i % j;
// printf("%d: %d\n", i, s);
// }
ll n; scanf("%lld", &n);
if(n == 1)
{
printf("0\n");
return;
}
for(ll i = 0; ; ++i)
{
if(((1ll<<i) < n) && n <= ((1ll<<i+1)))
{
printf("%lld\n", (1ll<<i) - 1);
break;
}
}
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
int T; scanf("%d", &T);
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
return 0;
}
Problem C. Puzzle loop
题目大意
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle T} 组输入，每组输入一个大小为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (n - 1) \times (m - 1)} 的地图，地图字符集为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \{'0', '1', '.'\}} .
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle '0'} 表示该格子周围四条边有偶数条红边.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle '1'} 表示该格子周围四条边有奇数条红边.
表示该格子周围四条边无限制.
要求红边形成若干个边不相交的环，求方案数.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1 \leq T \leq 100, 1 \leq n, m \leq 17} .
分析
红边实质上就是若个干不相交的欧拉路嘛，因此要求每个交点的度为偶数，这样便满足了形成若干个边不相交的环这一条件.
此外对每个格子的四条边建异或方程.
于是得到异或方程组，高斯消元即可.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e6;
const int N = (int)17;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
int n, m;
char s[N + 5][N + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int row, col;
bool a[2 * (N + 1) * (N + 1) + 5][2 * N * (N + 1) + 5];
inline int id(int x1, int y1, int x2, int y2)
{
if(x1 > x2) swap(x1, x2);
if(y1 > y2) swap(y1, y2);
if(x1 == x2) return (x1 - 1) * m + y1;
else return (n + 1) * m + (x1 - 1) * (m + 1) + y1;
}
void build()
{
row = 0, col = (n + 1) * m + n * (m + 1);
for(int i = 1; i <= n + 1; ++i)
{
for(int j = 1; j <= m + 1; ++j)
{
++row;
for(int k = 1; k <= col + 1; ++k) a[row][k] = 0;
for(int k = 0, x, y; k < 4; ++k)
{
x = i + dx[k], y = j + dy[k];
if(x < 1 || x > n + 1 || y < 1 || y > m + 1) continue;
a[row][id(x, y, i, j)] = 1;
}
}
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(s[i][j] == '.') continue;
++row;
for(int k = 1; k <= col + 1; ++k) a[row][k] = 0;
a[row][id(i, j, i, j + 1)] = 1;
a[row][id(i, j, i + 1, j)] = 1;
a[row][id(i, j + 1, i + 1, j + 1)] = 1;
a[row][id(i + 1, j, i + 1, j + 1)] = 1;
a[row][col + 1] = s[i][j] - '0';
}
}
// for(int i = 1; i <= row; ++i)
// {
// bool f = 0;
// for(int j = 1; j <= col; ++j)
// {
// if(!a[i][j]) continue;
// if(f) printf(" ^ ");
// printf("x(%d)", j);
// f = 1;
// }
// printf(" = 0\n");
// }
}
int gauss(int n, int m)
{
int c, r;
for(c = 1, r = 1; c <= m; ++c)
{
int t = r;
for(int i = r; i <= n; ++i)
{
if(a[i][c]) t = i;
}
if(!a[t][c]) continue;
for(int i = c; i <= m + 1; ++i) swap(a[t][i], a[r][i]);
for(int i = 1; i <= n; ++i)
{
if(i == r) continue;
if(a[i][c])
{
for(int j = m + 1; j >= c; --j)
{
a[i][j] ^= a[r][j];
}
}
}
++r;
}
for(int i = r; i <= n; ++i)
{
if(a[i][m + 1]) return -1;//无解
}
return m - r + 1;//自由元个数
}
ll quick(ll a, ll b, ll p = mod)
{
ll s = 1;
while(b)
{
if(b & 1) s = s * a % p;
a = a * a % p;
b >>= 1;
}
return s;
}
void work()
{
scanf("%d %d", &n, &m);
--n, --m;
for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
build();
int r = gauss(row, col);
if(r == -1) printf("0\n");
else printf("%lld\n", quick(2, r));
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
int T; scanf("%d", &T);
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
bitset 优化
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e6;
const int N = (int)17;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
int n, m;
char s[N + 5][N + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int row, col;
bitset<614> a[2 * (N + 1) * (N + 1) + 5];
inline int id(int x1, int y1, int x2, int y2)
{
if(x1 > x2) swap(x1, x2);
if(y1 > y2) swap(y1, y2);
if(x1 == x2) return (x1 - 1) * m + y1;
else return (n + 1) * m + (x1 - 1) * (m + 1) + y1;
}
void build()
{
row = 0, col = (n + 1) * m + n * (m + 1);
for(int i = 1; i <= n + 1; ++i)
{
for(int j = 1; j <= m + 1; ++j)
{
++row;
a[row].reset();
for(int k = 0, x, y; k < 4; ++k)
{
x = i + dx[k], y = j + dy[k];
if(x < 1 || x > n + 1 || y < 1 || y > m + 1) continue;
a[row].set(id(x, y, i, j));
}
}
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(s[i][j] == '.') continue;
++row;
a[row].reset();
a[row].set(id(i, j, i, j + 1));
a[row].set(id(i, j, i + 1, j));
a[row].set(id(i, j + 1, i + 1, j + 1));
a[row].set(id(i + 1, j, i + 1, j + 1));
a[row].set(col + 1, s[i][j] - '0');
}
}
// for(int i = 1; i <= row; ++i)
// {
// bool f = 0;
// for(int j = 1; j <= col; ++j)
// {
// if(!a[i][j]) continue;
// if(f) printf(" ^ ");
// printf("x(%d)", j);
// f = 1;
// }
// printf(" = 0\n");
// }
}
int gauss(int n, int m)
{
int c, r;
for(c = 1, r = 1; c <= m; ++c)
{
int t = r;
for(int i = r; i <= n; ++i)
{
if(a[i][c]) t = i;
}
if(!a[t][c]) continue;
swap(a[t], a[r]);
for(int i = 1; i <= n; ++i)
{
if(i == r) continue;
if(a[i][c]) a[i] ^= a[r];
}
++r;
}
for(int i = r; i <= n; ++i)
{
if(a[i][m + 1]) return -1;//无解
}
return m - r + 1;//自由元个数
}
ll quick(ll a, ll b, ll p = mod)
{
ll s = 1;
while(b)
{
if(b & 1) s = s * a % p;
a = a * a % p;
b >>= 1;
}
return s;
}
void work()
{
scanf("%d %d", &n, &m);
--n, --m;
for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
build();
int r = gauss(row, col);
if(r == -1) printf("0\n");
else printf("%lld\n", quick(2, r));
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
int T; scanf("%d", &T);
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
Problem D. Another thief in a Shop
题目大意
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle T} 组输入，每组给 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 和 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle k} .
有 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 个物品，价值分别为 ，每件物品有无穷多件.
![{\textstyle a[1],a[2],\cdots ,a[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92cd278a86b15266a1bdd667d0603735788d03db)
求拼凑出总价值为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle k} 的方案数.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1 \leq T \leq 100, 1 \leq n \leq 100, 1 \leq k \leq 10^{18}, 1 \leq a[i] \leq 10} .
分析
设 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle f[i][j]} 表示考虑了前 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle i} 个物品，总价值为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle j} 的方案数.
则有状态转移方程 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \begin{aligned} f[i][j] = \sum_{l = 0}^{\lfloor \frac{j}{a[i]} \rfloor}{f[i - 1][j - l \times a[i]]} \end{aligned}} .
接下来这一步被题解惊艳到了，拉格朗日插值！！！
但体会一下也就明白了，还是很妙的感觉.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e2;
const int N = (int)5e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
int n; ll k;
int a[M + 5];
int f[N + 5];
int y[M + 5];
int pre[M + 5];
int suf[M + 5];
int fac[M + 5];
int inv[M + 5];
int invfac[M + 5];
void init()
{
fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;
for(int i = 2; i <= M; ++i)
{
fac[i] = 1ll * fac[i - 1] * i % mod;
inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
invfac[i] = 1ll * invfac[i - 1] * inv[i] % mod;
}
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int Lagrange(int n, ll k)
{
if(k <= n + 1) return y[k];
pre[0] = 1; for(int i = 1; i <= n + 1; ++i) pre[i] = (k - i) % mod * pre[i - 1] % mod;
suf[n + 2] = 1; for(int i = n + 1; i >= 1; --i) suf[i] = (k - i) % mod * suf[i + 1] % mod;
int ans = 0, cur;
for(int i = 1; i <= n + 1; ++i)
{
cur = 1ll * pre[i - 1] * suf[i + 1] % mod * invfac[i - 1] % mod * invfac[n + 1 - i] % mod;
if(n + 1 - i & 1) cur *= -1;
cur = 1ll * cur * y[i] % mod;
ans = (ans + cur) % mod;
}
ans = (ans % mod + mod) % mod;
return ans;
}
void work()
{
scanf("%d %lld", &n, &k);
int lcm = 1;
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), lcm = lcm / gcd(lcm, a[i]) * a[i];
memset(f, 0, sizeof(f)); f[0] = 1;
int r = lcm * n;
for(int i = 1; i <= n; ++i)
{
for(int j = a[i]; j <= r; ++j) f[j] = (f[j] + f[j - a[i]]) % mod;
}
for(int i = k % lcm; i < r; i += lcm) y[i / lcm + 1] = f[i];
printf("%d\n", Lagrange(n - 1, k / lcm + 1));
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
init();
int T; scanf("%d", &T);
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
Problem E. Minimum spanning tree
题目大意
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle T} 组输入，每组给出一个 .
点的编号为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1, 2, \cdots, n} ，点 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle a} 与 点 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle b} 的权值定义为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle lcm(a, b)} .
求这个图的最小生成树.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1 \leq T \leq 10^2, 2 \leq n \leq 10^7} .
分析
显然合数与它的因子连边，质数与 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 2} 连边最优.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e7;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
int cnt, prime[M + 5];
bool is_prime[M + 5];
ll f[M + 5];
void init()
{
memset(is_prime, 1, sizeof(is_prime));
cnt = is_prime[0] = is_prime[1] = 0;
for(int i = 2; i <= M; ++i)
{
if(is_prime[i]) prime[++cnt] = i;
for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
{
is_prime[i * prime[j]] = 0;
if(i % prime[j] == 0) break;
}
}
f[2] = 0;
for(int i = 3; i <= M; ++i)
{
if(is_prime[i]) f[i] = f[i - 1] + 2 * i;
else f[i] = f[i - 1] + i;
}
}
void work()
{
int n; scanf("%d", &n);
printf("%lld\n", f[n]);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
init();
int T; scanf("%d", &T);
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
return 0;
}
Problem F. Xor sum
题目大意
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle T} 组输入，每组输入有两个整数 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 和 ，接下来 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 个整数表示 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle a[1], a[2], \cdots, a[n]} .
要求找一段区间，使得这段区间的异或和不小于 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle k} ，若不存在则输出 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle -1} ，存在则找到满足上述条件最短的区间，若仍不唯一，则输出最靠左的区间.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1 \leq T \leq 10^2, 1 \leq n \leq10^5, 0 \leq k, a[i] < 2^{30}} .
分析
记 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle s[i] = a[1] \; XOR \; a[2] \; XOR \; \cdots \; XOR \;a[i]} .
则区间 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle [l, r]} 异或和不小于 等价于 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle s[r] \; XOR \; s[l-1]} 不小于 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle k} .
因此字典树维护 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle s[i]} ，节点记录当前最新的时间戳，对于两边都能走的情况就选择最新的时间戳走.
详见代码.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e5;
const int N = (int)29;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
struct tnode
{
int nx[2], stamp;
} tree[M * 31 + 5];
int cnt;
int n, k;
void insert(int p, int d, int x, int stamp)
{
if(d == -1) return;
int v = (x>>d&1);
if(!tree[p].nx[v])
{
tree[p].nx[v] = ++cnt;
tree[tree[p].nx[v]].nx[0] = 0;
tree[tree[p].nx[v]].nx[1] = 0;
tree[tree[p].nx[v]].stamp = 0;
}
tree[p].stamp = stamp;
insert(tree[p].nx[v], d - 1, x, stamp);
if(d == 0)
{
tree[tree[p].nx[v]].stamp = stamp;
}
}
inline int setZero(int x, int k)
{
return x&(~(1<<k));
}
inline int setOne(int x, int k)
{
return x|(1<<k);
}
int queryMx(int x, int p, int d)
{
for(int i = d, v; i >= 0; --i)
{
v = (x>>i&1);
if(tree[p].nx[!v]) p = tree[p].nx[!v], x = setOne(x, i);
else p = tree[p].nx[v], x = setZero(x, i);
}
return x;
}
int mi, l, r;
void query(int x, int stamp, bool f = 0)
{
int p = 0;
for(int i = N, vk, vx; i >= 0; --i)
{
vk = (k>>i&1);
vx = (x>>i&1);
bool canZero = 0, canOne = 0;
if(tree[p].nx[vx]) canZero = queryMx(setZero(x, i), tree[p].nx[vx], i - 1) >= k;
if(tree[p].nx[!vx]) canOne = queryMx(setOne(x, i), tree[p].nx[!vx], i - 1) >= k;
if(canZero && canOne)
{
if(tree[tree[p].nx[vx]].stamp > tree[tree[p].nx[!vx]].stamp) p = tree[p].nx[vx], x = setZero(x, i);
else p = tree[p].nx[!vx], x = setOne(x, i);
}
else if(canZero) p = tree[p].nx[vx], x = setZero(x, i);
else if(canOne) p = tree[p].nx[!vx], x = setOne(x, i);
else return;
}
if(mi > stamp - tree[p].stamp)
{
mi = stamp - tree[p].stamp;
l = tree[p].stamp + 1, r = stamp;
}
}
void work()
{
mi = inf, l = -1, r = -1;
cnt = tree[0].nx[0] = tree[0].nx[1] = tree[0].stamp = 0;
scanf("%d %d", &n, &k);
insert(0, N, 0, 0);
int s = 0;
for(int i = 1, a; i <= n; ++i)
{
scanf("%d", &a);
s ^= a;
query(s, i);
insert(0, N, s, i);
}
if(mi == inf) printf("-1\n");
else printf("%d %d\n", l, r);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
int T; scanf("%d", &T);
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
return 0;
}
Problem G. Pass!
题目大意
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle T} 组输入，每组有两个整数 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 和 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x} .
一共有 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 个人和 个球，初始球在第 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1} 人脚下，每秒拥有球的那个人会把球传给另一个人.
经过 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle t} 秒后，球又回到了第 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1} 个人脚下，方案数为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x} .
现在给出 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x} 要求反解最小非负整数 .
分析
设 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle f[i][0]}
表示第 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle i}
秒末球不在第 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1}
个人脚下的方案数，
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \quad f[i][1]}
表示第 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle i}
秒末球在第 个人脚下的方案数.
则有如下转移方程：
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ \begin{aligned} f[0][1] &= 1 \\ f[i][0] &= (n - 2)f[i - 1][0] + (n - 1)f[i - 1][1] \\ f[i][1] &= f[i - 1][0] \end{aligned} \right. \rightarrow \left\{ \begin{aligned} f[1][0] &= n - 1 \\ f[2][0] &= (n - 1)(n - 2) \\ f[i][0] &= (n - 2)f[i - 1][0] + (n - 1)f[i - 2][0] \quad i \geq 3\\ \end{aligned} \right.}
学了一下二阶线性递推式的通项求法，夙愿清单减减.
于是可以得到 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle f[i][0]} 的解析式为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle f[i][0] = \frac{(n -1)^2}{n}(n-1)^{i - 1} + \frac{n - 1}{n}(-1)^{i - 1}} .
又由 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle f[i][1] = f[i - 1][0]} 得
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{aligned} f[i][1] &= f[i - 1][0] \\ &= \frac{(n -1)^2}{n}(n-1)^{i - 2} + \frac{n - 1}{n}(-1)^{i - 2} \quad i \geq 0 \\ &= \left\{ \begin{aligned} \frac{(n -1)^i}{n} &- \frac{n - 1}{n} \quad i \; is \; odd \\ \frac{(n -1)^i}{n} &+ \frac{n - 1}{n} \quad i \; is \; even \\ \end{aligned} \right. \\ &= \left\{ \begin{aligned} \frac{(n -1)^{2k+1}}{n} &- \frac{n - 1}{n} \quad i = 2k+1, k \geq 0\\ \frac{(n -1)^{2k}}{n} &+ \frac{n - 1}{n} \quad i = 2k, k \geq 0\\ \end{aligned} \right. \\ &\stackrel{Only \; need \; to \; solve}{\longrightarrow} \left\{ \begin{aligned} (n-1)^{2k} &\equiv \frac{nx + n - 1}{n - 1} \; (mod\; p) \\ (n-1)^{2k} &\equiv nx - n + 1\; (mod \; p) \\ \end{aligned} \right. \\ \end{aligned}} 至此套上 BSGS 即可.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e5;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
struct hashTable
{
const static int M = (int)1e5;
const static int N = (int)31601;
int head[N + 5], cnt;
struct node
{
int v, w, nx;
} a[M + 5];
void init()
{
cnt = 0;
memset(head, -1, sizeof(head));
}
void add(int v, int w)
{
for(int i = head[w % N]; ~i; i = a[i].nx)
{
if(a[i].w == w)
{
a[i].v = v;
return;
}
}
a[cnt].v = v;
a[cnt].w = w;
a[cnt].nx = head[w % N];
head[w % N] = cnt++;
}
int tofind(int w)
{
for(int i = head[w % N]; ~i; i = a[i].nx)
{
if(a[i].w == w) return a[i].v;
}
return -1;
}
} H;
struct LOG
{
ll quick(ll a, ll b, ll p = mod)
{
ll s = 1;
while(b)
{
if(b & 1) s = s * a % p;
a = a * a % p;
b >>= 1;
}
return s;
}
ll inv(ll n, ll p = mod)
{
return quick(n, p - 2, p);
}
int k = 31596, t;
void init(int a, int p)
{
H.init();
for(int i = 0, j = 1; i < k; ++i)
{
H.add(i, j);
j = 1ll * j * a % p;
}
t = quick(a, k, p);
}
int BSGS(int a, int b, int p)
{
a = (1ll * a % p + p) % p, b = (1ll * b % p + p) % p;
if(b == 1) return 0;
for(int i = 1, j = t * inv(b, p) % p, h; i <= k; ++i)
{
h = H.tofind(j);
if(~h && 1ll * k * i > h && !((1ll * k * i - h)&1)) return 1ll * k * i - h;
j = 1ll * j * t % p;
}
return -1;
}
} B;
int n, x;
int calOdd()
{
int a = (1ll * n * x % mod + n - 1 + mod) % mod * B.inv(n - 1) % mod;
int x = B.BSGS(n - 1, a, mod);
if(x == -1) return inf;
return x + 1;
}
int calEven()
{
int a = (1ll * n * x % mod - n + 1 + mod) % mod;
int x = B.BSGS(n - 1, a, mod);
if(x == -1) return inf;
return x;
}
void work()
{
scanf("%d %d", &n, &x);
B.init(n - 1, mod);
int odd = calOdd(), even = calEven();
int mi = min(odd ,even);
if(mi == inf) printf("-1\n");
else printf("%d\n", mi);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
int T; scanf("%d", &T);
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
Problem H. Maximal submatrix
题目大意
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle T} 组输入，每组输入一个 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n \times m} 的矩阵.
求一个最大子矩阵，这个子矩阵每一列中的元素递增，输出最大子矩阵的大小.
Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle 1\leq T\leq 10,1\leq n,m\leq 2000} .
分析
单调栈经典题了.
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)2e3;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
int n, m;
int a[M + 5][M + 5];
int b[M + 5][M + 5];
int s[M + 5], w[M + 5], p;
int cal(int a[])
{
a[m + 1] = p = 0;
int ans = 0;
for(int i = 1; i <= m + 1; ++i)
{
if(a[i] > s[p])
{
s[++p] = a[i], w[p] = 1;
}
else
{
int width = 0;
while(s[p] > a[i])
{
width += w[p];
ans = max(ans, width * s[p]);
p--;
}
s[++p] = a[i], w[p] = width + 1;
}
}
return ans;
}
void work()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
for(int j = 1; j <= m; ++j)
{
b[1][j] = 1;
for(int i = 2; i <= n; ++i)
{
if(a[i][j] >= a[i - 1][j]) b[i][j] = b[i - 1][j] + 1;
else b[i][j] = 1;
}
}
int mx = 0;
for(int i = 1; i <= n; ++i)
{
mx = max(mx, cal(b[i]));
}
printf("%d\n", mx);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
int T; scanf("%d", &T);
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
return 0;
}
Problem I. KD-Graph
题目大意
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle T} 组输入，每组输入 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n, m, k} 表示 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 个点 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle m} 条边的有权联通无向图.
接下来 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle m} 行，每行三个整数 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle u, v, w} 表示无向边的两个端点和边权.
一个图被称为 KD 图当且仅当 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 个点可以不重不漏地分成 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle K} 组且组内两两点之间存在一条路径，满足这条路径的最大边权小于等于 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle D} ，不同组的每两点则不存在这样的路径.
要求计算最小的非负整数 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle D} ，若不存在输出 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle -1} .
分析
赛时一开始二分 + BFS，结果 TLE...
换成二分 + 并查集，常数小了点，得到 AC.
代码实现
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e5;
const int N = (int)5e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
int n, m, k;
struct enode
{
int u, v, w;
} Edge[N + 5];
int fa[M + 5];
int rk[M + 5];
int tofind(int x)
{
if(x == fa[x]) return x;
return fa[x] = tofind(fa[x]);
}
int cal(int lim)
{
for(int i = 1; i <= n; ++i) fa[i] = i;
for(int i = 1, u, v; i <= m; ++i)
{
u = Edge[i].u, v = Edge[i].v;
if(Edge[i].w <= lim)
{
u = tofind(u), v = tofind(v);
if(u != v)
{
if(rk[u] > rk[v]) swap(u, v);
fa[u] = v, rk[v] = max(rk[v], rk[u] + 1);
}
}
}
int cnt = 0;
for(int i = 1; i <= n; ++i) if(fa[i] == i) ++cnt;
return cnt;
}
void work()
{
n = read(), m = read(), k = read();
int l = 0, r = 0, mid;
for(int i = 1; i <= m; ++i)
{
Edge[i].u = read(), Edge[i].v = read(), Edge[i].w = read();
r = max(r, Edge[i].w);
}
while(l < r)
{
mid = (l + r) >> 1;
if(cal(mid) <= k) r = mid;
else l = mid + 1;
}
if(cal(r) == k) printf("%d\n", r);
else printf("-1\n");
}
int main()
{
// cout << 5 * log2(inf) * (M + 2 * N) << "\n";
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
int T = read();
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
Problem J. zoto
题目大意
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle T} 组输入，每组输入 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n, m} 表示二维平面上有 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 个整数点和 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle m} 次询问.
接下来 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 行，每行一个非负整数 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle fx[i]} ，表示有一个整数点 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\textstyle (i,fx[i])} .
接下来 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle m} 行，每行四个整数 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x0, y0, x1, y1} 表示查询 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (x0, y0)} 与 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle (x1, y1)} 围成的矩阵里有多少个不同的 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle y} 值.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1 \leq T \leq 5, 1 \leq n, m, x0, x1 \leq 10^5, 0 \leq fx[i], y0, y1 \leq 10^5} .
分析
一开始用莫队 + 线段树喜提 TLE.
正解是莫队 + 分块.
分块支持 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle O(1)} 修改 + Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle O(\sqrt{10^5})} 查询.
小收获：莫队的修改次数很多，查询次数较少，应选择修改较快的数据结构进行维护.
代码实现
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
void print(int n)
{
if(n < 0)
{
putchar('-');
print(-n);
}
else
{
if(n > 9) print(n / 10);
putchar(n % 10 + '0');
}
}
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e5;
const int N = (int)320;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
int n, m, xblock, yblock, yblockCnt;
int a[M + 5];
int ans[M + 5];
struct qnode
{
int l, r, a, b, id;
bool operator<(const qnode& b)const
{
return l / xblock == b.l / xblock ? (r == b.r ? 0 : ((l / xblock) & 1) ^ (r < b.r)) : l < b.l;
}
} q[M + 5];
int id[M + 5];
int num[M + 5];
int nums[N + 5];
int mx;
void init()
{
yblock = (int)sqrt(mx), yblockCnt = (mx + yblock) / yblock;
for(int i = 0; i <= mx; ++i)
{
id[i] = i / yblock;
num[i] = 0;
}
for(int i = 0; i < yblockCnt; ++i) nums[i] = 0;
}
void add(int x)
{
if(++num[a[x]] == 1) ++nums[id[a[x]]];
}
void del(int x)
{
if(--num[a[x]] == 0) --nums[id[a[x]]];
}
int query(int l, int r)
{
int ans = 0;
if(id[r] - id[l] + 1 <= 2)
{
for(int i = l; i <= r; ++i) if(num[i]) ++ans;
}
else
{
for(int i = l; i <= n && id[i] == id[l]; ++i) if(num[i]) ++ans;
for(int i = r; i >= 1 && id[i] == id[r]; --i) if(num[i]) ++ans;
for(int i = id[l] + 1; i < id[r]; ++i) ans += nums[i];
}
return ans;
}
void work()
{
n = read(), m = read(); xblock = (int)sqrt(n);
for(int i = 1; i <= n; ++i) a[i] = read();
mx = 1;
for(int i = 1; i <= m; ++i)
{
q[i].l = read(), q[i].a = read(), q[i].r = read(), q[i].b = read();
mx = max(mx, q[i].b);
q[i].id = i;
}
init();
sort(q + 1, q + m + 1);
int l = 1, r = 0;
for(int i = 1; i <= m; ++i)
{
while(r < q[i].r) add(++r);
while(r > q[i].r) del(r--);
while(l < q[i].l) del(l++);
while(l > q[i].l) add(--l);
ans[q[i].id] = query(q[i].a, q[i].b);
}
for(int i = 1; i <= m; ++i) print(ans[i]), putchar('\n');
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
int T; scanf("%d", &T);
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
Problem K. Necklace of Beads
题目大意
组输入，每组给出 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 和 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle k} .
有红蓝绿三种颜色的珠子，红蓝珠子有无穷多个，绿色珠子只有 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle k} 个，要求串成 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 个珠子的项链.
两个项链如果可以通过旋转得到则认为是一种方案.
求方案数.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1 \leq T \leq 10, 1 \leq n, k \leq 10^6} .
分析
显然Burnside 引理，于是
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{aligned} ANS &= \frac{1}{n}\sum_{i=0}^{n - 1}{\sum_{j=0}^{\lfloor \frac{k}{n/gcd(n, i)} \rfloor}{f(gcd(n, i), j)}} \\ &= \frac{1}{n}\sum_{d=1}^{n}{\varphi(\frac{n}{d})\sum_{j=0}^{\lfloor \frac{k}{n/d} \rfloor}{f(d, j)}} \end{aligned}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle f(n, m)} 表示长度为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 的环，绿色珠子有 个的合法方案数.
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle g(n, m)} 表示长度为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle n} 的序列，选 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle m} 个互不相邻位置的方案数.
对绿色珠子的位置分类讨论：
- 假设绿色珠子放在 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1} 号位置，则 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 2, n} 这两个位置不能放绿色珠子，并且绿色珠子把环分割为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle m} 段，每段的方案数为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 2} ，因此总方案数为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle g(n - 3, m - 1) \times 2^{m}} .
- 假设绿色珠子放在 号位置，根据对称性，方案数同 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 1.}
- 除上述两种情况之外，方案数为 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle g(n - 2, m) \times 2^{m}} .
因此 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle f(n, m) = g(n - 3, m - 1) \times 2^{m+1} + g(n - 2, m) \times 2^{m}} .
由插空法可得 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle g(n, m) = \binom{n - m + 1}{m}} .
预处理出欧拉函数和阶乘，逆元，阶乘逆元.
时间复杂度 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle O(10^6 + T\sqrt{n})} .
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int M = (int)1e6;
const int N = (int)1e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
bool is_prime[M + 5];
int cnt, prime[M + 5];
int phi[M + 5];
int fac[M + 5], inv[M + 5], invfac[M + 5];
void init()
{
phi[1] = 1;
memset(is_prime, 1, sizeof(is_prime));
cnt = is_prime[0] = is_prime[1] = 0;
fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;
for(int i = 2; i <= M; ++i)
{
fac[i] = 1ll * fac[i - 1] * i % mod;
inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
invfac[i] = 1ll * invfac[i - 1] * inv[i] % mod;
if(is_prime[i])
{
prime[++cnt] = i;
phi[i] = i - 1;
}
for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
{
is_prime[i * prime[j]] = 0;
if(i % prime[j] == 0)
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
int c(int n, int m)
{
if(n < 0 || m < 0 || n < m) return 0;
return 1ll * fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
void work()
{
int n, k; scanf("%d %d", &n, &k);
int ans = 0;
for(int d = 1, two, r, f, dd; 1ll * d * d <= n; ++d)
{
if(n % d) continue;
two = 1, r = 1ll * k * d / n, f = (!(d&1)) * 2;
for(int j = 1; j <= r; ++j)
{
two = 2ll * two% mod;
f = (f + 2ll * two * c(d - j - 1, j - 1) + 1ll * two * c(d - j - 1, j)) % mod;
}
ans = (ans + 1ll * f * phi[n / d]) % mod;
if(d * d == n) continue;
dd = n / d;
two = 1, r = 1ll * k * dd / n, f = (!(dd&1)) * 2;
for(int j = 1; j <= r; ++j)
{
two = 2ll * two% mod;
f = (f + 2ll * two * c(dd - j - 1, j - 1) + 1ll * two * c(dd - j - 1, j)) % mod;
}
ans = (ans + 1ll * f * phi[n / dd]) % mod;
}
ans = 1ll * ans * inv[n] % mod;
printf("%d\n", ans);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
init();
int T; scanf("%d", &T);
for(int ca = 1; ca <= T; ++ca)
{
// printf("Case #%d:\n", ca);
work();
}
// work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}