c878. 107北二5.議會質詢紀錄

題目 Problem

題目連結:https://zerojudge.tw/ShowProblem?problemid=c878

敘述 Description

根據民主政治的精神,政府單位有責任到民意代表所組成的會議中接受質詢與監督。某議會的議長在會期開始前就和政府單位進行下面的溝通:「我們議會希望被質詢的官員每一次都要出席。如果有兩次以上的請假紀錄,或是連續三次以上請代理的同仁來接受質詢的話,恐怕會造成雙方溝通上的緊張。」
請你寫一隻程式來統計一下,當官員需要被質詢 N 次的情況下,有多少種官員出席紀錄可以保持府會的和諧關係。另外,由於答案可能會非常大,請回傳除以 100000007 之後的餘數。

輸入 Input

測試資料只有一行,只有一個正整數 N,代表某一官員所要接受質詢的次數。N 的範圍從 2 到 120000。

輸出 Output

輸出資料為一個數值,為能夠保持府會和諧的出席紀錄組合數量。

範例輸入 Sample Input

1
2
3
4
5
範例輸入一:
2

範例輸入二:
3

範例輸出 Sample Output

1
2
3
4
5
範例輸出一:
8

範例輸出二:
19

提示 Hint

範例輸入一:
八種組合列在下面:
[出席,出席][出席,代理][代理,出席]
[請假,出席][請假,代理][出席,請假]
[代理,請假][代理,代理]

範例輸入二:
會破壞行政單位和議會關係的紀錄組合:
[假假出][假出假][出假假][假假代][假代假]
[代假假][假假假][代代代]

題解 Solution

根據英國(?)研究顯示,看到 $Mod$ 題目,有 $87%$ 都是DP題
想了半天還是沒有想到DP轉移式
後來跟FB社團裡的大神求助後
才知道兩次以上的請假紀錄或是連續三次以上請代理需要分開寫

定義一下$dp[i][j][k]$
$i$是天數
$j$是請假天數
$k$是連續代理次數

所以可以這樣寫
$dp[120001][2][3]$

轉移式就可以這樣寫:
0次請假 且 0次連續代理 = 前一天的(0次請假 且 0次連續代理 + 0次請假 且 1次連續代理 + 0次請假 且 2次連續代理)

$$dp[i][0][0]=dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2]$$

0次請假 且 1次連續代理 = 前一天的(0次請假 且 0次連續代理)

$$dp[i][0][1]=dp[i-1][0][0]$$

0次請假 且 2次連續代理 = 前一天的(0次請假 且 1次連續代理)

$$dp[i][0][2]=dp[i-1][0][1]$$

1次請假 且 0次連續代理 = 前一天的(0次請假 且 0次連續代理 + 0次請假 且 1次連續代理 + 0次請假 且 2次連續代理 + 1次請假 且 0次連續代理 + 1次請假 且 1次連續代理 + 1次請假 且 2次連續代理)

這裡的會有0次請假,因為之前沒有請假,代表他今天可以請假
這裡的會有1次請假,代表他今天出席

$$dp[i][1][0]=dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2]+dp[i-1][1][0]+dp[i-1][1][1]+dp[i-1][1][2]$$

1次請假 且 1次連續代理 = 前一天的(1次請假 且 0次連續代理)

$$dp[i][1][1]=dp[i-1][1][0]$$

1次請假 且 2次連續代理 = 前一天的(1次請假 且 1次連續代理)

$$dp[i][1][2]=dp[i-1][1][1]$$

程式碼 Accepted Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main(){
long long int dp[120002][2][3]={0};
dp[1][0][0]=1;
dp[1][0][1]=1;
dp[1][1][0]=1;
for (int i = 2; i < 120002; ++i){
dp[i][0][0]=(dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2])%100000007;
dp[i][0][1]=dp[i-1][0][0]%100000007;
dp[i][0][2]=dp[i-1][0][1]%100000007;
dp[i][1][0]=(dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2]+dp[i-1][1][0]+dp[i-1][1][1]+dp[i-1][1][2])%100000007;
dp[i][1][1]=(dp[i-1][1][0])%100000007;
dp[i][1][2]=(dp[i-1][1][1])%100000007;
}
int N;
cin>>N;
cout<<(dp[N][0][0]+dp[N][0][1]+dp[N][0][2]+dp[N][1][0]+dp[N][1][1]+dp[N][1][2])%100000007<<'\n';
return 0;
}

後記 Afterword

這題 Sine Wu 也分享了他的解法
之後來研究,研究完會貼出來分享
台南一中OJ有個類題 https://toj.tfcis.org/oj/pro/416/
測試資料高達 $N=10^9$
這種就只能寫矩陣快速冪
可以把$O(N)$變成$O(\log N)$


c878. 107北二5.議會質詢紀錄
https://blog.yangjerry.tw/2018/11/22/zj-c878/
作者
Jerry Yang
發布於
2018年11月22日
許可協議