题解：P16450 [XJTUPC 2026] 但是什么也不会改变 3

· · 题解

很显然，这题需要推式子。\ \ 我们发现，数列的后一项永远在前两项之间，考虑枚举第一项和第二项的差，令其为 d。稍微列出几项找规律，发现当差为 d 时后面的数列的种数竟然是 z^{d-1}-1。 ::::success[证明] 在差为 d 的两数直接有 d-1 个数，每个数都可以选或不选，总可能数为 z^{d-1}。由于条件规定了数列内部的大小关系，所以每种选法都只有一种对应数列。刨去全不选的情况就是 2^{d-1}-1。证毕。 :::: 考虑差为 d 的两数在 [1,n] 内共 2\times(n-d) 种选法。所以答案就是 \sum_{d=2}^{n-1} 2\times(n-d)\times(2^{d-1}-1)，加上快速幂足以通过此题。\ \ 考虑优化，有：

ans=\sum_{d=2}^{n-1} (n-d)\times(2^{d}-2)

将其展开：

ans=\sum_{d=2}^{n-1} (n-d)\times2^d-\sum_{d=2}^{n-1} (n-d)\times2

运用等差等比计算公式和等差数列计算公式得：

ans=(2^{(n+1)}-4\times n)-(n^2-3\times n+2)

所以最终结果是：

ans=2^{n+1}-n^2-n-2

完全可以通过。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int zh[1001010];
signed main(){
    int n,ji=1;cin>>n;
    for(int i=1;i<=n+1;i++)ji*=2,ji%=998244353;
    cout<<(ji-n*n-n-2+998244353000000000)%998244353;
    return 0;
}

题外话：本题完全可以 1\le n\le10^{1000000}，考一个 FFT，成功升黑。