特殊数列

在知乎上看到一个有趣的问题: 如何证明这个数列无界？ 在此记录一下简单的做法，然后把这篇博客记录以后遇到的一些特殊数列。

证明：当 $x$ 是无理数时，$f_n(x)=\sum _{i=1}^n(-1{)}^{\lfloor ix\rfloor }$ 无界

$\lfloor x\rfloor$ 表示 $x$ 的整数部分， $0\le \{x\}\doteq x-\lfloor x\rfloor <1$ 表示 $x$ 的小数部分

为了更顺畅的介绍这个数列，我们先来点前戏，不然插入的时候就不那么顺滑了 0.0 不要笑，我没有开车 0.0

连分数

它和 Farey 序列，无理数的有理逼近，密切相关，还是由于求 Pell 方程的快速方法

我们将一个整数序列 $a_0,a_1,\cdots ,a_n$ 构成的分数叫做连分数，记作 $$[a_0,a_1,\cdots ,a_n]=a_0+\frac{1}{a_1+\frac{1}{a_2+\cdots }}$$ 其中 $a_0$ 是整数， $a_i(i>0)$ 是正整数。

我们定义:

$p_0=a_0,p_1=a_1{a}_0+1,p_n=a_n{p}_{n-1}+p_{n-2}(n>1)$

$q_0=1,q_1=a_1,q_n=a_n{q}_{n-1}+q_{n-2}(n>1)$

那么数学归纳法易证： $$[a_0,a_1,\cdots ,a_n]=\frac{p_n}{q_n}=x_0$$ 并且还有

• $[a_0,a_1,\cdots ,a_n]=[a_0,a_1,\cdots ,a_{n-1}+\frac{1}{a_n}]$
• $p_{n+1}{q}_n-q_{n+1}{p}_n=(-1{)}^n$
• 从而 $$$$
• $$$$
• 从而 $$$$

对任意一个数 $$$$ 构造连分数

0. 初始 $$$$
1. $$$$ 取 $$$$ 的整数部分。
2. $$$$ 结束
3. 取 $$$$
4. ++$$$$ 回到步骤 1

从构造中，我们看出：连分数长度有限当且仅当 $$$$ 是有理数，此时，最后一项得到的连分数就是 $$$$。

当 $$$$ 是无理数时， $$$$ ，又因为 $$$$ 且 $$$$ 单调递增，$$$$ 单调递减。所以 $$$$。并且 $$$$

补充定义

$$$$

$$$$

显然，$$$$

唯一分解

对于任意给定 $$$$，对任意 $$$$，有如下唯一分解： $$$$ 其中 $$$$ 且对任意 $$$$，$$$$ 。

$$$$ 何时有界

由于 $$$$， 所以我们仅考虑 $$$$ 时，$$$$ 跑遍 $$$$，即 $$$$ 从而 $$$$ 推出 $$$$ 无界。

对任意无理数 $$$$，我们证明 $$$$ 无界，从而 $$$$ 无界

目前没理解论文中的做法，太繁琐了

显然，我们只需考虑 $$$$

我们考虑 $$$$ 的连分数 $$$$，由于 $$$$ (目前不知道有什么简单的操作)

这个问题可以推广到更一般的情形：单栏阅读 双栏阅读

里面定理一挺有意思的，虽然长但是很清晰。

另一个相关问题：https://www.zhihu.com/question/392014769

是否存在 $$$$ 使得， $$$$ 对所有 $$$$ 成立。(izlyforever 和 寨森 Lambda-CDM 建议修改)

存在无穷多个正整数 $$$$ 使得 $$$$

引理： 对任意无理数 $$$$ , 存在无穷多个 $$$$，使得 $$$$

我们考虑 $$$$ 的连分数 $$$$, 我们知道 $$$$，由于 $$$$, 所以存在 $$$$ 使得 $$$$, 此时 $$$$，所以我们不妨假设 $$$$。所以 $$$$ 我们仅考虑 $$$$ 为奇数数的情况，此时 $$$$，所以 $$$$。而 $$$$ 即为所求。

实际上 $$$$ 为偶数时，也可以取做，只是此时 $$$$ 要换成 $$$$

取引理中 $$$$，由于 $$$$ 是周期为 $$$$ 的偶函数。所以 $$$$

受 寨森 Lambda-CDM 启发，可以不用引理直接证明：

存在无穷多个正整数 $$$$，使得 $$$$

Proof：考虑 $$$$ 的连分数 $$$$，我们有 $$$$，所以 $$$$

这个问题还关联这 Irrationality Measure，菲尔兹奖级别的工作！

