Educational Codeforces Round 123

發表於 更新於 分類於 ， Disqus： 文章字數： 2.4k 所需閱讀時間 ≈ 8 分鐘
F(斯特林数,第二类斯特林数,容斥原理,排列组合)

CF tracker

Edu List

https://codeforces.com/contest/1644

F. Basis

F(a数组,k数字) = 把a每个数组重复k次, 然后取 和a等长的前缀 [a_0_1,a_0_2...,a_0_k, a_1_1...a_1,k, a_2_1,...,a_2_k,...]

`x!=y, G(a数组,x数字,y数字) = 把a中所有x变成y, 所有y变成x

如果满足以下条件,则称a数组是b数组的父数组:

  • 存在 k使得F(a,k) = b
  • 或者 存在x!=y, G(a,x,y) = b

如果 有父数组链关系, 则称作祖先

问题, 给定n,k

构造系列 数组s={ s1,s2,..,sm}

每个si包含n个元素, si中的的值\in [1,k]

对于 任意的长n 值在 [1,k]的数组a, 至少在你给的s中存在一个si是a的祖先

问s的最小长度 mod 998244353

范围

n,k 2e5

6s

512mb

我的思路

si 通过 F,G的操作能变成任意数组

一个纯数字的数组, 那么通过F操作一定是自己的祖先,

两个不同的纯数字数组, 通过一次G操作 互为祖先

纯数字数组, 通过两次操作G一定是自己的祖先,

每个数组通过巨大k 操作, 都能变成纯数字数组

G的性质, 让数组的内容和具体值无关, 变成的一段一段的同样的值,(可以看成交换)

所以 比如 xxxyyyxxzz 是否能达到, 就是看 111221133 是否能达到

F的性质, 则是说不要考虑任何 x * w y * w z * w 的形状, 也就是能找到一个连续段的分割, 因为它总对应一个更小的

如果 k >= n, 那么就好了 [1,2,3,…,n], 啥都能变

–

考虑 k < n

两个没有 前缀 循环节的如何判断是否可以相互转化呢

1
2
3
n=5,k=4
1,2,3,3,4
1,2,2,2,3

一个猜想, 没有用完k的一定可以由 用完k的转化来, 因为至少有同色的个数 >= 2, 而且它不能转化回去(所以它的父一旦能被表示它则一定被表示, 所以它自身不需要存在)

两个序列之间如果可以转化 则 一定没有F操作, 否则形状会变有周期的,

而两个序列如果之间有G操作, 则不满足 从小到达命名1,2,3,4 的性质

综上, 需要统计

长度n, 用完k个,没有循环段, 且满足顺序赋值的个数(每个位置的值 <= 之前用的最大值+1)

有循环段很好算,枚举循环长度就行, 所以就找出满足 顺序赋值 的个数 再来减法

f[i][t] = 前i个最大命名为t的方案数

f[i][t] = f[i-1][t] * t + f[i-1][t-1] * 1, 分别是用前面一样的和用更大的

那么ans = f[n][k] - 有循环段的

直接搞是 O(n^2)

看成生成方程

$f_i(x) = f_{i-1}’(x) x + x f_{i-1}(x)$

$f_i(x)e^x = x (f_{i-1}e^x)’$

$令a_i = f_i(x)e^x$

再看 系数 $a[i][t] = a[i-1][t] * t$

所以 $a[n][t] = a[0][t] * t^n$

然后乘上$f[n] = a[n] * e^{-x}$ 就能得到 f[n][k]完了?

$a[0] = f[0] * e^x$

似乎有点问题

题解

显然F(G(a,x,y),m)=G(F(a,m),x,y),所以可以考虑先F再G

G(G(a,x,y),x,y)=a, 所以G的操作都可以恢复, 考虑所有F结束后用G调整顺序

实际是对{1,…,n} 做子集分割

那就是 直接 $\sum \limits_{i=1}^{\min(n, k)} S(n, i)$, 第二类 斯特林数S(n,m) 把n个有差别数 放进m个无差别盒子, 且每个盒子至少一个的方案数

对单个(一行固定n)第二类斯特林数的计算

$S(n, k)=\frac{1}{k!} \sum \limits_{i = 0}^{k} (-1)^i binom{k}{i} (k-i)^n$

$= \sum \limits_{i=0}^{k} \frac{(-1)^i \cdot k! \cdot (k-i)^n}{k! \cdot i! \cdot (k-i)!}$

是 $\frac{(-1)^i}{i!}x^i$ 与 $\frac{i^n}{i!}$ 的卷积

但实际上 当固定n以后, 算多个k 可以前缀一下暴力算, 不需要用ntt

令$A_i = \sum \limits_{j=1}^{\min(i, k)} S(i, j)$

一样的,就是有一段一段等长的同等数字的

然后就是容斥

$\sum \limits_{i=1}^{n} \mu(i) B_i = \sum \limits_{i=1}^{n} \mu(i) A_{\lceil \frac{n}{i} \rceil}$

这里有问题

比如n=3,n=2

1
2
3
A(3) = 4(111,122,121,112)
A(2) = 2(11,12) => (111,112)
A(1) = 1(1) => (111)

直接上面的容斥会 得到 4-2-1 = 1, 其中 111被重复减掉了

而出问题的就是这种 全部都一样的, (如果不是全部一样, 至少有个 < k的长度的因子)

而全部一样的只有1种, 所以需要A(i)-S(i,1)

代码

https://codeforces.com/contest/1644/submission/189829751

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <bits/stdc++.h>
namespace CMM{
  const int _mod = 998244353;
  class modint{
    private:
      long long _v;
    public:
      modint() :_v(0) {  }
      modint(long long _a) { // dont use modint{value}, use modint(value)
        _v = (_a < 0)? _mod - ((-_a) % _mod) : (_a % _mod);
      }

      int val()const { return _v; }
      modint operator+()const { return *this; }
      modint operator-()const { return { _mod - _v }; }
      modint operator+(const modint& rhs) const { return modint(*this) += rhs; }
      modint operator-(const modint& rhs) const { return modint(*this) -= rhs; }
      modint operator*(const modint& rhs) const { return modint(*this) *= rhs; }
      modint operator/(const modint& rhs) const { return modint(*this) /= rhs; }

      bool operator==(const modint& rhs)const { return _v == rhs._v; }
      bool operator!=(const modint& rhs)const { return _v != rhs._v; }
      bool operator> (const modint& rhs)const { return _v >  rhs._v; }
      bool operator>=(const modint& rhs)const { return _v >= rhs._v; }
      bool operator<=(const modint& rhs)const { return _v <= rhs._v; }
      bool operator< (const modint& rhs)const { return _v <  rhs._v; }

      modint& operator+=(const modint& rhs) {
        (_v += rhs._v) %= _mod;
        return *this;
      }
      modint& operator-=(const modint& rhs) {
        (_v += _mod - rhs._v) %= _mod;
        return *this;
      }
      modint& operator*=(const modint& rhs) {
        _v = _v * rhs.val() % _mod;
        return *this;
      }
      modint& operator/=(const modint& rhs) { // 费马小定理
        _v = _v * rhs.inv().val() % _mod ;
        return *this;
      }
      modint pow(long long pwr) const {
        long long res(1);
        long long _b(_v);
        while (pwr) {
          if (pwr & 1) (res *= _b) %= _mod;
          (_b *= _b) %= _mod;
          pwr /= 2;
        }
        return res;
      }
      modint inv() const {
        assert(_v != 0);
        return pow(_mod - 2);
      }
  };
};

template<class T> // mod type T
class Binomial{
  public:
    std::vector<T> fac;
    std::vector<T> ifac;
    std::vector<T> inv;
    Binomial(){};
    void init(int n) { // [0,n]
      fac.resize(n+1,1);
      ifac.resize(n+1);
      inv.resize(n+1);
      for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i;
      ifac[n]=fac[n].inv();
      for(int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1);
      for(int i=1;i<=n;i++) inv[i]=fac[i-1]*ifac[i];
    }
    Binomial(int n){ init(n); }
};

namespace NTT998{
  const int MOD = 998244353; // 7*17*2^23 + 1
  const int MAXPWR = 22; // 随着MOD改变, 2的幂次, 对应复平面单位向量的N = 2 && MAXPWR;
  const int g = 3;// 原根 随着MOD改变
  const int invg = 332748118;// 原根模逆元 随着MOD 和 g 改变

  // bit 翻转
  int rev(int x, int len) {
    int ans = 0;
    while(len -- ){
      ans <<= 1;
      ans |= x & 1;
      x >>= 1;
    }
    return ans;
  }

  inline int getlog2(int n){ return 31 - __builtin_clz(n);}

  template<class T>
  T mypow(T a, long long k) { //快速幂，a**k
    T res = 1;
    while (k) {
      if (k & 1) (res *= a); // modint %= MOD;
      (a *= a); // modint %= MOD;
      k >>= 1;
    }
    return res;
  }

  template<class mint>
  void NTT(std::vector<mint> &A, int flag = 1 /* 1: NTT, -1: INTT*/ ) {
    int n = A.size();
    if(n == 1) return ;
    // assert((n & (n-1)) == 0); // 2 的幂次
    int lgn = getlog2(n);
    // assert(lgn <= MAXPWR);
    for(int i=0;i<n;i++) { // 同FFT
      int j = rev(i, lgn);
      if (j > i) std::swap(A[i], A[j]);
    }
    for(int pwr=0;pwr<lgn;pwr++){
      int m = 1 << pwr;
      // assert((MOD - 1) % (m<<1) == 0);
      mint gn = mypow<mint>(flag == 1 ? g : invg, (MOD - 1) / (m << 1)); // 单位原根g_n
      for (int k = 0; k < n; k += (m<<1)) {
        mint gi = 1;
        for(int j=0;j<m;j++){
          mint U = A[k + j];
          mint T = A[k + j + m] * gi;
          A[k + j] = (U + T);
          A[k + j + m] = (U - T);
          gi *= gn;
        }
      }
    }
    if(flag == -1){ // 内置 / N
      const mint INVSIZE = mint(n).inv(); //  mypow(n, MOD-2);
      for(int i=0;i<n;i++) (A[i] *= INVSIZE) ; // modint %= MOD;
    }
  }

  template<class T>
  void INTT(std::vector<T> &A){ NTT<T>(A,-1);}

  // 卷积
  template<class T>
  std::vector<T> convolution(std::vector<T> v0, std::vector<T> v1){
    int sz = v0.size() + v1.size();
    if(sz == 0)return {};
    sz = 1 << (getlog2(sz) + !!(sz & (sz-1))); // 非2的幂次
    v0.resize(sz,0);
    v1.resize(sz,0);
    NTT<T>(v0);
    NTT<T>(v1);
    std::vector<T> v2(sz,0);
    for(int i=0;i<sz;i++) v2[i] = v0[i] * v1[i]; // modint % MOD;
    INTT<T>(v2);
    return v2;
  }

  // 平方 少一次 NTT
  template<class T>
  std::vector<T> poly_sq(std::vector<T> v0) {
    int sz = v0.size() * 2;
    if(sz == 0)return {};
    sz = 1 << (getlog2(sz) + !!(sz & (sz-1))); // 非2的幂次
    v0.resize(sz,0);
    NTT<T>(v0);
    std::vector<T> v2(sz,0);
    for(int i=0;i<sz;i++) v2[i] = v0[i] * v0[i]; // modint % MOD;
    INTT<T>(v2);
    return v2;
  }
}
// ---------- template end ----------

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
using mint = CMM::modint;
Binomial<mint> b;
std::vector<mint> p; // (-1)^i/i! x^i

int k;
mint A(int n){ // 分组个数不超过k的方案数, sum_{j=1~min(n,k) S(i,j)}
  std::vector<mint> pp; // 不要用完整长度, 太慢了
  rep(i,0,std::min(n,k)+1) pp.push_back(p[i]);
  std::vector<mint> q={0}; // (i)^n/i! x^i
  rep(i,1,std::min(n,k)+1) q.push_back(NTT998::mypow<mint>(i,n)*b.ifac[i]);
  std::vector<mint> s=NTT998::convolution(pp,q);
  mint r=0;
  rep(i,1,std::min((int)n,k)+1) r+=s[i];
  return r;
}

int main(){
  int n=read();
  k=read();
  if (n == 1 || k == 1) return 0 * printf("1\n");
  b.init(n);
  p.push_back(1);
  rep(i,1,std::min(n,k)+1) p.push_back(p.back()*b.inv[i]*(-1)); // (-1)^i/i!

  mint ans=0;
  std::vector<int> mu(n+1,1); // (-1)^质数个数次方
  std::vector<bool> prime(n+1,1);
  rep(i,2,n+1) if(prime[i]){
    for(ll j=i*i;j<=n;j+=i) prime[j] = false;
    rep(t,1,n+1) {
      if(i*t > n) break;
      if(t%i==0) mu[i*t] = 0;
      else mu[i*t]*=-1;
    }
  }

  rep(len,1,n+1) if(mu[len]) ans+=(A(n/len + !!(n%len)) - 1)*mu[len]; //
  printf("%d\n", ans.val());
  return 0;
}

总结

F

一个是想的问题 233 是没有变法变成222的, 只能322, 这点都想错了, 后面当然就错了, 不过大体的思路路线是对的

然后是最后这个- S(i,1), 就感觉也卡了

然后是n==1 || k==1的特殊情况

然后这里”卷积”的部分也可以通过交换积分顺序 暴力搞掉

A也可以加cache

参考

官方