NIM's GAME

發表於 2020-01-10 更新於 2024-10-23 分類於 algorithm Disqus：文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘

入门题目(Bash Game)

有一堆物品，两人轮流取,每次只能$[1,a]$个，最后取空的赢/输，求对策

假设你的对手取$x$个，有$1\le x \le a$,也就有$1 \le a+1-x \le a$,保证不论对手怎么取$x$，只要你取对应的$a+1-x$个就能保证剩余的个数对$a+1$ 取模不变

控制到了不变量(对$a+1$取模不变)也就找到了解题的关键

NIM(Nim Game)

NIM 1

现在是两堆石头（可能相同个数，可能不同），每轮任选一堆，从该堆取任意正数个，最后取空的人赢/输

如果两堆相等，则对方任意取多少，你取相同的，总能维持一个不变两堆的差值为0

NIM 2

变为n堆石头（每堆数量独立），取法和上题一致，最后取空的人赢/输

假设有偶数堆，且成对的相等，那么用上题的结论，然而，这里我们发现，上题无论初始状态如何，我们都能通过0步或者1步达到我们的平衡的状态/不变的状态，而这里如果假设是偶数堆和成对的相等，这样的状态并不是任意可达的。

对于数据小，又想不到“数学”方法去找平衡态，可以用递归搜索去做，不过不是本文要讲的内容。

然后是枚举，发现并不是只有上面的状态是必胜/必败

例如有石堆$1 2 3$，也是能做到最后取空的控制，说明偶数堆且成对相等和必胜必败没不全等只有被包含关系。

先直接上结论

所有石头堆的异或值为$0$，显然如果当前为$0$,那么任意操作会使异或值变成非0

假设异或值为$k \neq 0$，从数量为$a$的堆中取走，最后剩下$b$个，

那么取走的个数为$a-b \ge 0$,$k \oplus a \oplus b = 0$(原来的异或去掉a 新增b)

所以$b = a \oplus k$也就是要证明存在a使得$a \ge a \oplus k$

$k$是所有数量的异或结果，所以$k$的最高位$1$一定存在于某个$v[i]$中

$v[i]$ 和 $v[i]\oplus k$在高于$k$的最高位的位,值是相等的，在$k$的最高位$v[i]$为1,而$v[i]\oplus k$为$0$，所以存在$a = v[i]$使得$a \ge a \oplus k$,所以任意异或非$0$的$k$可以一步操作转化为$0$。

综上任意状态，能够通过0步或者1步转化为异或和为0。并且异或和为0是一个可以交替进行并被控制的平衡态。

至于为什么是想到异或和，我说不出，这个结论我也是从其它地方拿来，只会证明。

反过来再看NIM 1,会发现，虽然说是控制值相等，同时也就是控制异或和相等。

SG 函数

有向无环图上

$ \operatorname{mex}(S)=\min(\{x\}) \quad (x \notin S, x \in N) $

$\operatorname{mex}(S) = $集合$S$中不包含的最小非负整数

$ \operatorname{SG}(x)=\operatorname{mex}( \{ \operatorname{SG}(y) | y是x的后继 \} ) $

边界也就是没有出度的点，$\operatorname{SG}(\emptyset)=0$

显然如果$SG(x) = 0$，那么它的所有后继$\ne 0$,如果$SG(x) \ne 0$, 那么一定存在一个后继$SG(y) = 0$

换句话说$SG(x) = 0$的任意操作走向一个$SG(y) \ne 0$ , 而$SG(x) \ne 0$ 你总可以找到一个操作$SG(y) = 0$

所以一定能控制$SG(x) = 0$ 的平衡态，也一定能通过0步，或1步达到这个平衡态。

所以如果我们用$SG(失败状态) = 0$, 然后状态之间加上有向边, 那么以此计算$SG$ 就可以知道每个状态是成功还是失败了

应用在NIM 2中

考虑单个石堆游戏

有 $SG(个数) = 个数$

于是$SG(state(c_1,c_2,c_3,\cdots)) = c_1 \oplus c_2 \oplus c_3 \oplus \cdots= SG(c_1) \oplus SG(c_2) \oplus SG(c_3) \oplus \cdots$

