CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)

發表於 2024-03-30 更新於 2024-10-23 分類於 Codeforces ， Div1+2 Disqus：文章字數： 4.8k 所需閱讀時間 ≈ 16 分鐘

E(实现)F(数学)G(分治卷积)H()

https://codeforces.com/contest/1942

E. Farm Game(2s,256mb)

在区间[1,l]整数点上放 ABABAB…或者BABABA… 一共n组AB或BA, 坐标不一定相邻

玩家X可以选择任意多个X(和玩家ID相同),和一个方向（左或右），把所有选中的A沿着这个方向移动
A先B后
移动过程中字母不能重叠不能出[1,l]范围，如果无法移动则输掉

问给定$l,n$ 有多少个初始状态玩家A获胜

我的思路

很像nim的游戏之类的

那么考虑每个AB之间的空位的和，如果空位和为奇数，那么总可以移动那个位置让AB之间的空位和减1,而对于空位和是偶数，不一定能增大，也不一定能减少，但只要是能操作则结果也是奇数，

如果一轮操作后空位和不变（否则变小），那么对应位置整体向同一个方向移动了两个字母

所以获胜状态 = 所有AB间隔空隙和=奇数

那么 l个位置去掉 2n个占用位置，实际是切割成2n+1个 >=0 的段

也就是 l-2n长度线段切割成 2n+1个 >=0整数段且偶数index的段的长度和=奇数

考虑所有段+1

(l-2n)+(2n+1) 段切割成 2n+1个 >=1 整数段,且偶数index的段的长度和 = 奇数+n

考虑做顺序的置换，把所有偶数index段直接移动到最前，则方案还是一一对应

(l-2n)+(2n+1) 段切割成 2n+1个 >=1 整数段,且前n段的长度和 = 奇数+n

for 前n段的长度和 = i:
 if i % 2 == (n+1) % 2:
  ans += (i 切割 n)段 * (l+1-i 切割成 n+1) 段, 每个切割段 >=1

长度 x 切割成y个>=1整数段，相当于 x-1个切割点中选择y-1个切割点
cut(x,y) = binom(x-1,y-1)

最后答案 AB和BA反向需要乘上2

然而 pretest1都没过 https://codeforces.com/contest/1942/submission/256178349

然后我发现读错题了，是一次可以移动任意多个同方向，而不是一次一个

那么思路也完全一样，就是去挤压另一个

所以如果存在 > 0 个奇数空位，则A 总能把这些奇数空位全变偶数（0个奇数空位）

如果存在 0 个奇数空位，则全为偶数空位，则操作不确定，且操作后至少一个奇数空位

所以方案 = 所有方案 - 全偶数空位方案

一样的

l-2n个位置切割2n+1个>=0整段，其中偶数index的长度全偶数

(l-2n)+(2n+1)=l+1个位置切割2n+1个>=1整段，其中偶数index的长度全奇数

l+1个位置切割2n+1个>=1整段，其中前n段的长度全奇数

for 前n段长度和为i, i % 2 = n * 1 % 2:
 把 前n段每个长度+1, 则 前半
  i+n长度 切割成 n 个 >= 2的偶数段 (那么每2个看成一个)
  (i+n)/2 长度 切割成 n 个 >= 1的整数段
  也就是 cut((i+n)/2,n)
 cnt += cut((i+n)/2,n)*cut(l+1-i,n+1)

ans = (binom(l,2n)-cnt)*2

https://codeforces.com/contest/1942/submission/256179100

题解

读错题是一生之敌

F. Farmer John’s Favorite Function(5s 256mb)

整数组 a[n]

$f(1)=\sqrt{a_1}$

$i> 1,f(i)=\sqrt{f(i-1)+a_i}$

q个操作

每次改变指定单个$a[k_j]=x_j$
并输出 $f(n)$ 向下取整

n,q 2e5

$a_i \in [0,10^{18}]$, 改动的也满足范围

我的思路

第一个想法是根号会导致值快速下降，也就是 ai 对于 an的贡献，虽然受到了前置和后置的“影响”，但是如果太远了应该就会失去效果

