Submission #831003

#	Time	Username	Problem	Language	Result	Execution time	Memory
831003		rainboy	Party (INOI20_party)	C11	40 / 100	3076 ms	304 KiB

Main

#include <stdio.h>

#define MD	1000000007

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

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

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

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 main() {
	int q;

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

		scanf("%lld", &n);
		if (n == 1) {
			printf("0\n");
			continue;
		}
		l = 0;
		while ((1LL << l + 2) - 1 <= n)
			l++;
		m = n - ((1LL << l + 1) - 1);
		ans = 0;
		for (y = 0; y <= l + 1; y++)
			for (d = 0; d <= y + l + 1; d++) {
				k = count(d + min(d, l - y));
				if (d > y)
					k += (1LL << min(d - y, l) + 1) - 1 - count(d - y + min(d - y, l));
				if (m == 0 && 0) {
					if (y <= l)
						ans = (ans + (power(2, n - k) - 1) * ((1LL << y) % MD)) % MD;
				} else {
					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 + (power(2, n - (k + (1LL << l + 1 - y_))) - 1)
								* (wl % MD)) % MD;
						ans = (ans + (power(2, n - (k + (m & (1LL << l + 1 - y_) - 1))) - 1)
								* (wm % MD)) % MD;
						ans = (ans + (power(2, n - k) - 1)
								* (wr % MD)) % MD;
					} else
						ans = (ans + (power(2, n - k) - 1) * ((1LL << y) % MD)) % MD;
				}
			}
		ans = (long long) ans * inv((power(2, n) - 1 + MD) % MD) % MD;
		if (ans < 0)
			ans += MD;
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:43:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   43 |   while ((1LL << l + 2) - 1 <= n)
      |                  ~~^~~
Main.c:45:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   45 |   m = n - ((1LL << l + 1) - 1);
      |                    ~~^~~
Main.c:51:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   51 |      k += (1LL << min(d - y, l) + 1) - 1 - count(d - y + min(d - y, l));
      |                   ~~~~~~~~~~~~~~^~~
Main.c:58:23: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   58 |       wl = m >> l + 1 - y_ << y - y_;
      |                 ~~~~~~^~~~
Main.c:58:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   58 |       wl = m >> l + 1 - y_ << y - y_;
      |                               ~~^~~~
Main.c:59:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   59 |       wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
      |                             ~~^~~~
Main.c:59:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   59 |       wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
      |                                                  ~~~~~~^~~~
Main.c:59:62: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   59 |       wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
      |                                          ~~~~~~~~~~~~~~~~~~~~^~~
Main.c:61:53: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   61 |       ans = (ans + (power(2, n - (k + (1LL << l + 1 - y_))) - 1)
      |                                               ~~~~~~^~~~
Main.c:63:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   63 |       ans = (ans + (power(2, n - (k + (m & (1LL << l + 1 - y_) - 1))) - 1)
      |                                                    ~~~~~~^~~~
Main.c:63:64: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   63 |       ans = (ans + (power(2, n - (k + (m & (1LL << l + 1 - y_) - 1))) - 1)
      |                                            ~~~~~~~~~~~~~~~~~~~~^~~
Main.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:37:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%lld", &n);
      |   ^~~~~~~~~~~~~~~~~

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