Atcoder abc226

發表於 更新於 分類於 ， Disqus： 文章字數： 2.7k 所需閱讀時間 ≈ 9 分鐘
F(DP,组合数,gcd)G(贪心)H(概率论,微积分)

F - Score of Permutations

排列P,

初始,i号人有球i

每次 所有 i != pi 的人, 把球给pi号人

在 > 0 次后,如果所有人又是i号人有球i, 那么就停止

分数 = 最小的次数

求所有排列方案 的分数的k次方的和

mod 998244353

限制

N 50

k 1e4

2 s

1024 mb

我的思路

很明显, 交换的圈构成环, 次数 = lcm(每个环长)

N 很小, 是不是可以枚举因数

dp[i][j] = 使用i个,最大是j,的{lcm,方案数}

dp[i][j] 贡献来自 dp[i- tm][m],m > j, t > 0, 即n-i+tm个中选tm个, 然后分成t组每组m个

因为组合tm中分成t组,每组m个

这样想,tm中最小的作为开头,依次剩下的选m-1个, 然后剩余就是(t-1)m 同样的

这样每次考虑最小的所在环, 就不重不漏

$\binom{n-i+tm}{tm} A(tm-1,m-1) \cdot A((t-1)m-1,m-1) \cdots$

$ = \binom{n-i+tm}{tm} \frac{(tm)!}{m\cdot 2m \cdots tm}$

$ = \binom{n-i+tm}{tm} \frac{(tm)!}{m^t * t!}$

似乎就对了

代码

https://atcoder.jp/contests/abc226/submissions/33934208

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read
ll gcd(int a,int b){ return b == 0? a: gcd(b,a%b);}

map<int,mint> dp[60][60]; // dp[选最小i个][最大的环为j] = {lcm, count}
mint fac[100] = {1};
mint ifac[100];
mint binom(int n,int m) { return fac[n] * ifac[m] * ifac[n-m];}

int main(){
  rep(i,1,51) fac[i] = fac[i-1] * i;
  ifac[50] = fac[50].inv();
  per(i,0,50) ifac[i] = ifac[i+1] * (i+1);

  int n = read();
  int k = read();
  dp[0][0][1] = 1;
  rep(i,1,n+1) rep(j,1,i+1){
    mint invj = mint(j).inv();
    rep(t,1,n+1){
      int oldi = i - j*t; // [i - j*t][<j]
      if(oldi < 0) break;
      rep(k,0,j) for(auto [lcm,cnt]: dp[oldi][k]){
        dp[i][j][lcm * j / gcd(lcm,j)] += cnt * binom(n-oldi,j*t) * fac[j*t] * ifac[t] * invj.pow(t);
      }
    }
  }
  mint ans = 0;
  rep(j,1,n+1) for(auto [lcm,cnt]:dp[n][j]) ans += cnt * mint(lcm).pow(k);
  printf("%d\n",ans.val());
  return 0;
}

G - The baggage

重量1~5的物品每个Ai个

搬运能力1~5的人每个Bi个

问是否有方法, 让所有物品被至少一个人搬运,且每个人搬运的物品重量和不大于他的能力

一共T个询问

范围

T 5e4

Ai,Bi [0,10^16]

2s

1024mb

我的思路

一样看上去, 枚举或者数学题

考虑 物品重量不超过5的组合

再 组合x能力, 应该大概有 5x2^5以内的选项

每个选项有限制, 一些之间的和小于等于Bi, 一些之间的和 = Ai, 看是否有方案

似乎变成2sat? 然后是 偏序的样子, 但Ai,Bi范围大, 似乎没法那么多点

另一个从能力从小到大

能力1的只能消耗重量1,那么贪心

能力2的可以消耗 1个2,2个1,1个1, 而如果同时有1个2和2个1, 显然后面的更灵活,所以贪心消耗1个2,再消耗1

能力3的也是先1个3,然后2+1,然后剩余1

能力4的,先1个4, 问题来了, 是3+1先还是2+2先呢? 如果都考虑3+1还是2+2了, 说明4消耗完了,对5来说 5,3,2,1的处理肯定先整个5,然后先3找2,再去2+2+1

所以对于4来说,先2+2,后3+1

就这样? 似乎贪心就没了?

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;

ll a[10];
ll b[10];

vector<vector<pair<int,int> > > child[10];

void w(){
  rep(i,1,5+1) a[i] = read();
  rep(i,1,5+1) b[i] = read();

  rep(i,1,5+1) per(j,1,i+1) for(auto arr: child[j]){
    ll c = b[i];
    for(auto [v,t]:arr) c = min(c, a[v] / t);
    b[i] -= c;
    for(auto [v,t]:arr) a[v] -= c*t;
  }
  ll s = 0;
  rep(i,1,5+1) s += a[i];
  printf("%s\n",s == 0 ? "Yes" : "No");
}

