牛客IOI周赛21-提高组A题题解Java描述

链接：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分情况进行讨论。q>=n时为0；q<=-n+1时为任意非空集合数的平方；其他情况依次枚举A集合的最大值可以推出结果的表达式。
注意表达式溢出，不然只能过60%。

import java.util.*;
import java.io.*;
public class Main{

    private static long MOD = 998244353L;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(bf.readLine().trim());
        while(t-- > 0){
            String[] nq = bf.readLine().trim().split(" ");
            long n = Long.parseLong(nq[0]);
            //System.out.println(myPow(n));
            long q = Long.parseLong(nq[1]);
            long res = 0L;
            if(q >= 0 && q < n){
                long pow = myPow(n - q);
                res = (((n - q) % MOD * pow  - (pow - 1)) % MOD + MOD) % MOD;
            }else if(q < 0 && q > -1 * (n - 1)){
                long powN = myPow(n);
                long powNQ1 = myPow(1 - q);
                long powNQ2 = myPow(n - q);
                res = ((powN - 1) * (powNQ1 - 1) % MOD + MOD) % MOD;
                res = (res + ((n + q - 1) % MOD * powNQ2) % MOD + MOD) % MOD;
                res = ((res - ((powN - 1) - (powNQ1 - 1))) % MOD + MOD) % MOD;
            }else if(q <= -1 * (n - 1)){
                long pow = myPow(n);
                res = ((pow - 1) * (pow - 1) % MOD + MOD) % MOD;
            }
            System.out.println(res);
        }
    }


    private static long myPow(long n){
        if(n == 0){return 1L;}
        long res = 2L;
        long A = 2L;
        n--;
        while(n > 0){
            if((n & 1) == 1){
                res = res * A % MOD;
            }
            A = A * A % MOD;
            n >>= 1;
        }
        return res;
    }
}