題目描述

HSY 帶著 Yfengzi 一起去吃麥肯士吃垃圾食品。

麥肯士有種單點餐品（漢堡薯條雞翅之類的）。每次選擇一種或者以上的餐點，且每種餐點不多于一個的話，可以認為是購買套餐。購買一個套餐，價格是單品價格的總和（真黑啊），但是可以送一個玩具，HSY 最喜歡麥肯士的玩具了。不過有規定即使多次購買同一種套餐（也就是里面的餐點的種類和數量完全一樣）也只能獲得一個玩具。

HSY 為了收集盡可能多的玩具，需要買盡可能多種的套餐。請問如果想要收集到最多的玩具數量，至少要花掉多少錢？由于 HSY 是個土豪，所以我們需要輸出答案在模998244353意義下的結果。

輸入

第一行一個正整數n表示餐點數量。
第二行n個非負整數ai表示各個餐點的價格。

輸出

輸出一行一個整數表示答案在模998244353意義下的結果。

樣例輸入

5 1 2 3 4 5

樣例輸出

240

提示

對于全部數據1≤n≤107,0＜ai＜998244353。

思路

就是推公式，推出答案是輸入數據和乘以2^(n-1)，特別注意快速冪函數名不能取pow！！！我在這里瘋狂wa

代碼

#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const ll mo=998244353; const int inf=0x3f3f3f3f; ll ans,n,x; ll q_pow(ll a,ll b) {ll tmp=1;while(b){if(b&1) tmp=tmp*a%mo;a=a*a%mo;b/=2;}return tmp%mo; } int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=0;i<n;i++){cin>>x;ans=(ans+x)%mo;}ll tmp=q_pow(2,n-1);cout<<ans*tmp%mo;return 0; }

總結

以上是生活随笔為你收集整理的HSY 点餐（数论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。