Irrationality Measure

对于给定是实数 $$$$, 定义 $$$$ 显然考虑连分数，我们知道 当 $$$$ 是有理数时，$$$$，无理数时，$$$$。

Roth 证明，当 $$$$ 是代数数时 $$$$，因此获得 Field 奖。

$$$$，其中 $$$$ 为刘维尔（Joseph Liouville）数

我们下面证明：当 $$$$ 时，$$$$，则 $$$$ 的外（lebesgue）测度 $$$$，从而（lebesgue）测度 $$$$

由于 当 $$$$ 时， $$$$ 只有可数个，记作 $$$$ ，按照定义，$$$$, 另一方面 $$$$，从而 $$$$，同理可证了$$$$，从而 $$$$ 从而$$$$。其中 $$$$

sagemath 数值测试(Jupyter Notebook 上运行)

x = continued_fraction(1/pi).convergents()
for i in range(1,32):
    n = x[i].denominator()
    print(N(abs(sin(n))-pi/n),"\t= ",abs(sin(n))-pi/n ) # 后来精度就崩了

x = continued_fraction(1/pi).convergents()
for i in range(1,32):
    n = x[i].denominator()
    print(i,N(abs(sin(n))*n),"\t= ",abs(sin(n))*n) # 后来精度就崩了
PYTHON

$$$$, 其中 $$$$

方法：On a Series of Goldbach and Euler

$$$$

其中 $$$$，$$$$

$$$$

洛谷题目，具体题号就不便说了。

数据范围 $$$$ 。我们注意考察 $$$$ 的意义！假设我们要上楼梯，每次只能上 1 步或者 $$$$ 步，那么 $$$$ 就是方案数，因此，我们显然有

$$$$

当然了我们不考虑意义直接用 $$$$ 也可以得到这个公式。

无法过题的 $$$$ 代码，原因是没法找一个合适的基底

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using BI=__int128;
const LL mod=1e9+7;
const int M =10004;
BI a[4*M],r[4*M],ans[2*M];
template<typename T,typename U>
T powmod(T x,U n,T p){
  T r(1);
  while(n){
    if(n&1) r=r*x%p;
    n>>=1;  x=x*x%p;
  }
  return r;
}
void bitreverse(BI *x,int len){
  for(int i=0,j=0;i!=len;++i){
    if(i>j) swap(x[i],x[j]);
    for(int l=len>>1;(j^=l)<l;l>>=1);
  }
}
const BI FM = BI(29)<<57|1,gg=3;
// the mod must NTT-friendly or (len+1)*mod^2 < FM
void ntt(BI *x,int len,bool isInverse=false){
  g = powmod(gg,(FM-1)/len,FM);
  if(isInverse){
    g=powmod(g,len-1,FM);
    BI invlen = powmod(BI(len),FM-2,FM);
    for(int i=0;i!=len;++i){
      x[i]=x[i]*invlen%FM;
    }
  }
  bitreverse(x,len);
  for(int half=1,step=2;half!=len;half<<=1,step<<=1){
    BI wn = powmod(g,len/step,FM);
    for(int i=0;i<len;i+=step){
      BI w(1);
      for(int j = i;j<i+half;++j){
        BI t=(w*x[j+half])%FM;
        x[j+half]=(FM-t+x[j])%FM;
        x[j]=(x[j]+t)%FM;
        w = w*wn%FM;
      }
    }
  }
}
void stand(BI *a, int n){
  for(int i=2*n;i>n;--i){
    a[i-1]=(a[i-1]+a[i])%mod;
    a[i-n-1]=(a[i-n-1]+a[i])%mod;
    a[i] = 0;
  }
}
void square(BI *a, int n){
  int len = 1<<(32-__builtin_clz(2*n+1));
  ntt(a,len);
  for(int i=0;i<len;++i){
    a[i]=a[i]*a[i]%FM;
  }
  ntt(a,len,1);
  stand(a,n);
}
void mul(BI *a,BI *b,int na,int nb){
  int len = 1<<(32-__builtin_clz((na+nb)+1));
  ntt(a,len);ntt(b,len);
  for(int i=0;i<len;++i){
    a[i] = a[i]*b[i]%FM;
  }
  ntt(b,len,1);ntt(a,len,1);
  stand(a,na);
}
void initC(int m){
  for(int i=0;i<=m;++i){
    ans[i] = 1;
  }
  for(int i=m+1;i<=2*m;++i){
    ans[i] = (ans[i-1]+ans[i-m-1])%mod;
  }
  memset(a,0,sizeof(a));
  memset(r,0,sizeof(r));
  r[0]=a[1]=1;
}
LL getans(LL n,int m){
  initC(m);
  while(n){
    if(n&1) mul(r,a,m,m);
    n>>=1; square(a,m);
  }
  LL ret = 0;
  for(int i=0;i<=m;++i){
    ret+=(r[i]*ans[i+m])%mod;
  }
  return ret%mod;
}

