daily pastebin goal
49%
SHARE
TWEET

cipari

a guest Jan 16th, 2018 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. #define MOD 1000000009
  6.  
  7. ll dp[100009];//the number of ways to construct this number
  8.  
  9. /*
  10. 0
  11. 1
  12. 10
  13. 11
  14. 100
  15. 101
  16. 110
  17. 111
  18. 1000
  19. 1001
  20. */
  21.  
  22. int main(){
  23.     ios::sync_with_stdio(false);
  24.     string s;
  25.     cin >> s >> s;
  26.     dp[0]=1;
  27.     int l = 1;
  28.     for(int i = 0;i<s.size();i++){
  29.         dp[l]=dp[l-1];
  30.         for(int j = 2;j<=3 and l-j>=0;j++){
  31.             if(s[i-j+1]=='1')dp[l]+=dp[l-j];
  32.         }
  33.         if(l>=4){
  34.             if(s[i]=='0' and s[i-1]=='0' and s[i-2]=='0' and s[i-3]=='1'){
  35.                 dp[l]+=dp[l-4];
  36.             }
  37.             if(s[i]=='1' and s[i-1]=='0' and s[i-2]=='0' and s[i-3]=='1'){
  38.                 dp[l]+=dp[l-4];
  39.             }
  40.         }
  41.         dp[l]%=MOD;
  42.         l++;
  43.     }
  44.     cout << dp[s.size()] << "\n";
  45.     string ans;
  46.     l=s.size()-1;
  47.     while(l>=0){
  48.         if(l>=3){
  49.             if(s[l]=='1' and s[l-1]=='0' and s[l-2]=='0' and s[l-3]=='1'){
  50.                 l-=4;
  51.                 ans+='9';
  52.                 continue;
  53.             }
  54.             if(s[l]=='0' and s[l-1]=='0' and s[l-2]=='0' and s[l-3]=='1'){
  55.                 l-=4;
  56.                 ans+='8';
  57.                 continue;
  58.             }
  59.         }
  60.         if(l>=2){
  61.             if(s[l]=='1' and s[l-1] == '1' and s[l-2]=='1'){
  62.                 l-=3;
  63.                 ans+='7';
  64.                 continue;
  65.             }
  66.             if(s[l]=='0' and s[l-1]=='1' and s[l-2]=='1'){
  67.                 l-=3;
  68.                 ans+='6';
  69.                 continue;
  70.             }
  71.             if(s[l]=='1' and s[l-1]=='0' and s[l-2]=='1'){
  72.                 l-=3;
  73.                 ans +='5';
  74.                 continue;
  75.             }
  76.             if(s[l]=='0' and s[l-1]=='0' and s[l-2]=='1'){
  77.                 l-=3;
  78.                 ans+='4';
  79.                 continue;
  80.             }
  81.         }
  82.         if(l>=1){
  83.             if(s[l]=='1' and s[l-1]=='1'){
  84.                 l-=2;
  85.                 ans += '3';
  86.                 continue;
  87.             }
  88.             if(s[l]=='0' and s[l-1]=='1'){
  89.                 l-=2;
  90.                 ans += '2';
  91.                 continue;
  92.             }
  93.         }
  94.         if(s[l]=='1'){
  95.             l--;
  96.             ans += '1';
  97.             continue;
  98.         }
  99.         else{
  100.             l--;
  101.             ans += '0';
  102.             continue;
  103.         }
  104.     }
  105.     reverse(ans.begin(),ans.end());
  106.     cout << ans;
  107.     return 0;
  108. }
RAW Paste Data
Top