题解[A 序列问题]

链接：https://ac.nowcoder.com/acm/contest/9798/A
来源：牛客网
题目描述
存在一个集合S，由1到n这n这元素组成，A，B是S的两个非空子集，若对于任意的元素X∈A，Y∈B，皆满足Y-X>=q，则称A，B是一组满足条件的集合组。多组询问，每次给出n，q，求对于集合S，有多少组满足条件集合组，答案对998244353取模。

可能更好的阅读体验
推式子题，主要是细节特别多。讨论 $q$ 的范围，分 5 类。

只需 $B_{min}-A_{max} \geq q$

令 $i=A_{max},j=B_{min}$ , 考虑枚举 $i,j$ ,则 $A,B$ 集合中的其他数分别在 $[1,i-1],[j+1,n]$ 中任取。

易得：

$ans=\sum _{i=1}^{n} 2^{i-1} \times \sum_{j=max\{i+q,1\}}^{n} 2^{n-j}$

由于此式不能优美地化简，对 $q$ 分类。

$q \geq n$ 时, $ans=0$ .
$q \in [0,n-1]$ 时，
$ans=\sum _{i=1}^{n-q} 2^{i-1} \times \sum_{j=i+q}^{n} 2^{n-j}$

$= \sum _{i=1}^{n-q} 2^{i-1} \times (2^{n-i-q+1}-1)$ $= (n-q-1) \times 2^{n-q} +1$
$q\in [-n+1,-1]$ 时，有两类，别漏了第二类。
$ans=\sum _{i=|q|+1}^{n} 2^{i-1} \times \sum_{j=i+q}^{n} 2^{n-j}+\sum _{i=1}^{|q|} 2^{i-1} \times \sum_{j=1}^{n} 2^{n-j}$

$= \sum _{i=|q|+1}^{n-q} 2^{i-1} \times (2^{n-i-q+1}-1)+(2^{|q|}-1)\times (2^n-1)$ $=(n-|q|)\times 2^{n+|q|}-2^n+2^{|q|}+(2^{|q|}-1)\times (2^n-1)$
$q \leq -n$ 时，随便选 $ans=(2^n-1)^2$

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const LL MOD=998244353;

LL fpow(LL x,LL k,LL MOD)
{
    LL res=1; x%=MOD;
    while(k) {
        if(k&1) res=res*x%MOD;
        x=x*x%MOD; k>>=1;
    }
    return res;
}

int T;
LL n,q;

int main()
{
//    freopen("1.in","r",stdin);

    scanf("%d",&T);
    while(T--) {
        scanf("%lld%lld",&n,&q);
        if(q>=n) printf("0\n"); 
        else if(q>=0) printf("%lld\n",((n-q-1)%MOD*fpow(2,n-q,MOD)%MOD+1+MOD)%MOD);
        else if(n+q<=0) printf("%lld\n",(fpow(2,n,MOD)-1)*(fpow(2,n,MOD)-1)%MOD);
        else if(q<0) printf("%lld\n",
            (((n+q)%MOD*fpow(2,n-q,MOD)%MOD-fpow(2,n,MOD)+fpow(2,-q,MOD))%MOD+
                (fpow(2,-q,MOD)-1)*(fpow(2,n,MOD)-1)%MOD+MOD)%MOD);
    }
    return 0;
}