# 112上學期第一次社內賽題本

## 四則運算
前情提要：甲魚社長在高二時想要先修選修數甲下冊的微積分，但是她似乎不滿足於上面的習題，所以想要用程式節省她的運算功夫。

正文開始。

講到四則運算，我們肯定從幼稚園就開始接觸這項基本技術了，例如我們知道 $1+1=2$，而 $2-3=-1$，至於乘除法，$3 \times 2=6$，而 $4 \div 2=2$；而且，我們也已經知道，運算時必須遵守先乘除後加減的邏輯，括號要先算，其中，對於除法，我們甚至可以寫成分數形式，例如：$(5-3)\div 2 \times 3 = \dfrac{5-3}{2} \times 3 = 3$，而乘法則具有分配律，例如：$ab+ac+ad=a(b+c+d)$。瞭解了這些基本的原理後，我們就可以進行下一個簡單練習，也就是微分 $\dfrac{d}{dx} f(x)$ 與積分 $\int_{a}^{b}f(x)dx$。

首先是微分：微分其實不是一個名詞，而是一個動詞，這項數學動作就是求導函數，而導函數的定義則是「差商的極限」，數學表達式為：導函數 $f'(x)=\displaystyle\lim_{h\to 0} \dfrac{f(x+h)-f(x)}{h}$，也可以寫成導數 $f'(x_0)=\displaystyle\lim_{x\to x_0} \dfrac{f(x)-f(x_0)}{x-x_0}$，順帶一提，$f'(a)$稱為$f(x)$在$x=a$ 的「導數」，也就是 $x=a$ 處的切線斜率，言歸正傳，有了定義，我們便能推導冪函數 $x^n$ 的微分公式，但推導過程等到高三再考就好了，我們玩程式的，先記結論，即 $\dfrac{d}{dx} x^n=nx^{n-1}$，如果冪函數前面有乘上一個常數 $k$，則 $\dfrac{d}{dx}kx^n=k\times nx^{n-1}$，而最終的結果，如果有一連串冪函數相加，即多項式函數，則微分就是各自微分後再相加，也就是：$\dfrac{d}{dx} (a_n x^n+a_{n-1} x^{n-1}+\dots +a_1 x + a_0)=na_n x^{n-1}+(n-1)a_{n-1} x^{n-2}+\dots +a_1$。（請注意：$\dfrac{d}{dx}c = 0$）

接下來是積分：積分沒有公式，但是偉大的萊布尼茲成功證明了（高三也會教你證明）積分就是微分的反運算，也就是說，對於冪函數的積分（不定積分）：$\int{kx^n}dx=\dfrac{k}{n+1}x^{n+1}$，你可以檢查看看，$\dfrac{d}{dx} \dfrac{k}{n+1}x^{n+1} = (n+1)\times \dfrac{k}{n+1}x^{n}= kx^n$。所以對於多項式函數的積分，

$\int{(a_n x^n+a_{n-1} x^{n-1}+\dots +a_1 x + a_0)dx}=\dfrac{a_n}{n+1}x^{n+1}+\dfrac{a_{n-1}}{n}x^{n}+\dots +\dfrac{a_1}{2}x^{2}+a_0 x+c$

今天，你們的任務就是要幫助社長甲魚大人進行一些微積分的運算，題目會給你一個多項式函數 $p(x)$，請計算它的微分 $a(x)$ 與不定積分 $A(x)$。

### 輸入
第一行會先輸入一個 $N$，代表這個多項式函數 $p(x)$ 的最高次數（degree）

接下來會有 $N+1$ 行輸入，每行依序有「係數」$a_i$，與「次方數」$i$（$0\le i\le N$），中間以一個空格隔開。而次方數採取降冪排列，即第一行為 $n$ 次項，第二行為 $n-1$ 次項，以此類推。測資在計算不定積分後各項係數皆為整數。

$0\le N\le 100$
$0\le a_i \le 7656$