int main(){
  child[1] = {
    {{1,1}} // 1
  };
  child[2] = {
    {{2,1}}, // 2
    {{1,2}} // 1+1
  };
  child[3] = {
    {{3,1}}, // 3
    {{2,1},{1,1}}, // 2+1
    {{1,3}} // 1+1+1
  };
  child[4] = {
    {{4,1}}, // 4
    {{2,2}}, // 2+2
    {{3,1},{1,1}},// 3+1
    {{2,1},{1,2}}, // 2+1+1
    {{1,4}} // 1+1+1+1
  };
  child[5] = {
    {{5,1}}, // 5
    {{4,1},{1,1}}, // 4+1
    {{3,1},{2,1}}, // 3+2
    {{3,1},{1,2}}, // 3+1+1
    {{2,2},{1,1}}, // 2+2+1
    {{2,1},{1,3}}, // 2+1+1+1
    {{1,5}} // 1+1+1+1+1
  };

  int t = read();
  while(t--) w();
  return 0;
}

但ac x15, wa x33

看起来贪假了

原因大概是{1,5} 优先级比{3,1},{1,1} 高了?

调了半天优先顺序都没对

好神奇啊这题

题解

还是贪心,

但是说

5拿5

4拿4

5拿4

3拿3

5拿3

4拿3

5拿2

4拿2

3拿2

2拿2

5拿1

4拿1

3拿1

2拿1

1拿1

????????????? 学不会

tourist 都wa了一次

代码

https://atcoder.jp/contests/abc226/submissions/33953558

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;

ll a[10];
ll b[10];

void pack(ll x, ll y) {
  ll c = min(a[x], b[y]);
  a[x] -= c;
  b[y] -= c;
  if(y-x) b[y - x] += c; // c个工人的负重还剩下y-x
  return;
}

