2021牛客多校第一场
MorphLing
7月 18, 2021
A. Alice and Bob
题意：给出两堆石子a、b，两名玩家轮流取石子，取法是在一堆石子里取k个，并在另一堆石子里取$s\times k$个$(s\ge 0)$，给定a、b，问先后手谁必胜
观察得到，对于一堆石子为i个，那么只有最多一个对应的j，使得两堆石子为i、j时为必败态，于是必败态总数不超过n。对于每一个必败态，先枚举k，再枚举s，得到所有能一步达到该状态的必胜态，复杂度为调和级数$O(n\log n)$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 5e3 + 5;
int loss[N][N], win[N][N];
int vis[N], to[N];
int main() {
for (int i = 2; i <= 5000; i++) {
int j = i + 1;
for (; j <= 5000; j++) {
if (!win[i][j]) break;
}
if (j <= 5000) {
to[i] = j;
for (int k = 1; i + k <= 5000; k++) {
for (int p = 0; j + p <= 5000; p += k) {
int xx = i + k, yy = j + p;
if (xx > yy) swap(xx, yy);
win[xx][yy] = 1;
}
}
for (int k = 1; j + k <= 5000; k++) {
for (int p = 0; i + p <= 5000; p += k) {
int xx = i + p, yy = j + k;
if (xx > yy) swap(xx, yy);
win[xx][yy] = 1;
}
}
}
}
int T; scanf("%d", &T);
while(T--) {
int x, y; scanf("%d %d", &x, &y);
if (x > y) swap(x, y);
if (to[x] == y) printf("Bob\n");
else printf("Alice\n");
}
return 0;
}
G. Game of Swapping Numbers
H. Hash Function
题意：给定n个数$(0\le a_i\le 500000)$，求出最小的$seed$，使得每个数$a_i mod seed$结果不同
$seed$满足条件的充要条件是，对于任意两个数之差的绝对值$|a_i-a_j|，$$seed$都不是其因数
fft加速，求出某个数是否是任意两数之差，记录在一个数组里，然后从小到大枚举$seed$，若每个$k\times seed$都不存在，则将$seed$作为答案，复杂度类似于A题中的调和级数
#include <bits/stdc++.h>
#define fo(i, a, b) for (int i = a; i <= b; i++)
using namespace std;
typedef complex<double> cp;
const int N = 3e6 + 5;
const double pi = acos(-1);
cp a[N], b[N];
int n, m, limit, rev[N];
bool vis[N];
void fft(cp *a, int n, int inv)
{
int bit = 0;
while ((1 << bit) < n) bit++;
for (int i = 0; i < n; i++) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
if (i < rev[i]) swap(a[i], a[rev[i]]);//不加这条if会交换两次（就是没交换）
}
for (int mid = 1; mid < n; mid *= 2) {//mid是准备合并序列的长度的二分之一
cp temp(cos(pi / mid), inv * sin(pi / mid));//单位根，pi的系数2已经约掉了
for (int i=0;i<n;i+=mid*2)//mid*2是准备合并序列的长度，i是合并到了哪一位
{
cp omega(1,0);
for (int j=0;j<mid;j++,omega*=temp)//只扫左半部分，得到右半部分的答案
{
cp x=a[i+j],y=omega*a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
a[x + 500000].real(1);
b[-x + 500000].real(1);
}
limit = 1; while(limit < 1500000) limit <<= 1;
fft(a, limit, 1); fft(b, limit, 1);
for (int i = 0; i <= limit; i++) a[i] *= b[i];
fft(a, limit, -1);
for (int i = 500000; i <= 1500000; i++) {
int now = (int)(a[i].real() / limit + 0.5);
if (now) vis[abs(i - 1000000)] = 1;
}
for (int i = 1; i <= 1500001; i++) {
bool ok = 1;
for (int j = i; j <= 1500001; j += i) {
if (vis[j]) {
ok = 0;
break;
}
}
if (ok) {
printf("%d\n", i);
break;
}
}
return 0;
}
I. Increasing Subsequence
题意：给出排列P，两人轮流取数，要求取出的数比之前任何取的数都大，且在自己上次取的数的右边，若有多种取法则等概率选择，无人可取时终止，问期望轮数。
首先按照数值大小，从小到大排序，对应位置上的数为该数原来的位置。这样的话，在新的排列上考虑该问题，一个合法的选择方案一定是从左往右依次选择，且方案中奇数和偶数位上的数一定是分别递增的。
考虑dp，$f[i][j]$表示【最后一次选择j，倒数第二次选择i】这种情况发生的概率，那么下一个选择的k必须满足p[k]>p[i] && k > j，并且转移时要把$f[i][j]$乘上转移过去的概率【即在j右边，且p[l]>p[i]的l的个数，记作$num[i][j]$，可以$O(n^2)$预处理】，朴素把这个dp做完是$O(n^3)$的。
进一步优化，考虑从$f[i][j]$到$f[j][k]$的转移，发现在 $ i < j < k $ 的前提下，能够转移到$f[j][k]$的$f[i][j]$只需要满足$p[k] > p[i]$，于是想到在可以每个点都开一个树状数组去协助转移，每次得到$f[i][j]$后，修改j对应的树状数组中的p[i]位置，计算$f[j][k]$则查询j对应的树状数组中$[0,p[k]-1]$的区间和，得到一个$O(n\log n)$的做法，需要常数非常优秀才能通过（例如预处理所有逆元）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 5e3 + 5;
const int mod = 998244353;
const int MOD = 998244353;
const double pi = acos(-1);
int add(int x, int y){return x + y >= mod? x + y - mod: x + y;}
int sub(int x, int y){return x - y < 0? x - y + mod: x - y;}
int mul(int x, int y){return 1ll * x * y % mod;}
int qpow(int a, int b)
{
int ans = 1;
while(b)
{
if(b & 1)
ans = mul(ans,a);
b >>= 1;
a = mul(a,a);
}
return ans;
}
/////////////////////////////////////////
struct Node {
int v, pos;
bool operator < (Node &N) const {
return v < N.v;
}
}a[N];
int num[N][N], n, p[N];
struct BIT {
#define lowbit(x) (x & (-x))
int sum[N];
void change(int p,int v)
{
while (p<N)
{
sum[p]=add(sum[p],v);
p+=lowbit(p);
}
}
int query(int p)
{
int res=0;
while (p)
{
res=add(res,sum[p]);
p-=lowbit(p);
}
return res;
}
}bit[N];
int ans, invn, inv[N];
int main() {
scanf("%d", &n);
invn = qpow(n, MOD - 2);
for (int i = 1; i <= n; i++) inv[i] = qpow(i, MOD - 2);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i].v);
a[i].pos = i;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
p[i] = a[i].pos;
}
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
num[j][i] = num[j][i + 1] + (p[i + 1] > p[j]);
}
}
for (int i = 1; i <= n; i++) {
num[0][i] = n - i;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i - 1; j++) {
int pos = 0;
if (j == 0) {
pos = invn;
}
else {
pos = bit[j].query(p[i] + 1);
}
ans = add(ans, pos);
bit[i].change(p[j] + 2, mul(pos, inv[num[j][i]]));
}
}
printf("%d\n", ans);
return 0;
}
实际上还可以用桶替代树状数组，每次外层循环i修改后，重新扫一遍$f[j][i]$，把原先用树状数组记录的信息记录在桶里，同样可以完成转移，复杂度$O(n^2)$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N = 5e3 + 5;
const int mod = 998244353;
const int MOD = 998244353;
const double pi = acos(-1);
int add(int x, int y){return x + y >= mod? x + y - mod: x + y;}
int sub(int x, int y){return x - y < 0? x - y + mod: x - y;}
int mul(int x, int y){return 1ll * x * y % mod;}
int qpow(int a, int b)
{
int ans = 1;
while(b)
{
if(b & 1)
ans = mul(ans,a);
b >>= 1;
a = mul(a,a);
}
return ans;
}
/////////////////////////////////////////
struct Node {
int v, pos;
bool operator < (Node &N) const {
return v < N.v;
}
}a[N];
int num[N][N], n, p[N];
int ans, invn, inv[N], sum[N], f[N][N];
int main() {
scanf("%d", &n);
invn = qpow(n, MOD - 2);
for (int i = 1; i <= n; i++) inv[i] = qpow(i, MOD - 2);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i].v);
a[i].pos = i;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
p[i] = a[i].pos;
}
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
num[j][i] = num[j][i + 1] + (p[i + 1] > p[j]);
}
}
for (int i = 1; i <= n; i++) {
num[0][i] = n - i;
f[0][i] = inv[n];
}
for (int i = 1; i <= n - 1; i++) {
memset(sum, 0, sizeof(sum));
for (int j = 0; j < i; j++) {
sum[p[j]] = add(sum[p[j]], mul(f[j][i], inv[num[j][i]]));
}
for (int j = 1; j <= n; j++) sum[j] = add(sum[j - 1], sum[j]);
for (int j = i + 1; j <= n; j++) {
f[i][j] = sum[p[j] - 1];
ans = add(ans, f[i][j]);
}
}
printf("%d\n", add(ans, 1));
return 0;
}
其实一开始重新排列也不是必要的，而且也可以从后往前推，并得到一些常数更加优秀的做法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010;
const ll mod = 998244353;
int n, p[N];
ll inv[N], f[N][N], sum[N], cnt[N]; //f[i][j]表示上个人选了p[i]，当前应选位置>=j的局面的期望轮数
ll qpow(ll a, ll b = mod - 2) {
ll ret = 1;
while(b) {
if(b & 1) ret = ret * a % mod;
b >>= 1; a = a * a % mod;
}
return ret;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &p[i]), inv[i] = qpow(i);
for(int i = n; i >= 1; i--) {
ll sj = 0, cj = 0;
for(int j = n; j >= 0; j--) {
if(i == j) continue;
if(p[i] > p[j]) {
f[i][j] = (1 + sj * inv[cj]) %mod;
sum[j] = (sum[j] + f[i][j]) % mod;
cnt[j]++;
}
else { //p[i] < p[j]
f[i][j] = (1 + sum[j] * inv[cnt[j]]) % mod;
sj = (sj + f[i][j]) % mod;
cj++;
}
}
}
ll ans = 0;
for(int i = 1; i <= n; i++) ans = (ans + f[i][0]) % mod;
printf("%lld", ans * inv[n] % mod);
return 0;
}
K. Knowledge Test about Match
题意：随机给一个权值范围为0~n-1的序列，用一个0~n-1和它匹配，要求$\sqrt{|a_i-(i-1)|}$之和最小
瞎搞题，枚举差值d从0~n-1，优先匹配差值较小的匹配
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
const int MOD = 998244353;
int n, a[N], b[N];
bool vis[N], vis2[N];
int main() {
int T; scanf("%d", &T);
while(T--) {
scanf("%d", &n);
memset(vis, 0, sizeof(vis));
memset(vis2, 0, sizeof(vis2));
memset(b, 0, sizeof(b));
for (int i = 0; i <= n - 1; i++) scanf("%d", &a[i]);
for (int i = 0; i <= 2 * n; i++) {
for (int j = 0; j <= n - 1; j++) {
if (vis2[j]) continue;
if (a[j] + i <= n - 1 && !b[a[j] + i]) {
b[a[j] + i] = a[j];
vis2[j] = 1;
ans += sqrt(i);
continue;
}
if (a[j] - i >= 0 && !b[a[j] - i]) {
b[a[j] - i] = a[j];
vis2[j] = 1;
ans += sqrt(i);
continue;
}
}
}
for (int i = 0; i <= n - 1; i++) printf("%d ", b[i]);
}
return 0;
}