1151_DIV 2: C. 나 자 르 에 대한 문제 (수학)

제목 대의: 홀수 와 짝수 두 개의 무한대 집합 이 있 습 니 다. 홀수 집합 은 {1, 3, 5, 7...} 이 고 짝수 집합 은 {2, 4, 6, 8...} 입 니 다. 홀수 에서 1 개 를 뽑 은 다음 짝수 에서 2 개 를 뽑 고 홀수 에서 4 개 를 뽑 습 니 다.............................................................。 -- 새로운 집합 에서 l 부터 r 까지 의 숫자 합 은 얼마 인가.(대 1e9 + 7 모드)
방법: 사실은 수학 시 뮬 레이 션 문제 입 니 다. 분명히 답 은 접두사 와 성질 을 만족 시 킵 니 다. 우 리 는 solve (r) - solve (l - 1) 로 답 을 얻 을 수 있 습 니 다.어떻게 solve (x) 를 풀 수 있 습 니까?제목 의 뜻 에 따라 배가 하면 된다. 집합 에서 연속 적 인 홀수 블록 과 연속 적 인 짝수 블록 으로 구성 되 기 때문에 블록의 길 이 는 2 의 幂 次 이다. 우 리 는 홀수 블록 과 짝수 블록 을 분리 하여 인접 한 홀수 블록 이나 짝수 블록의 길이 가 4 배의 차 이 를 발견 할 수 있다.우 리 는 첫 번 째 조각 부터 옮 겨 다 니 기 시 작 했 는데, 몇 번 째 조각의 총 길이 가 x 를 초과 할 수 있 는 것 을 본 후에 화 해 를 구하 면 된다.화 해 를 구하 면 모든 블록 이 연속 적 인 등차 수열 이기 때문에 이 블록의 첫 번 째 항목 이 얼마 인지 계산 한 다음 에 블록의 길이 와 첫 번 째 항목 의 값 에 따라 공식 O (1) 를 이용 하여 계산 할 수 있 고 마지막 블록 (마지막 블록 이 전부 포함 되 지 않 았 기 때문에) 을 특수 하 게 계산 할 수 있 습 니 다. 여 기 는 여러 가지 모델 링 을 주의해 야 합 니 다. 그렇지 않 으 면 넘 쳐 서 모델 링 을 할 수 있 는 곳 에서 모두 모델 링 을 해 야 합 니 다.복잡 도 log (n)
코드:

#include
using namespace std;
const long long mod = 1e9 + 7;
long long l,r;
long long fpow(long long a,long long b) {
	long long res = 1;
	while(b) {
		if(b & 1) res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
long long solve(long long l) {
	long long odd = 0,even = 0; //          /   ，            
	long long cnt = 0,i;		//cnt     ，i       
	long long ans = 0;			//   
	for(i = 1,cnt = 1,even = 0,odd = 0; i <= l; i += i,cnt++){
		if(cnt % 2 == 0) {
			long long tmp = 2 * (fpow(4,even) - 1) / 3;
			//a1 = 2 + 2 * tmp;
			ans = ((ans + ((2 + 2 * tmp) % mod) * (i % mod)) % mod + ((i - 1) % mod * (i % mod)) % mod ) % mod;
			even++;
		}
		else {
			long long tmp = 1 * (fpow(4,odd) - 1) / 3;
			//a1 = 1 + (tmp) * 2
			ans = ((ans + ((1 + 2 * tmp) % mod) * (i % mod)) % mod  + ((i - 1) % mod * (i % mod)) % mod) % mod; 
			odd++;
		}
		l -= i;
	}	
	if(l) {
		if(cnt % 2 == 0) {
				long long tmp = 2 * (fpow(4,even) - 1) / 3;
				//a1 = 2 + 2 * tmp;
				ans = ((ans + ((2 + 2 * tmp) % mod) * (l % mod)) % mod  + ((l - 1) % mod * (l % mod)) % mod ) % mod;
				even++;
		}
		else {
				long long tmp = 1 * (fpow(4,odd) - 1) / 3;
				//a1 = 1 + (tmp) * 2
				ans = ((ans + ((1 + 2 * tmp) % mod) * (l % mod)) % mod  + ((l - 1) % mod * (l % mod)) % mod ) % mod; 
				odd++;
			}
	}
	return ans % mod;
}
int main() {
	scanf("%lld%lld",&l,&r);
	printf("%lld
",(solve(r) + mod - solve(l - 1)) % mod);
	return 0;
}