Advertisement
Guest User

Untitled

a guest
Feb 19th, 2018
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.69 KB | None | 0 0
  1.  
  2.  
  3. #include<set>
  4. #include<map>
  5. #include <unordered_map>
  6. #include <unordered_set>
  7. #include<list>
  8. #include<iomanip>
  9. #include<cmath>
  10. #include<string>
  11. #include<vector>
  12. #include<queue>
  13. #include<stack>
  14. #include<complex>
  15. #include<sstream>
  16. #include<iostream>
  17. #include<fstream>
  18. #include<algorithm>
  19. #include<numeric>
  20. #include<utility>
  21. #include<functional>
  22. #include<stdio.h>
  23. #include<assert.h>
  24. #include<memory.h>
  25. #include<bitset>
  26. #include<math.h>
  27. #include <strings.h>
  28.  
  29.  
  30.  
  31.  
  32. #define f first
  33. #define s second
  34. #define pb push_back
  35. #define sz(a) (int)(a).size()
  36. #define lp(i,a,n) for(int (i)=(a);(i)<=(int)(n);(i)++)
  37. #define lpd(i,n,a) for(int (i)=(n);(i)>=(a);--(i))
  38. #define mp make_pair
  39. #define clr(a,b) memset(a,b,sizeof a)
  40. #define all(v) (v).begin(),(v).end()
  41. #define mod 1000000007
  42. #define eps 1e-6
  43. #define infi 1000000002
  44. #define infll 4000000000000000005ll
  45. #define MX 1000000
  46. #define X real()
  47. #define Y imag()
  48. #define polar(r,t) ((r)* exp(point(0,(t))))
  49. #define length(a) hypot( (a).X , (a).Y )
  50. #define angle(a) atan2( (a).Y , (a).X )
  51. #define vec(a,b) ( (b) - (a) )
  52. #define dot(a,b) (conj(a)*(b)).X
  53. #define cross(a,b) (conj(a)*(b)).Y
  54. #define lengthsqr(a) dot(a,a)
  55. #define reflect(V,M) (conj((V)/(M)) * (M))
  56. #define normalize(a) ((a)/length(a))
  57. #define ccw(a,b,c) cross(vec(a,b) , vec(a,c)) > -eps
  58. #define cosRule(a,b,c) (acos(((a)*(a)+(b)*(b)-(c)*(c))/(2*(a)*(b))))
  59. #define cosDot(a,b) (acos(dot(a,b)/length(a)/length(b)))
  60. #define EQ(a,b) (fabs((a) - (b)) <= eps) /* equal to */
  61. #define NE(a,b) (fabs((a) - (b)) > eps) /* not equal to */
  62. #define LT(a,b) ((a) < (b) - eps) /* less than */
  63. #define GT(a,b) ((a) > (b) + eps) /* greater than */
  64. #define LE(a,b) ((a) <= (b) + eps) /* less than or equal to */
  65. #define GE(a,b) ((a) >= (b) - eps) /* greater than or equal to */
  66. #define mod1 100050001
  67. #define mod2 100030001
  68. #define base1 37
  69. #define base2 31
  70. #define que priority_queue<pair<int,int>, vector<pair<int,int>> , greater<pair<int,int> > >
  71. #define rotate(v,t) ((v)*exp(point(0,t)))
  72. #define rotateabout(v,t,a) (rotate(vec(a,v),t)+(a))
  73. #define PI atan(1)*4
  74.  
  75.  
  76. using namespace std;
  77. typedef long long ll;
  78. typedef pair<int, int> pii;
  79. typedef pair<double,double> pdd;
  80. typedef pair<ll, ll> pll;
  81. typedef vector<int> vi;
  82. typedef vector<ll> vll;
  83. typedef vector<vi> vvi;
  84. typedef set<int> si;
  85. typedef map<int, int> mii;
  86. typedef map<ll, ll> mll;
  87. typedef unordered_map<ll, ll> umll;
  88. typedef complex<long double> point;
  89. //typedef pair<point, point> line;
  90. typedef pair<double , point> Circle;
  91.  
  92.  
  93.  
  94. const int N = 100002;
  95.  
  96. int n,m,a[N],b[N];
  97.  
  98. ll dp[N], inv;
  99.  
  100. ll power(ll b,ll p) {
  101. if(!p) return 1;
  102. ll ret = power(b, p>>1);
  103. return ret*ret%mod*(p&1?b:1)%mod;
  104. }
  105.  
  106.  
  107. ll solve(int i) {
  108.  
  109.  
  110. if(i == n+1) return 0;
  111. if(b[i] && a[i] && b[i] > a[i]) return 0;
  112. if(b[i] && a[i] && a[i] > b[i]) return 1;
  113.  
  114.  
  115. if(~dp[i]) return dp[i];
  116.  
  117. ll &ret = dp[i];
  118.  
  119.  
  120. if(!a[i] && !b[i])
  121. ret = (((1ll*(m-1ll)*m/2ll)%mod) + solve(i+1)*m%mod)%mod*inv%mod*inv%mod;
  122. else if(!a[i])
  123. ret = ((m-b[i]) + solve(i+1))%mod*inv%mod;
  124. else if(!b[i])
  125. ret = ((a[i]-1) + solve(i+1))%mod*inv*mod;
  126. else
  127. ret = solve(i+1);
  128.  
  129. return ret;
  130. }
  131.  
  132. int main(){
  133. scanf("%d%d",&n,&m);
  134. lp(i, 1, n) scanf("%d",&a[i]);
  135. lp(i, 1, n) scanf("%d",&b[i]);
  136.  
  137. inv = power(m, mod-2);
  138. clr(dp, -1);
  139. printf("%lld\n", solve(1));
  140.  
  141.  
  142. return 0;
  143. }
  144.  
  145. /*
  146.  
  147.  
  148. 7
  149. 10
  150. 5 7 1
  151. 5 6 2
  152. 7 7 2
  153. 6 7 2
  154. 5 5 1
  155. 3 6 2
  156. 1 3 2
  157. 5 6 1
  158. 1 3 1
  159. 6 7 1
  160.  
  161.  
  162.  
  163. */
  164. //freopen("output.txt","w",stdout);
  165. //freopen("input.txt","r",stdin);
  166. //ios::sync_with_stdio(0);cin.tie(0);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement