Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<set>
- #include<map>
- #include <unordered_map>
- #include <unordered_set>
- #include<list>
- #include<iomanip>
- #include<cmath>
- #include<string>
- #include<vector>
- #include<queue>
- #include<stack>
- #include<complex>
- #include<sstream>
- #include<iostream>
- #include<fstream>
- #include<algorithm>
- #include<numeric>
- #include<utility>
- #include<functional>
- #include<stdio.h>
- #include<assert.h>
- #include<memory.h>
- #include<bitset>
- #include<math.h>
- #include <strings.h>
- #define f first
- #define s second
- #define pb push_back
- #define sz(a) (int)(a).size()
- #define lp(i,a,n) for(int (i)=(a);(i)<=(int)(n);(i)++)
- #define lpd(i,n,a) for(int (i)=(n);(i)>=(a);--(i))
- #define mp make_pair
- #define clr(a,b) memset(a,b,sizeof a)
- #define all(v) (v).begin(),(v).end()
- #define mod 1000000007
- #define eps 1e-6
- #define infi 1000000002
- #define infll 4000000000000000005ll
- #define MX 1000000
- #define X real()
- #define Y imag()
- #define polar(r,t) ((r)* exp(point(0,(t))))
- #define length(a) hypot( (a).X , (a).Y )
- #define angle(a) atan2( (a).Y , (a).X )
- #define vec(a,b) ( (b) - (a) )
- #define dot(a,b) (conj(a)*(b)).X
- #define cross(a,b) (conj(a)*(b)).Y
- #define lengthsqr(a) dot(a,a)
- #define reflect(V,M) (conj((V)/(M)) * (M))
- #define normalize(a) ((a)/length(a))
- #define ccw(a,b,c) cross(vec(a,b) , vec(a,c)) > -eps
- #define cosRule(a,b,c) (acos(((a)*(a)+(b)*(b)-(c)*(c))/(2*(a)*(b))))
- #define cosDot(a,b) (acos(dot(a,b)/length(a)/length(b)))
- #define EQ(a,b) (fabs((a) - (b)) <= eps) /* equal to */
- #define NE(a,b) (fabs((a) - (b)) > eps) /* not equal to */
- #define LT(a,b) ((a) < (b) - eps) /* less than */
- #define GT(a,b) ((a) > (b) + eps) /* greater than */
- #define LE(a,b) ((a) <= (b) + eps) /* less than or equal to */
- #define GE(a,b) ((a) >= (b) - eps) /* greater than or equal to */
- #define mod1 100050001
- #define mod2 100030001
- #define base1 37
- #define base2 31
- #define que priority_queue<pair<int,int>, vector<pair<int,int>> , greater<pair<int,int> > >
- #define rotate(v,t) ((v)*exp(point(0,t)))
- #define rotateabout(v,t,a) (rotate(vec(a,v),t)+(a))
- #define PI atan(1)*4
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef pair<double,double> pdd;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef vector<ll> vll;
- typedef vector<vi> vvi;
- typedef set<int> si;
- typedef map<int, int> mii;
- typedef map<ll, ll> mll;
- typedef unordered_map<ll, ll> umll;
- typedef complex<long double> point;
- //typedef pair<point, point> line;
- typedef pair<double , point> Circle;
- const int N = 100002;
- int n,m,a[N],b[N];
- ll dp[N], inv;
- ll power(ll b,ll p) {
- if(!p) return 1;
- ll ret = power(b, p>>1);
- return ret*ret%mod*(p&1?b:1)%mod;
- }
- ll solve(int i) {
- if(i == n+1) return 0;
- if(b[i] && a[i] && b[i] > a[i]) return 0;
- if(b[i] && a[i] && a[i] > b[i]) return 1;
- if(~dp[i]) return dp[i];
- ll &ret = dp[i];
- if(!a[i] && !b[i])
- ret = (((1ll*(m-1ll)*m/2ll)%mod) + solve(i+1)*m%mod)%mod*inv%mod*inv%mod;
- else if(!a[i])
- ret = ((m-b[i]) + solve(i+1))%mod*inv%mod;
- else if(!b[i])
- ret = ((a[i]-1) + solve(i+1))%mod*inv*mod;
- else
- ret = solve(i+1);
- return ret;
- }
- int main(){
- scanf("%d%d",&n,&m);
- lp(i, 1, n) scanf("%d",&a[i]);
- lp(i, 1, n) scanf("%d",&b[i]);
- inv = power(m, mod-2);
- clr(dp, -1);
- printf("%lld\n", solve(1));
- return 0;
- }
- /*
- 7
- 10
- 5 7 1
- 5 6 2
- 7 7 2
- 6 7 2
- 5 5 1
- 3 6 2
- 1 3 2
- 5 6 1
- 1 3 1
- 6 7 1
- */
- //freopen("output.txt","w",stdout);
- //freopen("input.txt","r",stdin);
- //ios::sync_with_stdio(0);cin.tie(0);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement