제출 #19004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19004		kriii	로봇 (kriii4_F)	C++14	100 / 100	0 ms	1088 KiB

F

#include <stdio.h>

const long long mod = 1000000007;

long long pow(long long a, long long p)
{
	a %= mod;
	p = (p % (mod - 1) + mod - 1) % (mod - 1);
	long long r = 1;
	while (p){
		if (p & 1) r = r * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return r;
}

struct complex{
	complex(){
		x = y = 0;
	}
	complex(long long x_, long long y_){
		x = (x_ % mod + mod) % mod;
		y = (y_ % mod + mod) % mod;
	}
	long long x,y;

	complex operator *(complex t){
		return complex(x*t.x-y*t.y,x*t.y+y*t.x);
	}
	complex operator *(long long a){
		return complex(x*a,y*a);
	}
	complex operator +(complex t){
		return complex(x+t.x,y+t.y);
	}
	complex operator -(complex t){
		return complex(x-t.x,y-t.y);
	}
};

complex sum(complex u, long long n)
{
	complex v(1,0),w,p,q; long long z=1,r=n;
	while (n){
		if (n & 1){
			q = (q + p * z) * u + w;
			p = p * u + v;
		}
		w = (w + v * z) * u + w;
		v = v * u + v;
		u = u * u;
		n /= 2;
		z *= 2;
	}

	return p * r - q;
}

int main()
{
	long long n,l,m,r;
	scanf ("%lld %lld %lld %lld",&n,&l,&m,&r);

	long long inv = pow(l+m+r,-1);
	complex u(m,l-r),v(m,r-l);
	u = u * inv;
	v = v * inv;
	complex ans = sum(u,n) + sum(v,n) - complex(n,0);

	printf ("%lld\n",ans.x);

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 96 / 96