int main() {
  //freopen("in","r",stdin);
  //freopen("m","w",stdout);
  std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
  LL n;
  int m;
  while(cin>>n>>m){
    if(m==0){
      cout<<powmod(2LL,n,mod)<<endl;
    }else{
      if(n<=m){
        cout<<1<<endl;
      }else{
        cout<<getans(n-m,m)<<endl;
      }
    }
  }
  return 0;
}
CPP

求 $$$$ 阶线性递推关系式第 $$$$ 项

参考：2013/03/02 线性递推关系和矩阵乘法

上面文献的意义：矩阵加速已经成为过去式了，多项式加速时代的到来，NTT 加速多项式的时代到来。

设 $$$$，给定了初值 $$$$ 的情况下，求 $$$$

我们记 $$$$ 并且显然 $$$$ 我们就可以用矩阵乘法在 $$$$ 解决这个问题了。

但线性递推关系式可以不用矩阵优化到 $$$$ ：

显然 $$$$ 的特征多项式 $$$$，所以 $$$$，也就是说 $$$$ 可以由 $$$$ 线性表出，而 $$$$ 然后运算就是卷积运算，相当于多项式乘法！也就是说我们可以在 $$$$ 时间复杂度，求出 $$$$, 注意到 $$$$ 所以我们只需预处理出 $$$$ 这 $$$$ 个数即可。 代码见我博客的模板

这也提供了一般 $$$$ 阶矩阵的 $$$$ 次方的一个 $$$$ 的算法！！！卧槽！我也太帅了吧。

最后如果递推关系中仅有常数个 $$$$ 不为 0，此时还能用 NTT（数论快速变换） 利用 多项式带模除法: Division with remainder 的 $$$$ 算法，上述算法可以优化到 $$$$，（暂时不知道如何去掉 $$$$）但是写法太复杂。搞定！参考 这里，不要涉及矩阵

注意到一次乘法之后，会变成 $$$$ 的线性组合，$$$$ 这 $$$$ 个要再用前 $$$$ 线性表出，由于 $$$$ 仅有常数个不为 0，可以 $$$$ 复杂度把他们写成前 $$$$ 个的线性组合。

当 $$$$ 时，我们就有必要写带 NTT 的版本了（NTT 模板可以在我博客中找到）有需求的时候再写吧。

$$$$

数据范围：$$$$

记 $$$$ 满足 $$$$，则答案为 $$$$，其中 $$$$

假设 $$$$，则答案就是 $$$$，即答案是 $$$$

这个跟上面一样本质是一样的，做带模的多项式运算。

参考：zscoder 的博客

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

class Poly{
 public:
  const static int N = 2003;
  int d;
  LL a[N];
  Poly(int _d):d(_d){
    memset(a,0,sizeof(a));
  }
  auto& operator[](int i){
    return a[i];
  }
  Poly operator*(Poly &A){
    Poly R(d+A.d);
    for(int i=0;i<=d;++i){
      for(int j=0;j<=A.d;++j){
        R[i+j] += a[i]*A[j];
      }
    }
    return R;
  }
};
Poly mulmod(Poly &A,Poly &B,int m,LL mod){
  Poly R = A*B;
  for(int i=R.d;i>=m;--i){
    R[i-m] += R[i];
    R[i]=0;
  }
  R.d = m;
  for(int i=0;i<=m;++i){
    R[i]%=mod;
  }
  return R;
}
template<typename T,typename U>
T powmod(T x,U n,int m,LL mod){
  T r(0);
  r[0]=1;
  while(n){
    if(n&1) r=mulmod(r,x,m,mod);
    n>>=1;  x=mulmod(x,x,m,mod);
  }
  return r;
}

int main(){
  //freopen("in","r",stdin);
  std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
  LL n,r,mod;
  int m;
  while(cin>>n>>m>>r>>mod){
    Poly A(m-1);
    A[0]=A[1]=1;
    Poly R = powmod(A,n,m,mod);
    cout<<(R[r%m]*m%mod)<<endl;
  }
  return 0;
}
CPP

组合数倒数交错和 $$$$

考虑积分 $$$$，显然 $$$$ 且分部积分即可知道 $$$$，再等比数列求和就有

$$$$

To be continued