c434. 連續正整數(Natural_Number)
Tags :
Accepted rate : 36人/44人 ( 82% ) [非即時]
評分方式:
Strictly

最近更新 : 2024-02-29 19:48

Content

  我們說 $\color{black}{f(n)}$ 表示在一個有正整數 $\color{black}{1\sim n}$ 的集合內,擁有三個或三個以上連續正整數的子集合個數。像是 $\color{black}{n=5}$ 就有 $\color{black}{\{1,2,3\},\{2,3,4\},\{3,4,5\},\{1,2,3,5\},\{1,3,4,5\},\{1,2,3,4\},\{2,3,4,5\},\{1,2,3,4,5\}}$ 八種子集合,故 $\color{black}{f(5)=8}$。

Input

首行有一個正整數 $\color{black}{T}$,代表接下來有 $\color{black}{T}$ 組測資。接下來 $\color{black}{T}$ 行,只有一個正整數 $\color{black}{N}$ 代表這筆測資要你輸出的是 $\color{black}{f(N)}$。

Output

因為答案可能很大,所以對於每筆測資,請輸出一個整數代表 $\color{black}{f(N)}$ 模 $\color{black}{10^9+7}$ 的餘數於一行。

 

Sample Input #1
3
3
4
5
Sample Output #1
1
3
8
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (18%): 1.0s , <1K
不公開 測資點#1 (1%): 1.0s , <1K
不公開 測資點#2 (1%): 1.0s , <1K
不公開 測資點#3 (28%): 1.0s , <1K
不公開 測資點#4 (1%): 1.0s , <1K
不公開 測資點#5 (1%): 1.0s , <1K
不公開 測資點#6 (48%): 1.0s , <1K
不公開 測資點#7 (1%): 1.0s , <1K
不公開 測資點#8 (1%): 1.0s , <1K
Hint :

本題共有三個子題,每一子題可有多筆測試資料:
第一子題的測試資料 $\color{black}{N\leq 20}$,全部解出可獲 20 分;
第二子題的測試資料 $\color{black}{N\leq 1000}$,全部解出可獲 30 分;
第三子題的測試資料 $\color{black}{N\leq 10^6}$,全部解出可獲 50 分。

對於所有測資,$\color{black}{T\leq 10}$。

Tags:
出處:
板橋高中模擬賽2016年APMO初選 [管理者: baluteshih (波路特石) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
38869 k034006 (Sine Wu) c434
思路
104 2023-12-28 23:43