题意
定义 n-数列 为满足以下条件的数列 \({a_i}\) :
- 数列长度不小于 \(3\) , 且每个元素为 \(1\) 到 \(n\) 的整数 .
- 对于任意 \(k \ge 3\) , 有 $ (a_k-a_{k-2})(a_{k-1}-a_{k-2})<0$ .
给出 \(n\) , 求 n-数列 的个数 , 对 \(10^9+7\) 取模 .
\(n\le 10^{500000}\)
时空限制 \(1s,512MB\)
题解
第二个条件的易于理解的说法是 : 每个元素的大小都介于后两个元素之间 . 而对于每个限制 , 都有两种情况 , 即 $a_k>a_{k-2}>a_{k-1} $ 或 $a_k<a_{k-2}<a_{k-1} $ .
尝试手动模拟大小关系 , 发现这些大小关系的限制很紧 , 如图 :
逐个条件进行推导 , 当我们钦定 \(a_2<a_3\) , 就一定有 $ a_3>a_4$ , $ a_4 <a_5$ 等等 . 也就是说 , 一旦 \(a_2,a_3\) 的大小关系得以确定 , 所有的限制都只剩下一种情况 .
而观察 \(a_2<a_3\) 情况下的所有大小关系 , 发现这些关系中包含一个完整的链 : $ 5>4>1>2>4 $ . \(a_2 > a_3\) 同理 .
因此对于确定的 \(k\) 个不同数字 , 组成一个合法序列的方法有且仅有 \(2\) 种.
对于一个长度为 \(k\) 的 n-数列 , 相当于在 \(n\) 个数字里选互不相同的 \(k\) 个 , 每种选择方案对应两个序列 . 可得答案即为 :
\[2\times\sum_{k=3}^{n} C_n^k\\ =2\times(\sum_{k=1}^{n} C_n^k - C_n^0- C_n^1- C_n^2) \\ =2\times(2^n-1-n-\frac{n(n-1)}{2}) \]最后 , 因为要取模 , 所以高精度是没有必要的 . 分别逐位读取处理 $n\mod p $ 与 $2^n \mod p $ 即可 .
代码
#include<bits/stdc++.h>
#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define int long long
#define INF 0x3f3f3f3f
#define INF64 1e18
using namespace std;
constexpr int N=26;
constexpr int p=1e9+7;
int qp(int x,int t){
int res=1;
while(t){
if(t&1) res=res*x%p;
x=x*x%p;
t>>=1;
}
return res;
}
string s;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>s;
int x=0,y=1;
for(int i=0;i<s.length();i++) x=(x*10+s[i]-'0')%p,y=qp(y,10)*qp(2,s[i]-'0')%p;
cout<<2*(y-1-x-x*(x-1)/2%p+2*p)%p;
}