对于多个游戏的组合(n个有向图)

结论, 一个游戏的$SG$函数值等于各个游戏的$SG$函数值的$Nim$ 和(异或和)

$\operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \ldots \oplus \operatorname{SG}(s_n)$

同上面证明NIM 2的过程，假设所有异或和为$k$ (总状态)，我们能得到

存在至少一个$i$满足$SG(s_i) > SG(s_i)\oplus k$,对于第$i$个游戏，$SG(s_i)\oplus k$是$SG(s_i)$ 的后继状态

因为注意到$SG$ 是通过$\operatorname{mex}$定义的意味着, 如果$SG(x) = w$, 那么它一步是可以走到$0..w-1$的任意$SG$状态的, 这就是NIM二中的一堆里面任意取个数的意义一样

所以 $SG(state(s_1,s_2,s_3, \cdots)) = SG(s_1)\oplus SG(s_2)\oplus SG(s_3)\oplus \cdots $

参考

game theory

Sprague–Grundy_theorem

Hello 2020

發表於 2020-01-09 更新於 2024-10-23 分類於 Codeforces ， Div1+2 Disqus：文章字數： 811 所需閱讀時間 ≈ 3 分鐘

E (计算几何,浮点数)

E

原题链接

2500评分

大意

平面上n个点，不存在3个共线,

对于所有(点p,另外四个点),如果另外四个点能包围点p则计数+1,对于同样的p和选中的4个点，不论有几种方式，只要能包围就计数+1

求p依次取遍所有点的计数和

范围

5<=n<=2500,

3s

1024MB

官方题解

https://codeforces.com/blog/entry/72804

题解

计算几何我就开始自闭了

最终要求的为sum{是否包围(p,另外四个点)},反向问题为

sum{是否不包围(p,另外四个点)}

考虑选取总方案为

$n*C_{n-1}^4$

如果选取的4个点，对于点p在同一个半圆内，那么选取的4个点无法包围，如果不在同一个半圆内则能包围

如果选取的4个点在同一个半圆内，则它们以p为顶点，构成的夹角小于180度，则这个夹角上存在顺时针的起始和结束点

假设选取点p和起始点q1，那么剩余三个点q2,q3,q4,与p和q1构成的夹角应该在0 到180度之间(且保证方向，也就是-0到-180度是不可取的)

这样对于每一个不包围的4个点，能做到不重不漏的计算

O(p枚举 * 计算几何排序和遍历)

然后计算几何和浮点数和test9杀我,我浮点数+计算几何就是过不了，然后换成纯整数处理过了，自闭

代码

accept

68473398 Wrong answer on test 9

68473313 Wrong answer on test 9

68473215 Runtime error on test 9

68473189 Runtime error on test 9

68473103 Runtime error on test 9

68473021 Runtime error on test 9

68471693 Runtime error on test 9

68471651 Runtime error on test 9

68471600 Wrong answer on test 9

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const long double pi = acos(-1.0);

pair<ll,ll>xy[3010];
pair<ll,ll>xysort[3010];
int n;

template<class T1, class T2>
inline const pair<T1, T2> operator-(const pair<T1, T2>&p1, const pair<T1, T2>&p2) {
  return {
    p1.first - p2.first,
      p1.second - p2.second
  };
}

ll cross(pair<ll,ll> vec1,pair<ll,ll> vec2){
  auto [x1,y1] = vec1;
  auto [x2,y2] = vec2;
  return x1*y2-x2*y1;
}