void w(){
  rep(i,1,5+1) a[i] = read();
  rep(i,1,5+1) b[i] = read();

  per(i,1,5+1){
    pack(i,i);
    per(j,i+1,5+1) pack(i,j);
    pack(i,i);
  }

  bool ans = true;
  rep(i,1,5+1)if (a[i] > 0)ans = false;
  printf("%s\n", ans? "Yes": "No");
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

H - Random Kth Max

N 个随机量

Xi 均匀分布于[Li,Ri]的实数区间

输出 期望 E(第k大的元素) mod 998244353

范围

N 50

Li,Ri 100

2 s

1024 mb

我的思路

概率论, 日常不会

如果指定了哪个是第k大的, 那么剩下有k-1个小于等于它的(虽然等于可能带来重复计算,但是在样本区间是连续的里面,单个的不会影响

但问题是如果制定了第k大的,它依然是区间而不是值

$v_i \in [L_i,R_i]$

其它的不大于它的概率为 $p_j = (v_i-l_j)/(r_j-l_j)$

感觉上会变成v的k次方的表达式

然后再积分??

不会了

题解

考虑其分布函数 $F_X(x) = P(X \le x) = x$

$P(a < X \le b ) = F(b) - F(a)$

$F(x) = \int_{-\infty}^x f(t)dt.$

若$X$在$[a,b]$之间分布

$1 = \int_{a}^b f(x)dx,$

$E \lbrack X \rbrack = \int_{a}^b xf(x)dx,$

$ = \int_{a}^b x d F(x) $

$ = (bF(b) - aF(a)) - \int_{a}^b F(x) d x $

$ = b - \int_{a}^b F(x) d x $

$ = a + (b - a) + \int_{a}^b -F(x) d x $

$ = a + \int_{a}^{b} (1 - F(x)) dx.$

考虑子问题

N个随机变量都是 (0,1) 随机分布, 求第k大的数的期望

比x大的期望是$1-x$ 比x小的期望是$x$

因此第k大的数比x大的期望是 $1-F(x) = \overline{F}(x) = \sum_{i=k}^n \binom{n}{i} (1-x)^i x^{n-i}.$

解释一下,就是n个中选$i = [k\cdots n]$个大于x, 而剩余的小于x

根据上面的期望表达式有(这里用了beta function

$\begin{aligned}
f(n,k) &= E\lbrack X \rbrack \\
&= \int_{0}^{1} \left\lbrace \sum_{i=k}^n \binom{n}{i} (1-x)^i x^{n-i} \right\rbrace dx \\
&= \sum_{i=k}^n \binom{n}{i} \int_{0}^{1} (1-x)^i x^{n-i} dx \\
&= \sum_{i=k}^n \binom{n}{i} \frac{i!(n-i)!}{(n+1)!} \\
&= \sum_{i=k}^n \frac{n!}{i!(n-i)!} \frac{i!(n-i)!}{(n+1)!} \\
&= \sum_{i=k}^n \frac{1}{n+1} \\
&= \frac{n-k+1}{n+1} \\
&= 1 - \frac{k}{n+1}.
\end{aligned}$

Beta Function, Gamma Function

beta function , $\forall P,Q > 0$

$B(P,Q) = \int_0^1 x^{P-1}(1-x)^{Q-1}dx$

Gamma Function

$\Gamma(x) \equiv \int_0^{+\infty} t^{x-1} \mathrm{e} ^{-t} ,\mathrm{d}{t} \qquad (x > 0)$

$x! = \Gamma(x+1)$

$B(P,Q) = \frac{\Gamma(P)\Gamma(Q)}{\Gamma(P+Q)}$

对于整数$m,n$ 有 $\int_{0}^{1} x^m (1-x)^n dx = B(m+1,n+1) = \frac{\Gamma(m+1)\Gamma(n+1)}{\Gamma(n+m+2)} = \frac{m!n!}{(m+n+1)!},$

回到原问题

!!!!!拆线段, 让每个值都在 多个长度为1的线段里分布,再计算答案

对于每个线段[A,A+1]算dp,最后算贡献

dp[i][j][t] = 前i个随机变量, j个大于A+1, t 个在[A,A+1] 之间 的概率

第i无非3种, < A, [A,A+1]之间> A+1

< A: +dp[i-1][j][t] * (min(A,ri)-li)/(ri-li), 需要A >= li

[A,A+1]: +dp[i-1][j][t-1] * 1/(ri-li), 且[A,A+1] 在[li,ri] 之间

> A: +dp[i-1][j-1][t] * (ri-max(li,(A+1)))/(ri-li), 需要 ri >= A+1

滚动可以空间$O(N^2)$

j个大于A+1, t个在[A,A+1]中, 那么第k大的期望就是 [A,A+1]中第k-j大的期望

那么[A,A+1] 对答案的贡献, $\sum dp_{n,j = 0 \cdots n, t = 0 \cdots n} \cdot (A + 1 - \frac{k-j}{t+1})$

看起来$O(n^4)$ 但是有些状态达不到, 常数一般

看起来还有$O(N^3)$ 甚至 taylor shift 分治可以$N^2 log^2 N$ 的做法

代码

https://atcoder.jp/contests/abc226/submissions/34060577

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read

ll inv[110] = {0,1}; // inv[i] = 1/i
int l[60];
int r[60];

int main() {
  rep(i,2,100+1) inv[i] = (MOD-MOD/i) * inv[MOD%i] % MOD;
  int n = read();
  int K = read();
  rep(i,1,n+1){
    l[i] = read();
    r[i] = read();
  }
  int minl = *min_element(l+1,l+n+1);
  int maxr = *max_element(r+1,r+n+1);
  mint ans = 0;
  rep(A,minl,maxr){// 处理区间[A,A+1]
    // dp[i][j][t] = 前i个, j个大于, t个在`[A,A+1]`, 滚动掉一个维度
    auto dp = vector(n+1,vector<mint>(n+1,0));
    dp[0][0] = 1;
    rep(i,1,n+1){
      int invrl = inv[r[i]-l[i]];
      per(j,0,i+1) if(j <= K) per(t,0,i-j+1){
        // val[i] < A
        dp[j][t] = (l[i] <= A) ?                  dp[j  ][t  ]*(min(r[i],A) - l[i])*invrl : 0;
        // val[i] \in [A,A+1]
        if(l[i]<=A && A+1<=r[i] && t) dp[j][t] += dp[j  ][t-1]                     *invrl;
        // val[i] > A+1
        if(A+1<=r[i] && j )           dp[j][t] += dp[j-1][t  ]*(r[i]-max(l[i],A+1))*invrl;
      }
    }
    rep(j,0,K) rep(t,0,n+1) if (K-j <= t) ans += dp[j][t] * (A+1-(K-j)*inv[t+1]);
  }
  printf("%d\n",ans.val());
  return 0;
}

总结

F

dp 组合数, 主要是看到和很小,所以lcm估计也很少,没啥难的

G

贪心完全不会

H

概率论完全不会, 这里思路还是积分类的

就是对于连续的概率分布,转变成 概率分布以后,就方便计算分布函数的概率,而不是单点的概率表达式, 这样再反推概率表达式也行, 直接得到E(X)也行

这个拆线段也是很神奇, 没想到, 感觉大量的dp做的还是离散的,这里的有针对这种连续的处理方法

参考

官方题解

贝塔函数 百度百科

wuli.wiki gamma