对于$a\ge 0,b\ge 0$，有$\sqrt{a+b} \le \sqrt{a}+\sqrt{b}$, 因为两边平方右侧多一个$2\sqrt{ab}$

$\sqrt{\sqrt{\sqrt{a}+b}+c} < \sqrt{a^{\frac{1}{4}}+b^{\frac{1}{2}}+c} < a^{\frac{1}{8}}+\sqrt{b^{\frac{1}{2}}+c}$

对于更长的表达式来说，如果固定后面的值，那么a在变化时对于上界（可能不可达）的影响是 $a^{\frac{1}{2^{t}}}$, 其中$t$是长度

又有希望 $a\in[0,f(x)),b\in[0,x], a_n=\sqrt{a_{n-1}+b} \le \sqrt{f(x)+x} = f(x)$ 成立

只需要

$f(x)^2-f(x)-x=0$

$f(x)=\frac{1\pm\sqrt{1+4x}}{2}$, 这里要取正号

所以回到原题，任何前缀$<\frac{1+\sqrt{1+4\cdot 10^{18}}}{2}$ 大约是 $[10^9,10^9+1]$

至此2个结论

前缀的结果 $[0,10^9+1)$
$2^{29}=5,3687,0912 < 10^{9} < 10,7374,1824=2^{30}$ 也就说明了倒数个数 > 40个 (忽略边界细节)的值，对最终上界影响 < 2

问题也是有的

这样只是证明了对上界的影响，没有证明对具体值的影响，虽然从体感上猜想应该也是类似的
虽然很小，但是这里不是求近似值（可以控制位数），如果真的正好让值跨过一个整数，那么怎么记录呢？

其实还有一个显然的性质，如果固定后面的值，前面的值变化，对结果是单调的影响的

所以如果 [0,..最后40个值], [1e9,..最后40个值] 得到的整数部分一样（不只需要结果差距是1）那么答案显然了

那么问题是如果不一样要如何判断? 因为实际上的确可以实现这样的微调

1 2	4 2 2 2 2 2.....2 的结果肯定是2，因为一直是 \sqrt{2+2} 而可以通过微调很前面index 的值，-1导致最后结果变为1

题解

hint1 考虑特殊情况，修改任何ai都会让答案变小，就是上面我考虑的特殊情况，所以只考虑最后几个数是不行的

hint2 如果 n >= 6 那么 a1 对于 f(n)的影响最多是1？啊，比我的结论的长度小了这么多？？？而且不是影响上界而是直接影响目标值

hint3 !!!!!!!!!!!!!!!!!!!! 可以每一次都做floor运算不影响结果, 哦好有道理！！！！

hint4 把数组切割成 size b >= 6 的块

4 2 2 2 … 2 所有结果都是整数，所以减少任何数，对结果都会减少
推的方向对的但是幂次自己傻了

$\sqrt{a+b}^2 = (a+b)\le a+b+2\sqrt{ab} = (\sqrt{a}+\sqrt{b})^2$

$\sqrt{a+b} \le \sqrt{a}+\sqrt{b}$

$\sqrt{a+b}-\sqrt{b}\le \sqrt{a}$

$\sqrt{c+\sqrt{b+a}}-\sqrt{c+\sqrt{b}}\le \sqrt{\sqrt{b+a}-\sqrt{b}}\sqrt{\sqrt{a}}=a^{\frac{1}{2^2}}$

$2^6 = 64$

$10^{18} < 2^{64}$

hint3 感觉以前遇到过一次，很好证明，但很难从零想到

如果当前的结果是 [a,a+1),其中$a$是整数，那么下一个结果是 $[\sqrt{a+b},\sqrt{a+b+1})$

$\sqrt{a+b+1}-\sqrt{a+b} = \frac{1}{\sqrt{a+b+1}+\sqrt{a+b}} < 1$

注意只有可能整数的根号才是整数

说明 $\sqrt{a+b},\sqrt{a+b+1}$的整数部分是一样的

