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 位多放一個在右盤，最少需要放置的砝碼個數。則有： dp[i][0]＝min(dp[i＋1][0]＋num[i],dp[i＋1][1]＋4－num[i]); $$dp[i][0]＝min(dp[i＋1][0]＋num[i],dp[i＋1][1]＋4－num[i]);$$ dp[i][1]＝min(dp[i＋1][1]＋num[i]＋1,dp[i＋1][1]＋3－num[i]); $$dp[i][1]＝min(dp[i＋1][1]＋num[i]＋1,dp[i＋1][1]＋3－num[i]);$$ 對于方案數，只要在動態規劃的過程中順便處理一下就可以了。然后代碼參考了Po爺，蒟蒻高精度巨TM炸。。。