Submission #1037856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037856		javotaz	LIS (INOI20_lis)	C++17	0 / 100	1 ms	348 KiB

Main

// In the Name of Allah

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")

typedef long long ll;

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
#define int long long

const int N = 62;

const int mod = 1'000'000'000 + 7;
ll n, dp[N];

int bp(int x, ll y) {
	if (y < 2) return y? x : 1;
	ll tmp = bp(x, y / 2);
	tmp = tmp * tmp % mod;
	return (y & 1)? tmp * x % mod : tmp;
}

void solve() {
	cin >> n;
	ll ans = 0;
	int k = 0;
	for (int i = 0; i < 61; i++)
		if ((1ll << i) - 1 == n)
			k = i;
	if (n != (1ll << k) - 1)
		exit(0);
	ll mk = bp(bp(2, n) - 1, mod - 2);
	for (int i = 0; i < k; i++) {
		vector<ll> v;
		v.pb(1);
		for (int j = 1; j < 2 * k; ++j) {
			ll cnt = (i + j < k)? (1ll << j) : 0;
			for (int z = i - 1; z >= 0; z--)
				if (j == (i - z))
					cnt++;
				else if (j > (i - z) && z + j - (i - z) < k)
					cnt += (1ll << (j - (i - z) - 1));
			if (!cnt)
				break;
			v.pb(cnt);
		}
		ll c = 1;
		for (int j = 1; j < v.size(); ++j) {
			c += v[j];
			dp[i] = (dp[i] + (bp(2, v[j]) - 1) * bp(2, n - c) % mod * j % mod * mk) % mod;
		}
		ans = (ans + dp[i] * ((1ll << i) % mod)) % mod;
	}
	cout << ans << '\n';
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:56:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int j = 1; j < v.size(); ++j) {
      |                   ~~^~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80