2022绍兴市初中组编程比赛-----问题 B: 最大乘积(product) 题解

题目

问题 B: 最大乘积(product)

题目描述

黑板上有一个正整数 n。你可以做任意次如下的操作：选择一个黑板上的整数 x，把 x 擦掉，然后写上 floor(x/2) 和 ceil(x/2)。
你要最大化黑板上所有数的乘积，输出这个乘积对 998244353 取模后的结果。
提示：对于某个实数 k，floor(k) 表示不大于k的最大整数，ceil(k) 表示不小于k的最小整数。

输入

一行一个整数n。

输出

一行一个整数，表示答案对 998244353 取模后的结果。

样例输入

3

样例输出

3

提示

样例输入2
15
样例输出2
192
样例1：不进行任何操作。
样例2：擦掉 15，写上 7 和 8；
擦掉 7，写上 3 和 4；
擦掉 4，写上 2 和 2；
擦掉 8，写上 4 和 4；
黑板上的数有 3,2,2,4,4，乘积对 998244353 取模后的结果为 192。
【数据范围约定】
对于10%的数据，n≤5；
对于20%的数据，n≤20；
对于40%的数据，n≤50；
对于60%的数据，n≤10^3；
对于80%的数据，n≤10^6；
对于90%的数据，n≤10^9；
对于所有数据，1≤n≤10^18。

题解

首先分到2或3就可以不用分了，不然答案会很小。
另外数据很大，建议用map存储。

#include <bits/stdc++.h>
using namespace std;
long long n;
map<long long,long long> m; 
long long check(long long k){
    if (k <= 4){
        return k;
    }
    if(m[k]){
        return m[k];
    }
    m[k] = check(k/2)*check(k-k/2)%998244353;
    return m[k];
} 
int main() {
    scanf("%lld",&n);
    printf("%lld\n",check(n));
    return 0;
}