Educational Codeforces Round 133

發表於 2023-01-14 更新於 2024-10-23 分類於 Codeforces ， Edu Disqus：文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘

E(树) F(第二类斯特林数,数学)

CF tracker

Edu List

https://codeforces.com/contest/1716

E. Swap and Maximum Block

给一个长度 2^n 的数组a, 值范围是[1~2^n]

q个询问,

每个询问, 给k, for i = [1..2^n-2^k], 如果该轮询问没有交换过a[i],则交换swap(a[i],a[i+2^k])

操作后, 输出最大的连续区间的和

范围

n 18

a[i] \in [-1e9,1e9]

q 2e5

512mb

我的思路

很显然就是一个满完全二叉树

而操作k 就是从下向上第k层左右交换,(第k-1层每个点交换左右儿子)

问题是如何维护最大值, 或者如何算最大值

考虑直接算,

f(l..r) = max(f(l..mid),f(mid+1..r),maxr(l..mid) + maxl(mid+1..r))

maxr(l…r) = max(suffix(l…r))

maxl(l…r) = max(prefix(l…r))

但问题是交换会让比 n-k层更低的都会影响

感觉可能的方向, 就是暴力从下向上, 枚举所有

似乎就层数的个数和层数的方案数的乘积都是2^n, 这样就是n 2^n???

题解

还真是这样

代码

https://codeforces.com/contest/1716/submission/189373554

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
const int K = 18;

struct node {
  ll sum, pref, suff, ans;
  node(const node& l, const node& r) {
    sum = l.sum + r.sum;
    pref = max(l.pref, l.sum + r.pref);
    suff = max(r.suff, r.sum + l.suff);
    ans = max(max(l.ans, r.ans), l.suff + r.pref);
  }
  node(int x) {
    sum = x;
    pref = suff = ans = max(x, 0);
  }
  node() {};
};

int a[1 << K];
vector<node> tree[2 << K];

void build(int v, int l, int r) { // [l,r)
  tree[v].resize(r - l);
  if(r-l == 1){
    tree[v][0] = node(a[l]);
  } else {
    int m = (l + r) / 2;
    build(v*2+1, l, m);
    build(v*2+2, m, r);
    rep(i,0,m-l){
      tree[v][i]       = node(tree[v*2+1][i], tree[v*2+2][i]);
      tree[v][i+(m-l)] = node(tree[v*2+2][i], tree[v*2+1][i]);
    }
  }
}

int main() {
  int n=read();
  int m = (1 << n);
  rep(i,0,m) a[i]=read();
  build(0, 0, m);
  int q=read();
  int cur = 0;
  rep(i,0,q){
    int x=read();
    cur ^= (1 << x);
    printf("%lld\n", tree[0][cur].ans);
  }
  return 0;
}

F. Bags with Balls

n个包1到n(包两两不同), 每个包有m球, 编号1..m

需要每个包取一个, F=(球上数字为奇数的个数)

计算对于所有方案w, sum_w ((F_w)^k)

mod 998244353

范围

t 5000 测试点

n,m [1,MOD-1]

k 2000

我的思路

n,m 这么大, 所以 F范围也是[1,MOD-1]

枚举F算贡献都不太可能

但朴素一点, 直接想到的就是枚举F算贡献

c[f]= 有f个球是奇数的方案数 = binom(n,f) * ((m+1)/2)^f * (m-(m+1)/2)^{n-f}

ans = sum_{f=0}^n c[f] * f^k

k=0的时候还好,看起来就是二项式展开 $((m-\lfloor \frac{m+1}{2} \rfloor) + \lfloor \frac{m+1}{2} \rfloor)^n = m^n$

k=1的时候也还行,可以转化成 $n x \binom{n-1}{f-1} x^{f-1} (m-x)^{n-f}, x=\lfloor \frac{m+1}{2} \rfloor$ 即 $n \lfloor \frac{m+1}{2} \rfloor m^{n-1}$

k=2的时候, 感觉是不是要上求导什么的了

$\binom{n}{f} x^f (m-x)^{n-f} f^2, x=\lfloor \frac{m+1}{2} \rfloor$

题解

的确可以求导推!!

数学推

$\sum_{i=0}^{n}i^k \binom{n}{i} \left ( \left \lceil \frac{m}{2} \right \rceil \right )^i \left ( \left \lfloor \frac{m}{2} \right \rfloor \right )^{n-i}$

$=\sum_{i=0}^{n}\sum_{j=0}^{k}\begin{Bmatrix} k\\ j \end{Bmatrix}i^{\underline j}\binom{n}{i} \left ( \left \lceil \frac{m}{2} \right \rceil \right )^i \left ( \left \lfloor \frac{m}{2} \right \rfloor \right )^{n-i}$

$=\sum_{i=0}^{n}\sum_{j=0}^{k}\begin{Bmatrix} k\\ j \end{Bmatrix}\binom{n-j}{i-j}n^{\underline j} \left ( \left \lceil \frac{m}{2} \right \rceil \right )^i \left ( \left \lfloor \frac{m}{2} \right \rfloor \right )^{n-i}$

$=\sum_{j=0}^{k}\begin{Bmatrix} k\\ j \end{Bmatrix} n^{\underline j} (\left \lceil \frac{m}{2} \right \rceil)^j (\sum_{i=0}^{n}\binom{n-j}{i-j} \left ( \left \lceil \frac{m}{2} \right \rceil \right )^{i-j} \left ( \left \lfloor \frac{m}{2} \right \rfloor \right )^{n-i})$

$=\sum_{j=0}^{k}\begin{Bmatrix} k\\ j \end{Bmatrix} n^{\underline j} (\left \lceil \frac{m}{2} \right \rceil)^j m^{n-j}$

代码

https://codeforces.com/contest/1716/submission/189445390

#include <bits/stdc++.h>
typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<n;i++)
ll read(){ll r;scanf("%lld",&r);return r;} // read

const int N=2000;
int stir2[N+10][N+10]={{1}}; // stirling 2

ll mypow(ll a,ll p){
  ll r=1;
  for(;p;p/=2){
    if(p&1) (r*=a)%=MOD;
    (a*=a)%=MOD;
  }
  return r;
}

void w(){
  ll n=read();
  ll m=read();
  ll k=read();
  ll ans=0;
  ll r=mypow(m,n);
  ll t=((m+1)/2)*mypow(m,MOD-2)%MOD; // ((m+1)//2) * m
  rep(i,1,std::min(n,k)+1){ // n-i >= 0
    (r*=(n-i+1)*t%MOD)%=MOD; // n^{\underline i} ((m+1)//2)^i m^{n-i}
    (ans+=stir2[k][i]*r%MOD)%=MOD;
  }
  printf("%lld\n",ans);
}

int main(){
  rep(i,1,N+1) rep(j,1,i+1) stir2[i][j]=(stir2[i-1][j-1]+stir2[i-1][j]*j%MOD)%MOD;
  int q=read();
  while(q--)w();
  return 0;
}

总结

评分都是2500

E 但实际上好好思考一下计算,和思考一下数量级,就很显然暴力就完了, 没啥难的

数学太菜,

不过这里学会了以后如果在求和里看到 $binom \cdot n^m$的时候, 就可以去想用斯特林数拆$n^m$了

以及第二类斯特林数也不熟悉

参考

官方

stirling