Description
Mary準備舉辦一個聚會,她準備邀請很多的人參加她的聚會。并且她準備給每位來賓準備一些金子作為禮物。為了不傷及每個人的臉面,每個人獲得的金子必須相同。Mary將要用一個天平來稱量出金子。她有很多的砝碼,所有砝碼的質量都是4的冪。Mary將金子置于左邊并且將砝碼置于右盤或者兩個盤。她希望每次稱量都使用最少的砝碼。并且,他希望,每次都用不同的稱量方法稱出相同質量的金子。對于給定的質量n,Mary希望知道最少需要用多少個砝碼可以完成稱量,并且想知道用這么多個砝碼一共有多少種方式進行稱量。 Input
輸入文件僅包含一個整數,表示Mary希望給每個人的金子的質量。(1<=n<=10^1000) Output
輸出文件僅包含一個整數,表示一共可能的稱量方式對10^9的模。 Sample Input 166
Sample Output 3
樣例解釋
一共有三種方式稱量出166。166=64+64+16+16+4+1+1。166=256-64-16-16+4+1+1。166=256-64-16-4-4-1-1。
解題方法: 我們首先考慮把 n 轉換成一個四進制數。我們記轉換完的數有 m 位,第 i 位(從低到高)的值為 num[i]。我們發現對于第 i 位要想滿足條件只有兩種放置方法,第一種是在天平的右盤放 num[i]個 4 i 的砝碼,第二種是在天平的右盤放 1 個 4 i+ 1 的砝碼,在天平的左盤放 4-num[i]個 4 i的砝碼。因此我們可以考慮用 DP 解決,定義狀態 dp[i][j]表示第 i 到 m 位已經處理完,dp[i][0]表示第 i 位不多放一個在右盤,dp[i][1]表示在第 i 位多放一個在右盤,最少需要放置的砝碼個數。則有:
新聞熱點
疑難解答