因此可以改成 $f(i)=\lfloor \sqrt{f(i-1)+a_i}\rfloor$

再把数组切割成6个一组，不是6的倍数补前导0

对于一组 $a[l\cdots r]$

令 $v(r) = f(r)$ 当$f(l-1)=0$时的值

那么随着$f(l-1)$的变化, 而$a[l\cdots r]$不变时, $f(r)\in[v(r),v(r)+1]$, (修改后的)

令 $c(r) =$ 最小的$f(l-1)$ 使得 $f(r) = v(r)+1$

这可以逆向计算 block得到

注意到每个block固定后变成了

block[v,c]

也就是 v表示它的输出值是 v或v+1

c表示最小的上一个block输出值让它是v+1, 注意到c的性质即是完成了 v=> v+1 同时它刚好产生的整数

用线段树维护

block[v0,c0] + block[v1,c1]

那么得到的一定是

block[v1,c0]:  
		[0..c0-1] => v0     == c1-1
		[c0..max] => v0+1   == c1

block[v1,max+1]:  // 输出全是v1
		[0..c0-1] => v0
		[c0..max] => v0+1   < c1
		
block[v1+1,max+1]:  // 输出全是v1+1
		[0..c0-1] => v0     >= c1
		[c0..max] => v0+1

换个视角看

...... v0 ,  v0+1 ......
               c1...      v1,max+1
             c1              v1,c0
    ...c1                    v1+1,max+1

另一方面，也可以不用线段树，根号分治，用$\sqrt{n}$大小的块，每次更新一个块，再对所有块做计算

代码

https://codeforces.com/contest/1942/submission/257996167

#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;}

const int B = 470; // sqrt(2e5) 块大小
const int MAX = 2e5 + B + 5;
const ll V=1'000'000'000'000'000'000;
int numBlocks;
ll A[MAX];
ll v[MAX]; // 块输出值为 v 或 v+1
ll c[MAX]; // 最小的c 使得值变为 v+1

void buildBlock(int blk){
  // [l,r)
  int l = blk * B;
  int r = l + B;
  // 正向计算 前面输出0的值v
  ll cur = 0;
  rep(i,l,r) cur = floor(sqrtl((long double)cur + A[i]));
  v[blk] = cur;
  // 逆向计算 == v+1的值
  ll x = cur + 1;
  per(i,l,r) {
    if (x > 2e9){
      c[blk] = V+1; // 所有都不能
      return;
    }
    x = x * x - A[i]; // v能达到，所以v+1反推一定是正的
  }
  c[blk] = x;
}
ll qry(){
  ll cur = 0;
  rep(b,0,numBlocks) cur = (cur >= c[b]) ? v[b] + 1 : v[b];
  return cur;
}

int main(){
  int n=read();
  int q=read();
  int offset = (B - n % B) % B;
  n += offset;
  numBlocks = n / B;
  rep(i,offset,n) A[i]=read();
  rep(b,0,numBlocks) buildBlock(b);
  while (q--){
    ll k=read()-1+offset;
    ll x=read();
    A[k] = x;
    buildBlock(k / B);
    printf("%lld\n",qry());
  }
  return 0;
}

G Bessie and Cards

a张 draw 0

b张 draw 1

c张 draw 2

5个特殊卡

游戏开始时，所有牌都在随机洗好的牌组中。

Bessie 开始抽取卡堆最顶5张卡

然后可以使用手上的draw x抽取顶上的x张卡,

特殊卡不能用，剩余卡< x则抽取全部

目标是抽取所有的卡则获胜

对于 (a+b+c+5)! 种的随机洗牌结果, 求他获胜的概率 mod 998244353

$a,b,c \in [0,20’0000]$

256mb

我的思路

考虑策略，如果当前手上有 draw x 则使用，所以实际上相当于

a[i]=draw的值

prefix = 5

然后一直循环 prefix = 5 + presum[prefix]

然后关心的是 5张特殊卡(对应的)全部拿到

而操作上采取每次把所有手中的同时使用？

所以 5 -> 5+前5张的draw的和