int main() {
  ll n;
  scanf("%lld",&n);
  rep(i,0,n){
    ll x,y;
    scanf("%lld %lld",&x,&y);
    xy[i] = {x,y};
  }
  ll res = n * ((n-1) * (n-2) * (n-3) * (n-4) / (1*2*3*4));
  rep(i,0,n){
    rep(j,0,n){
      if(i == j)continue;
      xysort[j>i?j-1:j] = xy[j];
    }
    sort(xysort+1,xysort+n-1,
        [i](const pair<ll,ll>p0,const pair<ll,ll>p1) -> bool{
        ll cross0 = cross(p0-xy[i],xysort[0]-xy[i]);
        ll cross1 = cross(p1-xy[i],xysort[0]-xy[i]);
        if(cross0 >=0 && cross1 < 0){
          return true;
        }else if(cross0 < 0 && cross1 >= 0){
          return false;
        }
        ll cross01=cross(p0-xy[i],p1-xy[i]);
        return cross01 <= 0;
        });
    int index = 1;
    // 四个点的起始点,首尾游标
    rep(j,0,n-1){
      while(index < j + n-1){
        ll crossij = cross(xysort[index%(n-1)]-xy[i],xysort[j]-xy[i]);
        if(crossij >= 0 ){
          index++;
        }else{
          break;
        }
      }
      // C_cnt^3
      ll cnt = index - j - 1;
      res -= (cnt * (cnt - 1) * (cnt - 2)) / (1*2*3);
    }
  }
  printf("%lld\n",res);
  return 0;
}

总结

1是想到反向计算，我一直在想算三角形然后带其它点，再容斥，就没想出来

2是浮点数精度，哎自闭，还是整数香

Good Bye 2019

發表於 2020-01-04 更新於 2024-10-23 分類於 Codeforces ， Div1+2 Disqus：文章字數： 884 所需閱讀時間 ≈ 3 分鐘

F (分块算法)

F

原题链接

2600评分

大意

0/1构成的字符串, 如果s[l,r]长度为len,其中1的个数为n(n>0)且len%n == 0,那么这个子字符串为awesome

求awesome子字符串的个数

范围

