P9532 [YsOI2023] 前缀和

题目背景

Ysuperman 模板测试的试机题。

小心立秋，小心秋丽。

题目描述

立秋有一个长度为 $n$ 的数组 $a$ ，所有数字都是正整数，并且除了其中第一个数字以外其它数字都等于前面所有数字的和。

例如，数组 $[1,1,2,4,8,16]$ 就有可能是立秋有的一个数组，因为除了第一个数字 $1$ ，后面的每个数字都是前面数字的和，例如：

第二个数字 $1=1$ 。
第三个数字 $2=1+1$ 。
第四个数字 $4=1+1+2$ 。
第五个数字 $8=1+1+2+4$ 。
第六个数字 $16=1+1+2+4+8$ 。

现在立秋告诉了秋丽数字 $x$ 存在于这个数组中，秋丽希望知道 $a_n$ 最小会是多少，或者说整个数组最后一个数字最小有多少。

输入格式

本题有多组测试数据。

输入第一行一个数字 $T$ 表示测试数据组数。

接下来 $T$ 行每行两个正整数 $n,x$ 。

输出格式

输出共 $T$ 行，分别表示每组测试数据的答案。

对于某组数据 $n,x$ ，输出一行一个正整数表示可能的最小的 $a_n$ 。

输入输出样例 #1

输入 #1

输出 #1

2
2
4

输入输出样例 #2

输入 #2

输出 #2

2
2
4

输入输出样例 #3

输入 #3

输出 #3

6
6
12

输入输出样例 #4

输入 #4

输出 #4

6
6
12

说明/提示

样例 1 解释

第一组数据只有唯一可能的数组 $[2,2]$ ，所以答案为 $2$ ；
第二组数据有两种可能的数组，分别是 $[2,2,4]$ 和 $[1,1,2]$ ，所以答案为 $2$ ；
第三组数据有两种可能的数组，分别是 $[2,2,4,8]$ 和 $[1,1,2,4]$ ，所以答案为 $4$ 。

样例 2 解释

第一组数据只有唯一可能的数组 $[1,1,2]$ ，所以答案为 $2$ ；
第二组数据有两种可能的数组 $[1,1,2]$ 和 $[2,2,4]$ ，所以答案为 $2$ ；
第三组数据有两种可能的数组 $[2,2,4]$ 和 $[4,4,8]$ ，所以答案为 $4$ 。

数据范围

对于前 $30\%$ 的数据，满足 $x$ 不能被 $2$ 整除，或者说 $2$ 不是 $x$ 的一个因数，或者说 $x$ 是奇数。

另有 $30\%$ 的数据，满足 $x$ 可以被 $2^{n-2}$ 整除，或者说 $2^{n-2}$ 是 $x$ 的一个因数。

另有 $20\%$ 的数据，满足 $x\le 1000$ ，可以证明在这个数据范围下答案可以使用一个 int 类型变量存储。

对于 $100\%$ 的数据，满足 $1\le T\le 10^4$ ， $2\le n\le 20$ ， $1\le x\le 10^9$ 。

求解前缀和数组

    int n, x;
    cin >> n >> x;
    vector<i64> arry(n + 1, 0);
    vector<i64> prefix(n + 1, 0);
    arry[0] = 1;
    arry[1] = 1;
    for (int i = 1; i < n + 1; i++)
    {
        prefix[i] = prefix[i - 1] + arry[i - 1];
        arry[i] = prefix[i];
    }
    prefix[0] = 1;

AC代码

// @file    :P_9532_YsOI_2023_前缀和.cpp
// @brief   :just for fun
//@author  :Luo Xinrui
//@version :V2.0.0
//@date    :2025-05-27
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
#define lowbit(x) = ((x) & -(x))
#define rep_0(a, b, c) for (int a = b; a < c; a++)
#define rep_1(a, b, c) for (int a = b; a <= c; a++)
#define per(a, b, c) for (int a = b; a >= c; a--)
using namespace std;

void solve()
{
    int n, x;
    cin >> n >> x;
    vector<i64> arry(n + 1, 0);
    vector<i64> prefix(n + 1, 0);
    arry[0] = 1;
    arry[1] = 1;
    for (int i = 1; i < n + 1; i++)
    {
        prefix[i] = prefix[i - 1] + arry[i - 1];
        arry[i] = prefix[i];
    }
    prefix[0] = 1;
    if (x % 2 != 0)
    {
        cout << x * prefix[n - 1] << endl;
    }
    else if (x % 2 == 0)
    {
        int jishu = 1;
        i64 temp = x;
        while (temp % 2 == 0)
        {
            if (jishu != 1)
            {
                jishu -= 1;
            }
            temp = temp / 2;
            jishu += 2;
        }
        if (jishu >= n)
        {
            cout << x * prefix[0] << endl;
        }
        else
        {
            cout << temp * prefix[n - 1] << endl;
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }

    return 0;
}

洛谷题解 | # P9532 [YsOI2023] 前缀和#