Submission #831035

#	Time	Username	Problem	Language	Result	Execution time	Memory
831035		rainboy	Party (INOI20_party)	C11	100 / 100	303 ms	400 KiB

Main

#include <stdio.h>

#define L	60	/* L = ceil(log2(10^18)) */
#define MD	1000000007
#define V2	500000004

int min(int a, int b) { return a < b ? a : b; }

long long power(long long a, long long k) {
	long long p = 1;

	if (k < 0)
		return 0;
	while (k) {
		if (k & 1)
			p = p * a % MD;
		a = a * a % MD;
		k >>= 1;
	}
	return p;
}

int inv(int a) {
	return a == 1 ? 1 : (long long) inv(a - MD % a) * (MD / a + 1) % MD;
}

int pp[L + 2], qq[L + 2], rr[L + 2], ss[L + 2], tt[L + 2];

void init() {
	int i;

	pp[0] = qq[0] = 1, rr[0] = 2, ss[0] = V2;
	for (i = 1; i <= L + 1; i++) {
		pp[i] = pp[i - 1] * 2 % MD;
		qq[i] = (long long) qq[i - 1] * V2 % MD;
		rr[i] = (long long) rr[i - 1] * rr[i - 1] % MD;
		ss[i] = (long long) ss[i - 1] * ss[i - 1] % MD;
	}
}

long long count(int d) {
	return (1LL << (d + 1) / 2) + (1LL << (d + 2) / 2) - 2;
}

int p2count(int d) {
	return (long long) rr[(d + 1) / 2] * rr[(d + 2) / 2] % MD * qq[2] % MD;
}

int q2count(int d) {
	return (long long) ss[(d + 1) / 2] * ss[(d + 2) / 2] % MD * pp[2] % MD;
}

int main() {
	int q;

	init();
	scanf("%d", &q);
	while (q--) {
		long long n, m, wl, wm, wr;
		int l, y, y_, d, p, p_, ans;

		scanf("%lld", &n);
		l = 0;
		while ((1LL << l + 2) - 1 <= n)
			l++;
		m = n - ((1LL << l + 1) - 1);
		p = power(2, n);
		tt[0] = 1;
		for (y = 0; y <= l; y++)
			tt[y + 1] = (long long) tt[y] * ((m & 1LL << y) == 0 ? 1 : ss[y]) % MD;
		ans = 0;
		for (y = 0; y <= l + 1; y++)
			for (d = 0; d <= y + l; d++) {
				p_ = (long long) p * q2count(d + min(d, l - y)) % MD;
				if (d > y)
					p_ = (long long) p_ * ss[d - y + 1] % MD * 2 % MD * p2count((d - y) * 2) % MD;
				if (y + d > l) {
					y_ = (y + l - d + 2) / 2;
					wl = m >> l + 1 - y_ << y - y_;
					wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
					wr = (y <= l ? 1LL << y : m) - wl - wm;
					ans = (ans + ((long long) p_ * ss[l + 1 - y_] % MD - 1) * (wl % MD)) % MD;
					ans = (ans + ((long long) p_ * tt[l + 1 - y_] % MD - 1) * (wm % MD)) % MD;
					ans = (ans + (p_ - 1) * (wr % MD)) % MD;
				} else
					ans = (ans + (p_ - 1) * ((1LL << y) % MD)) % MD;
			}
		ans = (long long) ans * inv(p - 1) % MD;
		if (ans < 0)
			ans += MD;
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:64:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   64 |   while ((1LL << l + 2) - 1 <= n)
      |                  ~~^~~
Main.c:66:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   66 |   m = n - ((1LL << l + 1) - 1);
      |                    ~~^~~
Main.c:79:22: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   79 |      wl = m >> l + 1 - y_ << y - y_;
      |                ~~~~~~^~~~
Main.c:79:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   79 |      wl = m >> l + 1 - y_ << y - y_;
      |                              ~~^~~~
Main.c:80:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   80 |      wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
      |                            ~~^~~~
Main.c:80:55: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   80 |      wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
      |                                                 ~~~~~~^~~~
Main.c:80:61: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   80 |      wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
      |                                         ~~~~~~~~~~~~~~~~~~~~^~~
Main.c:57:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:62:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%lld", &n);
      |   ^~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 33 / 33
• Subtask 4: 37 / 37