dp[i] = , 按这样操作能达到的i的位置，也就是中间跨过的不算

dp[i]=true => dp[5+presum[i]]=true

什么时候停止，也就是 i==5+presum[i]

5+presum[i] > i 就可以继续多拿一张！（拆解draw x成1张1张的动作）

因为按照上面的方法一轮操作中 5+presum[oldi] = newi > oldi,1张1张拿的过程中的for i = [oldi..newi), 而过程中的 i < newi = 5+presum[oldi] <= 5+presum[i]的

所以问题变成首个 i==5+presum[i]的位置 >=第5张特殊排的位置

再变形一下

首个 5+presum[i]-i==0

$5+\sum_i (a[i]-1) == 0$，这里i最小取5,

也就是值变成 -1,0,1, 然后前缀和保持 $> 0$ 当$=0$是要包含所有特殊牌

因为方案中所有牌两两不同, 先把特殊牌和draw0 合并再提出

计算 f[sz][z] = 首个 == 0的长度是sz, 其中有z个(draw 0)(-1)的无差别0,1,2 在总长度里的方案数

$ans += \sum f_{sz,z} \binom{z}{5} 5! a!b!c!$

g[sz][z][s] = 前缀长度sz 全部 > 0且当前和为s， (draw 0)有z个的前置方案数

draw 0个数+draw 1个数+draw 2个数 = sz
draw 0个数 = z <= a+5
(-1)*(draw 0个数)+0*(draw 1个数)+1*(draw 2个数)=s
draw 2个数 = s+z <= c
draw 1个数 = sz -z -(s+z)<= b

问题是这个状态是 $O(n^3)$的，转移倒是可以转移

不过 -1,0,1 用x-y的图像看就是首个交点0的位置是sz，不过上面 f[sz][z]的状态数都是$O(n^2)$

另一个观察是，这里的b完全不影响和0的交界，所以可以先剔除!!

只考虑-1,1 最后再放入0

这样的话，长度和1/-1个数有了更紧密的关系

(a+5)个 -1

c个1

那么显然首次=0时用的 -1的个数为z的话，那么用的1的个数是 z-5

f[sz][z] = f[2z-5][z]

f变成 z个-1,(z-5)个1, prefix[0]=5, 然后首次=0 是在2z-5的位置

令 h[2z-5] = binom(2z-5,z) 有z个-1,z-5个1和为-5的所有方案

令 g[2z] = binom(2z,z) 有z个1,z个-1和为0 所有方案

令 f[2z-5]= 长度2z-5是首次前缀=0（和为-5）的方案

容斥一下, f[2z-5] = h[2z-5] - sum f[j < 2z-5] * g[2z-5 - j] ，也就是去掉前面就=0的

这看起来就是个分治卷积?

如果得到了f

ans = sum f[2z-5] binom(z,5)5!a!b!c! * b的插入其中的方案

b个切割成 a+c+5+1 段，每段的个数 >=0

b+(a+c+5+1)个切割成 a+c+5+1 段，每段的个数 >=1

b+(a+c+5+1)-1个切割点选择其中(a+c+5+1)-1个切割点切割

ans = sum f[2z-5] binom(z,5)5!a!b!c! * binom(b+(a+c+5),a+c+5)

数学上优化一下表达式计算

new f[z] = 有z个1,z+5个-1 首次前缀=-5的方案

new h[z] = 有z个1,z+5个-1 的方案 = $\binom{2z+5}{z}$

new g[z] = 有z个1,z个-1 的方案 = $\binom{2z}{z}$

类似的

f[z] = h[z] - sum f[j < z] * g[z-j]

f[z] = h[z] - [x^z] f * g, 令 g[0]=0

代码

https://codeforces.com/contest/1942/submission/258106122

#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;}
namespace CMM{
  const int _mod = 998244353;
  class modint{
    private:
      long long _v;
      static constexpr unsigned int umod() { return _mod; }
    public:
      modint() :_v(0) {  }
      modint(long long _a) { // dont use modint{value}, use modint(value)
        _v = (_a < 0)? umod() - ((-_a) % umod()) : (_a % umod());
        assert(_v >=0 and _v < umod());
      }