子任務 1（20%）：$N=0$
子任務 2（30%）：輸入形式如冪函數
子任務 3（50%）：無其他限制

### 輸出
請仿照輸入的方式輸出。

第一行請輸出："a(x)="（不含引號）

接下來的 $N-1$ 行，請於每一行輸出「係數」與「次方數」，中間以一個空格隔開。

第 $N+1$ 行請輸出："A(x)="（不含引號）

接下來的 $N+1$ 行，請於每一行輸出「係數」與「次方數」，中間以一個空格隔開。而未定的常數請以一個小寫 $c$ 表示

## 救救牛奶糖
寒假即將到來，電算社也迎來寒假最重要的一個活動——寒訓。今天，斜槓達人牛奶糖因為它的生活太無聊，又懶得做社課要用的簡報，因此跑去加入寒訓的行政組，希望以此為沒時間做簡報的藉口。而進入行政組後的牛奶糖，馬上面臨到一項艱鉅的任務——訂房間。訂房間牽扯到許多數學運算、排列組合相關的問題，而對於數學一竅不通的牛奶糖頓時無法解決，因此，想請你幫助笨笨的牛奶糖找出此三元一次方程式的所有解，和總共需要的金額，方便他選擇心目中的最佳方案。（房型只有三種，分別是兩人房、三人房、四人房）

### 輸入
第一行輸入一個正整數 $N$，$N$ 代表參加寒訓的總人數。
第二行有三個整數 $x$、$y$、$z$，其中 $x$ 代表兩人房的價錢，$y$ 代表三人房的價錢，$z$ 代表四人房的價錢。

$2 \le N \le 100$
$10^3\le x \le y \le z \le 10^5$

### 輸出
輸出4個正整數 $a$、$b$、$c$、$d$，並以空白分隔，其中 $a$ 代表訂 $a$ 間兩人房，$b$ 代表訂 $b$ 間三人房，$c$ 代表訂 $c$ 間四人房，$d$ 代表花費的金額。 $a$ 由小到大輸出，若 $a$ 相同，則 $b$ 由小到大輸出。

## 和乘數
小明是一位熱愛數學的小學生，有一天他定義了一種「和乘數」，定義如下：
若 $A$ 為和乘數，則存在兩個以上的正整數 $x_1, x_2, \cdots, x_n$ $(n\ge 2)$，使得

$x_1+x_2+\cdots +x_n=A$
$x_1, x_2, \cdots, x_n$ 的最小公倍數為 $A$

由於小明只是個小學生，對這種數的性質完全沒有想法
小明給你了一些數，請幫幫他找出所有的和乘數的和

### 輸入
第一行包含一個整數 $N$，代表有 $N$ 個數要請你判斷它是不是和乘數
接下來 $N$ 行，每行都包含一個正整數 $A$

$1\le N\le 100$
$2\le A\le 10^9$

子任務 1（20%）：$A\le 3000$
子任務 2（80%）：無其他限制

### 輸出
請輸出一個整數，代表所有和乘數的和

## 好大的黑板
現在在黑板上有一個整數 $A$，你可以做以下操作任意次：

選一個在黑板上的數 $x$
將 $x$ 擦掉，並寫上 $\lfloor \frac{x}{2} \rfloor$ 和 $\lceil \frac{x}{2} \rceil$

請找到在經過任意次操作後，黑板上所有數字的乘積最大值為多少

由於數字很大，請輸出答案除以 $998244353$ 後的餘數

註：$\lfloor a \rfloor$ 代表小於等於 $a$ 的最大整數，$\lceil a \rceil$ 代表大於等於 $a$ 的最小整數

### 輸入
第一行包含一個正整數 $A$，代表最開始在黑板上的數

$1\le A\le 10^{18}$

子任務 1（10%）：$A\le 100$
子任務 2（20%）：$A\le 10^5$
子任務 3（30%）：$A\le 10^9$
子任務 4（40%）：無其他限制

### 輸出
請輸出經過任意次操作後，黑板上的所有數乘積最大值除以 $998244353$ 的餘數