Guest User

Untitled

a guest
Jan 11th, 2015
446
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.84 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <string.h>
  5. #include <queue>
  6. #include <math.h>
  7. #include <cmath>
  8. #include <map>
  9. #include <set>
  10. #include <vector>
  11. #include <algorithm>
  12. #include <bitset>
  13. #include <ctype.h>
  14. #include <cassert>
  15. #include <stack>
  16. #include <fstream>
  17. #include <unordered_map>
  18. #include <ctime>
  19.  
  20. using namespace std;
  21.  
  22. #define snd second
  23. #define fst first
  24. #define mp make_pair
  25. #define ll long long
  26. #define ull unsigned long long
  27. #define ld long double
  28. #define pb push_back
  29. #define left _left
  30. #define right _right
  31.  
  32. const ld pi = 3.14159265359;
  33.  
  34. template < typename T > T abs(T x)
  35. {
  36.     return x > 0 ? x : -x;
  37. }
  38.  
  39. template < typename T > T sqr(T x)
  40. {
  41.     return x * x;
  42. }
  43.  
  44. const int maxn = 1000005;
  45. const ll mod = 1000000007;
  46.  
  47. char s[maxn];
  48. int sp = 0;
  49.  
  50. ll dp[205][205];
  51.  
  52. int nxt()
  53. {
  54.     while (s[sp] == ' ')
  55.     {
  56.         sp++;
  57.     }
  58.    
  59.     if (s[sp] == '?')
  60.     {
  61.         sp++;
  62.         return -1;
  63.     }
  64.    
  65.     int res = 0;
  66.     while (s[sp] != ' ')
  67.     {
  68.         res = res * 10 + s[sp] - '0';
  69.         sp++;
  70.     }
  71.    
  72.     return res;
  73. }
  74.  
  75.  
  76. ll fact[maxn], invFact[maxn];
  77. ll inv[maxn];
  78.  
  79. ll C(ll n, ll k)
  80. {
  81.     if (k > n)
  82.         return 0;
  83.     return (fact[n] * invFact[k] % mod) * invFact[n - k] % mod;
  84. }
  85.  
  86. ll F(ll n, ll order)
  87. {
  88.     n -= order - 1;
  89.     if (n < 0)
  90.         return 0;
  91.     return (C(2 * n + order - 1, n) * inv[n + order] % mod) * order % mod;
  92. }
  93.  
  94. ll get(ll currPos, ll prvPos, ll prvCoeff, ll prvOrder, ll order)
  95. {
  96.     ll res = 0;
  97.     for (int i = 0; i < 205; i++)
  98.     {
  99.         res += F(currPos - (prvPos - i), order) * dp[prvOrder][i] % mod;
  100.     }
  101.    
  102.     return (res % mod) * prvCoeff % mod;
  103. }
  104.  
  105. int main()
  106. {
  107.     //gen();
  108.     //freopen("a.in", "r", stdin);
  109.     //srand(time(NULL));
  110.    
  111.     inv[0] = 1;
  112.     inv[1] = 1;
  113.    
  114.     for (int i = 2; i < maxn; i++)
  115.     {
  116.         inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  117.     }
  118.        
  119.     fact[0] = invFact[0] = 1;
  120.    
  121.     for (int i = 1; i < maxn; i++)
  122.     {
  123.         fact[i] = (fact[i - 1] * i) % mod;
  124.         invFact[i] = (invFact[i - 1] * inv[i]) % mod;
  125.     }
  126.    
  127.     dp[1][0] = 1;
  128.     dp[2][1] = 1;
  129.     dp[2][0] = mod - 1;
  130.    
  131.     for (int i = 3; i < 205; i++)
  132.     {
  133.         for (int j = 0; j < 204; j++)
  134.             dp[i][j + 1] = (mod + dp[i - 1][j] - dp[i - 2][j]) % mod;
  135.     }
  136.    
  137.    
  138.     int n;
  139.     scanf("%d\n", &n);
  140.    
  141.     gets(s);
  142.     s[strlen(s)] = ' ';
  143.    
  144.     if (nxt() > 0)
  145.     {
  146.         cout << 0 << endl;
  147.         return 0;
  148.     }
  149.    
  150.     if (n == 1)
  151.     {
  152.         cout << 1 << endl;
  153.         return 0;
  154.     }
  155.    
  156.     int g = nxt();
  157.     if (g != -1 && g != 1)
  158.     {
  159.         cout << 0 << endl;
  160.         return 0;
  161.     }
  162.    
  163.    
  164.     ll prvPos = 1, prvCoeff = 1, prvOrder = 1;
  165.    
  166.    
  167.     for (int i = 2; i < n; i++)
  168.     {
  169.         int c = nxt();
  170.        
  171.         if (c == 0)
  172.         {
  173.             cout << 0 << endl;
  174.             return 0;
  175.         }
  176.        
  177.         if (c > 0)
  178.         {
  179.             ll res = get(i, prvPos, prvCoeff, prvOrder, c);
  180.            
  181.             prvPos = i;
  182.             prvCoeff = res;
  183.             prvOrder = c;
  184.         }
  185.     }
  186.    
  187.     cout << get(n, prvPos, prvCoeff, prvOrder, 1) << endl;
  188.    
  189.     return 0;
  190. }
Advertisement
Add Comment
Please, Sign In to add comment