      int val()const { return _v; }
      modint operator+()const { return *this; }
      modint operator-()const { return { umod() - _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) %= umod();
        return *this;
      }
      modint& operator-=(const modint& rhs) {
        (_v += umod() - rhs._v) %= umod();
        return *this;
      }
      modint& operator*=(const modint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
      }
      modint& operator/=(const modint& rhs) { // 费马小定理
        _v = _v * rhs.inv().val() % umod();
        return *this;
      }
      modint pow(long long pwr) const {
        unsigned long long res(1);
        unsigned long long _b(_v);
        while (pwr) {
          if (pwr & 1) (res *= _b) %= umod();
          (_b *= _b) %= umod();
          pwr /= 2;
        }
        return res;
      }
      modint inv() const {
        assert(_v != 0);
        return pow(umod() - 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];
        }
        T binom(ll n,ll m){ return (n<m or m<0)?0:fac[n]*ifac[m]*ifac[n-m]; }
        Binomial(int n){ init(n); }
    };

  namespace NTT{
    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 ----------
using mint = CMM::modint;

int n;
const int N=(1<<18); // > 2e5
mint f[N+10];
// f[x]=h[x] - sum f[j<x]*g[x-j]
CMM::Binomial<mint> B((1<<20)+1); //  > 6e5+5

// [l,r)
void calc(int l,int r){
  if(l+1==r){
    f[l] = B.binom(2*l+5,l)-f[l];
    return ;
  }
  int mid=(l+r)/2;
  calc(l,mid);
  // [l,mid) => [mid,r)
  int sz=r-l;
  assert((sz&(sz-1)) == 0);
  vector<mint> flmid;
  vector<mint> g;
  rep(i,l,mid) flmid.push_back(f[i]);
  rep(i,0,sz) g.push_back(B.binom(2*i,i));
  // g[0]=0;
  auto res = CMM::NTT::convolution(flmid,g);
  rep(i,sz/2,sz) f[l+i]+=res[i];
  calc(mid,r);
}

void w(){
  int a=read();
  int b=read();
  int c=read();
  mint ans=0;
  rep(i,0,min(c,a)+1) { // [i+5个-1,i个1], [a-i个-1,c-i个1
    ans += f[i]*B.binom(i+5,5)*B.binom(a-i+c-i,c-i);
  }
  // 如果 总和 > 0, 那么还有一种可能是始终没有 = 0
  if(c-a>0){
    mint w = B.binom(a+c+5,c);
    rep(i,0,min(a,c)+1) {
      w -= f[i]*B.binom(a-i+c-i,c-i);
    }
    ans += w*B.binom(a+5,5);
  }
  // printf("%d * %d %d\n",ans.val(),B.fac[5].val(),B.binom(b+a+c+5,a+c+5).val());
  // printf("fm = %d\n",B.fac[a+b+c+5].val());
  printf("%d\n",((ans*B.fac[5]*B.fac[a]*B.fac[b]*B.fac[c]*B.binom(b+(a+c+5),a+c+5))/(B.fac[a+b+c+5])).val());
}

int main(){
  calc(0,N); // 524288 > 2*2e5
  // rep(i,0,5) printf("%lld %d\n",i,f[i].val());
  int t = read();
  while(t--) w();
  return 0;
}

总结

VP了这场（4715 大概2101的表现（如果实际打会掉分, 但是可以领TON）），
C2错了三次很僵硬，
E自己没做出来更僵硬（赛后发现读错题了，艹，
这应该是自己能做出来的，如果做出来多个1400分也只有（2240的表现分），而且不读错题，应该比D还简单）

A(7min)

B(12min)

C1(7min)

C2(26min), 罚时x3

D(54min)

E 很早就得到结论，然后瞎推生成函数推了半天，外加读错题，本身难度不高

hint3 总觉得以前遇到过一次，也很显然，但自己想就是想不到

虽然超时了，但是自己做出来了，感觉比F更不需要智力

H()