Submission #830952

#	Time	Username	Problem	Language	Result	Execution time	Memory
830952		rainboy	Party (INOI20_party)	C11	30 / 100	2403 ms	568 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	200
#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;

	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--) {
		static int pp2[N + 1], dd[N + 1], qu[N], kk[N];
		long long n, k;
		int cnt, l, h, i, j, s, d, ans;

		scanf("%lld", &n);
		if ((n & n + 1) == 0) {
			l = 0;
			while (1LL << l + 1 <= n)
				l++;
			ans = 0;
			for (i = 0; i <= l; i++)
				for (d = 0; d <= l * 2; d++) {
					k = count(d + min(d, l - i));
					if (d > i)
						k += (1LL << min(d - i, l) + 1) - 1 - count(d - i + min(d - i, l));
					ans = (ans + (power(2, n - k) - 1) * ((1LL << i) % MD)) % MD;
				}
		} else {
			pp2[0] = 1;
			for (i = 1; i <= n; i++)
				pp2[i] = pp2[i - 1] * 2 % MD;
			ans = 0;
			for (s = 1; s <= n; s++) {
				for (i = 1; i <= n; i++)
					dd[i] = n;
				cnt = 0;
				dd[s] = 0, qu[cnt++] = s;
				for (h = 0; h < cnt; h++) {
					i = qu[h], d = dd[i] + 1;
					if ((j = i >> 1) > 0 && dd[j] > d)
						dd[j] = d, qu[cnt++] = j;
					if ((j = i << 1 | 0) <= n && dd[j] > d)
						dd[j] = d, qu[cnt++] = j;
					if ((j = i << 1 | 1) <= n && dd[j] > d)
						dd[j] = d, qu[cnt++] = j;
				}
				memset(kk, 0, n * sizeof *kk);
				for (i = 1; i <= n; i++)
					kk[dd[i]]++;
				for (d = 1; d < n; d++)
					kk[d] += kk[d - 1];
				for (d = 0; d < n; d++)
					ans = (ans + pp2[n - kk[d]] - 1) % MD;
			}
		}
		ans = (long long) ans * inv(power(2, n) - 1) % MD;
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:39:14: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   39 |   if ((n & n + 1) == 0) {
      |            ~~^~~
Main.c:41:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   41 |    while (1LL << l + 1 <= n)
      |                  ~~^~~
Main.c:48:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   48 |       k += (1LL << min(d - i, l) + 1) - 1 - count(d - i + min(d - i, l));
      |                    ~~~~~~~~~~~~~~^~~
Main.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:38:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%lld", &n);
      |   ^~~~~~~~~~~~~~~~~

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