原字符串长度[1,200'000]

官方题解

https://codeforces.com/blog/entry/72611

题解

首先想到的就是前缀和+暴力

预处理O(n),计算每个[l->r],只需要O(1)

总的时间代价O(n^2)

显然过不了,然后我赛内想来想去没想到方法了

pref表示前缀和

如果 $r - l + 1 = k \cdot (pref[r] - pref[l - 1])$,那么就是awesome的

变形 $r - k \cdot pref[r] = l - 1 - k \cdot pref[l - 1]$

所以对于k=1->n,计算上面成立有多少对

假设取一个给定的值T

对于 k>T, $r - k \cdot pref[r] = l - 1 - k \cdot pref[l - 1]$ , 也就是这类成立的子字符串包含1的个数比较少,我们遍历前缀，然后找比它1个数大的值小于等于n/T的，对于所有k>T，总时间代价为O(n * n/T)

对于 k<=T , $-nT \le i - k \cdot pref[i] \le n$ , 对于给定k，遍历O(n) ，总时间代价O(nT)

所以理论上 T=sqrt(n)时，总的时间代价为O(n^(3/2))

代码

这里T取的死值300,没有取sqrt

6224 ms

我自闭了这个TLE11: https://codeforces.com/contest/1270/submission/68136316

然后这个过了: https://codeforces.com/contest/1270/submission/68136440

点compare就换了一下map的位置

另外我把T设置为450(sqrt(200'000)=447.21359549995793)也TLE11: https://codeforces.com/contest/1270/submission/68136641

这个慢的是后一部分，原因基本就是(map/unordered_map)的代价,优化方案例如有数组+pair,最后 sort一下统计(没写)

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const double pi = acos(-1.0);
 
// len % (num of 1) == 0
 
// fft?
 
// 10010010
// n/1 has only 1
// n-1 has only 2 of 1
 
// kmp?
 
char s[200010]; // 0->n-1
 
int onecnt = 0;
int onepos[200010]; // 0->n-1
unordered_map<int,int> v2cnt;
 
int n;
int main(){
  scanf("%s",s);
  n = strlen(s);
  rep(i,0,n){
    if(s[i]=='1'){
      onepos[onecnt++]=i;
    }
  }
  int T = 300;
  if(onecnt == 0){
    printf("0\n");
    return 0;
  }
  ll ans = 0;
  int stj = 0;
 
  // ans ==15612){ // n =1000
  //
  // k>T -> precnt <= n/T
  rep(i,0,n){
    int cnt = 0;
    rep(j,stj,onecnt){
      cnt++;
      if(!(cnt<=n/T))break; // 注意 这个是上界，不是精确范围，
      // 0-index
      // i 010 pos 01100 posnext
      // [i -> [pos -> posnext-1] ]
      int pos = onepos[j];
      int posnext = 0;
      if(j == onecnt -1){
        posnext = n;
      }else{
        posnext = onepos[j+1];
      }
      // [lenst+1->lenend] = lenend/cnt-lenst/cnt
      int lenst = pos-i;
      int lenend = posnext-i;
      // printf("%d,[%d,%d]=%d , len:[%d->%d] \n",i,pos,posnext,cnt,lenst,lenend);
      if( (lenend/cnt) >= T){ // 精确的范围
        ans+=(lenend/cnt)- max((lenst/cnt),T);
      }
      // printf("ans=%lld\n",ans);
    }
 
    if(stj < onecnt && onepos[stj] <= i){
      stj++;
    }
  }
  //  cout<<"            ans="<<ans<<endl;
  // k<=T, k=1->T,i=0->n
  rep(k,1,min(T,n)+1){
    v2cnt.clear();
    // i - k * pre[i];
    v2cnt[0]++;
    ll cnt = 0;
    rep(i,0,n){
      cnt+=(s[i] == '1');
      v2cnt[i+1-k*cnt]++;
    }
    for(auto item:v2cnt){
      ll c = item.second;
      ans+=c*(c-1)/2;
      // if(c>1){
      //   printf("k=%d: [%lld,%lld]\n",k,v,c);
      // }
    }
  }
  // ans
  printf("%lld\n",ans);
  return 0;
}

总结

这种分块首先要看出是分块

然后分块除了实现和算法本身，一个需要注意的就是划分边界的处理，做到不重不漏,不要把理论最大最小上下界当成精确边界，另外因为实现是分块，所以理论上改变划分界限，代码应该有相同输出，可以作为测试方法。

Codeforces Round 597

發表於 2019-11-03 更新於 2024-10-23 分類於 Codeforces ， Div2 Disqus：文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘

E (模拟,DP,概率论),F(bitDP,容斥原理)

E

原题链接

2300评分

大意

很难直接说，看原题目图片

大概就是10x10网格，从左下横走到头，向上一层，再横走到头，再向上一层，这样走到左上角

每次步长整数[1->6]等概率

其中有一些纵向梯子，梯子出度为0/1

只能停在梯子下方时(立刻?)使用梯子，重叠的梯子不能切换,不能从上到下使用梯子, 不能在没有横着走的情况下连续使用梯子

如果走的步数会导致超过终点那么他不会走

他会尽快走

求期望步数

数据范围

梯子数量<=100

题解

显然虽然我赛内没有做出来，也知道基本知识点是 dp和概率论，然而我的概率论弱到爆炸

然后也是显然把二维降到一维

官方题解

先定义f函数如果

i点没有梯子， f(i) = i;

i有梯子， f(i) = 梯子的目标;

i点到终点，的最小期望步数为$dp_i$

显然dp_100 = 0

$$dp_i = 1 + \sum_{r = 1}^{6} \frac{1}{6} \cdot \min(dp_{g(i, r)}, dp_{f(g(i, r))})$$ // 这里min是必要的因为可能因为一些小梯子错过一些大梯子，不一定爬梯子更优

从i走 r=1->6步,到 i->i+r 或者

其中当 $i+r<=100$时 $g(i, r) = i + r$ 否则 $g(i,r)=i$

作为一个概率论弱菜，想说这里的期望步数竟然可以直接取min的咯????

以及为什么明明是 1/6 的前进概率，却可以反过来还是按照1/6来算???

对于上面会超过终点，也就是$95 \leq i \leq 99$时

$dp_i = \frac{6}{100 - i} \cdot \left( 1 + \sum_{r = 1}^{100 - i} \frac{1}{6} \cdot \min(dp_{i + r}, dp_{f(i + r)}) \right)$

其实也是上面的式子，把其中走改为停在原地 $dp_i$再移项得到的

这里我卡了很久很久很久

大概最后能理解的是

dp表示的是剩余期望步数,是一个最终结果值

如果考虑过程的话，每一次 i 会向 i+1~6 发送 (期望步数-1)*1/6

而计算当计算到i时，小于i的所有都已经和最终结果相同了，所以对于dp[i]来说

dp[i][最终结果] = sum{dp[i-1~6][最终结果]-1}/6也是满足的

也就是每次从i走1/6的概率和反过来看最终期望值，可以用一样的概率

然后对于尾部的思考感觉还是没有直接思考出，但是用无穷级数得到一样的答案了XD

感觉自己概率论还是没有入门啊

当然题解的另外一个方法就是直接模拟个1000次

每次至少前进一步，那么100步以后，就只剩下最后几个，然后就没了，每轮的量也就100*6 随便搞啊精度应该不会爆吧

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

// 10x10
// 左下->左上

// 蛇形路线
//
// 有纵向梯子
// 不能用连续的后一个梯子

int main() {
  int grid[10][10]; // 输入
  int arr[110]; // 可以用梯子到达的目标
  int flat[10][10]; // 映射为一维数组
  rep(i,0,10){
    rep(j,0,10){
      scanf("%d",grid[i]+j);
      flat[i][j] = (9 - i) * 10 + ((i & 1) ? j : 9 - j);
      arr[flat[i][j]] = flat[i-grid[i][j]][j];
    }
  }

  double dp[100];
  dp[99] = 0;
  per(i,0,99){
    double dpi = 0;
    int c = 6;
    rep(r,1,7){
      if (i + r >= 100) continue;
      dpi += min(dp[i + r], dp[arr[i + r]]) / 6;
      c--;
    }
    dp[i] = 6 * (1+dpi) / (6 - c);
  }
  printf("%.10lf\n",dp[0]);
  return 0;
}

参考

https://www.cnblogs.com/LLTYYC/p/11782276.html

问题难点分析

为什么可以反过来使用概率,反过来用不等于反着走，而且期望的事情，可以把dp[i]改成dp[i][过程中/最终值]来加深理解

然后就是自己能到自己的理解了，依照各个题解过程意思是等价代换推新公式即可？

然后就是题目这里的梯子，其实是一个可选择的不消耗次数的传送门，当你停在门前时才可选择，不能路过时使用。

F

原题链接

2300评分

大意

t组测试数据

求 l<=x,y<=r中满足 x+y==x^y的有序对(x,y)的个数

数据范围

0<=l<=r<=10^9

题解

如果一道题看上去像bitdp，长得像容斥原理，那么它就是 bitdp+容斥原理

假设 F(n,m)表示 a属于[0,n], b属于[0,m]

那么ans = F(r,r) - 2F(l-1,r) + F(l-1,l-1)

所以如果能计算F(n,m)即可

G[前i位][x 是否贴着上限][y 是否贴着上限]的方案数

贡献

G[i][false][false]:

x3 -> G[i+1][false][false]

(因为都没有贴着上限，所以x,y值无论填0/1都依然没有贴着上限,由因为两个只能最多有一个1,所以只有(0,0),(1,0),(0,1)三种))

对于

G[i][false][true] / G[i][true][false] / G[i][true][true]

其中至少有一个是贴着上限的，那么，贡献时注意是否上限，填写的时候不要超过上限

也注意x&y == 0 也就是x+y<=1

rep(x,0,2){
  rep(y,0,2-x){
    G[i][ln & ( x == ((n>>(30-i))&1) )][lm & ( y == ((m>>(30-i))&1) )] += G[i-1][ln][lm];`
  }
}

当然可以用滚动数组进行优化

代码

官方题解

https://codeforces.com/blog/entry/71080

直接设f(l,r)是l<=x,y<r的答案，也就是真的答案是f(l,r+1)

有f(0,r)=2r-1+f(1,r), 因为 (0,0),(0,1~r-1),(1~r-1,0)都合法一共(2r-1)

如果l,r都大于0那么 f(2l,2r) = 3 f(l,r)

其实和上面的数位dp 推理很像，这里是考虑最后一位，只有3种可选的，且都合法，因为有2倍保证

然后再把 l,r 不是2的倍数的和2的倍数之间找出关联，最终可归约到 f(0,?) 即可

问题难点分析

第一个是我有往数位dp想，但是没想到具体

一个是没有拆解成F(x,y)变成类似前缀和或者说计算子矩阵和的样式

另外就是数位dp做的题太少，还是不够熟悉

问题还有就是两种方法，只要在草稿纸上多画一画会变得简单很多。

虽然以前对两个的维度来做前缀，或者向下归约的题型做过，但实际操作还是体现出了不熟练

容斥是没怎么用还是矩阵和数位dp

Codeforces Global Round 5

發表於 2019-10-17 更新於 2024-10-23 分類於 Codeforces ， Div1+2 Disqus：文章字數： 627 所需閱讀時間 ≈ 2 分鐘

E (bitdp)

原题链接

tourist出的题！

大意

二叉查找树节点有n个且

倒数第二层满节点

每个节点和左儿子奇偶相反

每个节点和右儿子奇偶相同

的方案数

结果mod 998244353

数据范围

1<=n<=1'000'000

3s

512MB

题解

塞内没看到sum of depths做了个假题

第一个思路直接树上dp, dp[cnt][height][oddoreven] 表示总节点cnt,高度height的,root奇偶性为oddoreven的方案数

然后dp表达式

dp[cnt][height][root is odd?] = 

sum{
  dp[left cnt][height -1/-2][root is odd ^ 1] *
  dp[cnt-1-left cnt][height -1/-2][even] *
}

其中注意保证性质

调完bug的代码TLE 11 见下面

因为一些编写过程的推理问题，遗留的height,其实当cnt确定，根据题目的要求，height也就唯一了，算是多设计的

因为每次计算时计算的子来源大概有 cnt/2左右个

代码

TLE 11

代码

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);
 
// 1 -> 3 -> 7(C(4,4)) -> 15 -> 31 -> ...
// 4(C 4,1) 5(C 4,2)
 
//    ji
// ou     ji
//ji     ou      ou  ji
//ou ji ji ou  ji ou ou ji
 
 
// dp[cnt][height][ji/ou]
 
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
 
ll dp[1000010][22][2];
 
int v2h(int v){
  int ret = 0;
  while(v){
    ret++;
    v>>=1;
  }
  return ret;
}
 
int h2v(int v){
  return (1<<v)-1;
}
 
ll dfs(int cnt,int height,int jiou,int dep=0){
  // rep(i,0,dep){
  //   printf("\t");
  // }
  // printf("call dfs(%d,%d,%d)\n",cnt,height,jiou);
 
  ll &ret = dp[cnt][height][jiou];
  if(ret != -1)return ret;
  if(height == 1){
    return ret = (cnt == 1 && jiou == 1);
  }
  if(height == 0){
    return ret = (cnt == 0);
  }
  if(cnt > h2v(height) || cnt <= h2v(height-1))return ret = 0;
  ret = 0;
  int r = h2v(height-1);
  int l = cnt-1-r;
 
  rep(i,l,r+1){
    if(i%2 == jiou)continue;
    int hl = v2h(i);
    int hr = v2h(cnt-1-i);
    if(hl != height-1){
      if(hl != height-2 || hl > 1)continue;
    }
    if(hr != height-1){
      if(hr != height-2 || hr > 1)continue;
    }
    if(!(hr == height -1 || hl == height -1))continue;
 
    ll lcnt = dfs(i,hl,jiou^1,dep+1);
    ll rcnt = dfs(cnt-i-1,hr,0,dep+1);
 
    // rep(i,0,dep){
    //   printf("\t");
    // }
    // printf("dfs(%d,%d,%d) %d-1-%d : {l * r}={%lld * %lld}\n",cnt,height,jiou,i,cnt-1-i,lcnt,rcnt);
    (ret+=lcnt*rcnt)%=MOD;
  }
  // rep(i,0,dep){
  //   printf("\t");
  // }
  // printf("ret dfs(%d,%d,%d)=%lld\n",cnt,height,jiou,ret);
  return ret;
}
 
int main(){
  int n;
  cin>>n;
  int h = v2h(n);
  rep(i,0,1000001){
    rep(j,0,22){
      rep(k,0,2){
        dp[i][j][k] = -1;
      }
    }
  }
  cout<<(dfs(n,h,0)+dfs(n,h,1))%MOD<<endl;
  return 0;
}

果然tle了

AC代码 … TODO