Submission #831007

#	Time	Username	Problem	Language	Result	Execution time	Memory
831007		rainboy	Party (INOI20_party)	C11	100 / 100	1391 ms	428 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() {
	static long long nn[2023];
	static int answer[2023];
	int q, cnt;

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

		scanf("%lld", &n);
		h = 0;
		while (h < cnt && nn[h] != n)
			h++;
		if (h < cnt) {
			printf("%d\n", answer[h]);
			continue;
		}
		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 (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);
		nn[cnt] = n, answer[cnt] = ans, cnt++;
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:54:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   54 |   while ((1LL << l + 2) - 1 <= n)
      |                  ~~^~~
Main.c:56:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   56 |   m = n - ((1LL << l + 1) - 1);
      |                    ~~^~~
Main.c:62:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   62 |      k += (1LL << min(d - y, l) + 1) - 1 - count(d - y + min(d - y, l));
      |                   ~~~~~~~~~~~~~~^~~
Main.c:65:22: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   65 |      wl = m >> l + 1 - y_ << y - y_;
      |                ~~~~~~^~~~
Main.c:65:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   65 |      wl = m >> l + 1 - y_ << y - y_;
      |                              ~~^~~~
Main.c:66:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   66 |      wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
      |                            ~~^~~~
Main.c:66:55: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   66 |      wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
      |                                                 ~~~~~~^~~~
Main.c:66:61: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   66 |      wm = (y <= l ? 1LL << y - y_ : m & (1LL << l + 1 - y_) - 1);
      |                                         ~~~~~~~~~~~~~~~~~~~~^~~
Main.c:68:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   68 |      ans = (ans + (power(2, n - (k + (1LL << l + 1 - y_))) - 1)
      |                                              ~~~~~~^~~~
Main.c:70:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   70 |      ans = (ans + (power(2, n - (k + (m & (1LL << l + 1 - y_) - 1))) - 1)
      |                                                   ~~~~~~^~~~
Main.c:70:63: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   70 |      ans = (ans + (power(2, n - (k + (m & (1LL << l + 1 - y_) - 1))) - 1)
      |                                           ~~~~~~~~~~~~~~~~~~~~^~~
Main.c:34:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:41:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%lld", &n);
      |   ^~~~~~~~~~~~~~~~~

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