Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define lp(i,a,n) for(int i=a;i<=n;++i)
- #define lpd(i,a,n) for(int i=a;i>=n;--i)
- #define mem(a,b) memset(a,b,sizeof a)
- #define all(v) v.begin(),v.end()
- #define println(a) cout <<(a) <<endl
- #define sz(x) ((int)(x).size())
- #define readi(x) scanf("%d",&x)
- #define read2i(x,y) scanf("%d%d",&x,&y)
- #define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
- #define mod 1000000007
- #define eps 1e-8
- #define infi 1000000000
- #define infll 1000000000000000000ll
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> pii;
- typedef pair<ll,ll> pll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<ll> vll;
- typedef set<int> si;
- typedef map<int,int> mii;
- const int N = 500002, M = 1000003;
- int n,a,b,c,row[N],col[N];
- ll aPow[N],bPow[N],ans;
- ll fact[N],revFact[N];
- ll poly1[N],poly2[N],poly3[N];
- ll power(ll x, ll y){
- if(!y) return 1;
- ll sq = power(x, y/2);
- sq = sq * sq % M;
- if(y&1) sq = sq * x % M;
- return sq;
- }
- void init(){
- aPow[0] = bPow[0] = 1;
- lp(i,1,n){
- aPow[i] = aPow[i-1] * a % M;
- bPow[i] = bPow[i-1] * b % M;
- }
- fact[0] = revFact[0] = 1;
- lp(i,1,N-1){
- fact[i] = fact[i-1] * i % M;
- revFact[i] = power(fact[i], M-2);
- }
- }
- ll comb(ll x, ll y){
- if(x < y) return 0;
- return fact[x] * revFact[y] % M * revFact[x - y] % M;
- }
- typedef complex<double> CD;
- const double PI = acos(-1.);
- inline void dft(CD out[], int n, int oper) {
- for (int i = 1, j = 0; i < n - 1; i++) {
- for (int s = n; j ^= s >>= 1, ~j & s;);
- if (i < j)
- swap(out[i], out[j]);
- }
- for (int d = 0; (1 << d) < n; d++) {
- int m = 1 << d, m2 = m << 1;
- double theta = PI / m * oper;
- CD u0 = CD(cos(theta), sin(theta));
- for (int i = 0; i < n; i += m2) {
- CD u = 1.;
- for (int j = i; j < i + m; j++) {
- CD p1 = out[j] + u * out[j + m];
- CD p2 = out[j] - u * out[j + m];
- out[j] = p1;
- out[j + m] = p2;
- u *= u0;
- }
- }
- }
- }
- inline void conv(ll a[], ll b[], ll c[], int n) {
- while (n & (n - 1))
- n++;
- n *= 2;
- CD _a[n + 5], _b[n + 5], _c[n + 5];
- for (int i = 0; i < n; i++) {
- _a[i] = CD(a[i], 0);
- _b[i] = CD(b[i], 0);
- }
- dft(_a, n, 1);
- dft(_b, n, 1);
- for (int i = 0; i < n; i++)
- _c[i] = _a[i] * _b[i];
- dft(_c, n, -1);
- for (int i = 0; i < n; i++)
- c[i] = (ll) (_c[i].real() / n + .5);
- }
- void addC(){
- lp(i,1,n-2){
- poly1[i] = aPow[i] * revFact[i] % M;
- poly2[i] = bPow[i] * revFact[i] % M;
- }
- lpd(i,n,2){
- ans = (ans + c * aPow[n-i] % M) % M;
- if(i < n)
- ans = (ans + c * bPow[n-i] % M) % M;
- }
- conv(poly1, poly2, poly3, n-1);
- lp(i,2,2*(n-1)){
- poly3[i] = poly3[i] % M * fact[i] % M;
- ans = (ans + c * poly3[i] % M) % M;
- }
- }
- int main(){
- cin >>n >>a >>b >>c;
- lp(i,1,n) readi(col[i]);
- lp(i,1,n) readi(row[i]);
- init();
- lp(i,2,n){
- ans = (ans + row[i] * aPow[n - i] % M * bPow[n - 1] % M * comb(n-i + n-2, n-2) % M) % M;
- ans = (ans + col[i] * aPow[n - 1] % M * bPow[n - i] % M * comb(n-i + n-2, n-2) % M) % M;
- }
- addC();
- cout <<ans;
- }
- /*
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement