Submission #949730

#	Time	Username	Problem	Language	Result	Execution time	Memory
949730		KiaRez	Party (INOI20_party)	C++17	63 / 100	3027 ms	15264 KiB

Main

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 18;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

ll q, n, cur, dp[125][125][125], pd[125][125], num[125][125];

ll f(ll m) {
	if(m==0) return 124;
	ll numc=0, now=1, ans=0;
	while(now < m) {
		now*=(2ll); now++; numc++;
	}
	if(now == m) return numc;
	int c1, c2;
	//fuck(m);
	if(m >= (1ll<<numc)+(1ll<<(numc-1ll))) {
		//cout<<(1ll<<(numc))-1<<' '<<(m-(1ll<<numc))<<endl;
		c1=f((1ll<<(numc))-1ll), c2=f(m-(1ll<<(numc)));
	} else {
		//cout<<m-(1ll<<(numc-1))<<' '<<((1ll<<(numc-1)) - 1)<<endl;
		c1=f(m-(1ll<<(numc-1ll))), c2=f((1ll<<(numc-1ll)) - 1ll);
	}
	int i = cur; cur++;
	for(int j=0; j<=60; j++) {
		if(j == 0) num[i][0] = 1;
		else num[i][j] = MOD(num[c1][j-1] + num[c2][j-1]);
		if(j==0) {
			pd[i][j] = MOD(2ll * (pd[c1][0] + 1) * (pd[c2][0] + 1) - 1);
		} else {
			pd[i][j] = MOD((pd[c1][j-1]+1)*(pd[c2][j-1]+1) - 1);
		}
		if(j == 0) {
			for(int k=60; k>0; k--) {
			dp[i][j][k] = MOD((pd[c1][k-1]+1)*(pd[c2][k-1]+1) - (pd[c1][k]+1)*(pd[c2][k]+1));
			}
		} else {
		ll tot1 = (j==0 ? 0 : num[c1][j-1]), tot2 = (j==0 ? 0 : num[c2][j-1]);
		for(int k=2*60; k>0; k--) {
			ll res = 0;
			
			res = MOD(dp[c1][j-1][k] * (j>=k ? (pd[c2][0]+1)*2ll : pd[c2][k-j-1] + 1));
			res = MOD(res + dp[c2][j-1][k] * (j>=k ? (pd[c1][0]+1)*2ll : pd[c1][k-j-1] + 1));

			if(k>=j) res = MOD(res + tot1 * (k==j ? (pd[c2][0]+1) : (pd[c2][k-j-1] - pd[c2][k-j])));
			if(k>=j) res = MOD(res + tot2 * (k==j ? (pd[c1][0]+1) : (pd[c1][k-j-1] - pd[c1][k-j])));
			dp[i][j][k] = res;

			tot1 = MOD(tot1 + dp[c1][j-1][k]);
			tot2 = MOD(tot2 + dp[c2][j-1][k]);
		}
		}
	}
	return i;
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	pd[0][0] = 1;
	num[0][0] = 1;
	for(int i=1; i<=60; i++) {
	int c1=i-1, c2=i-1;
	for(int j=0; j<=i; j++) {
		if(j == 0) num[i][0] = 1;
		else num[i][j] = MOD(num[c1][j-1] + num[c2][j-1]);
		if(j==0) {
			pd[i][j] = MOD(2ll * (pd[c1][0] + 1) * (pd[c2][0] + 1) - 1);
		} else {
			pd[i][j] = MOD((pd[c1][j-1]+1)*(pd[c2][j-1]+1) - 1);
		}
		if(j == 0) {
			for(int k=i; k>0; k--) {
			dp[i][j][k] = MOD((pd[c1][k-1]+1)*(pd[c2][k-1]+1) - (pd[c1][k]+1)*(pd[c2][k]+1));
			}
		} else {
		ll tot1 = (j==0 ? 0 : num[c1][j-1]), tot2 = (j==0 ? 0 : num[c2][j-1]);
		for(int k=2*i; k>0; k--) {
			ll res = 0;
			
			res = MOD(dp[c1][j-1][k] * (j>=k ? (pd[c2][0]+1)*2ll : pd[c2][k-j-1] + 1));
			res = MOD(res + dp[c2][j-1][k] * (j>=k ? (pd[c1][0]+1)*2ll : pd[c1][k-j-1] + 1));

			if(k>=j) res = MOD(res + tot1 * (k==j ? (pd[c2][0]+1) : (pd[c2][k-j-1] - pd[c2][k-j])));
			if(k>=j) res = MOD(res + tot2 * (k==j ? (pd[c1][0]+1) : (pd[c1][k-j-1] - pd[c1][k-j])));
			dp[i][j][k] = res;

			tot1 = MOD(tot1 + dp[c1][j-1][k]);
			tot2 = MOD(tot2 + dp[c2][j-1][k]);
		}
		}
	}
	}

	cin>>q;
	while(q--) {
		ll numc=0, now=1, ans=0;
		cin>>n;
		cur = 61;
		ll wh = f(n);
		for(int i=0; i<=60; i++) {
		for(ll j=1; j<=2*60; j++) {
			ans = MOD(ans + j * dp[wh][i][j]);
		}
		}
		for(int i=61; i<=cur; i++) for(int j=0; j<=60; j++) num[i][j]=pd[i][j]=0, fill(dp[i][j], dp[i][j]+2*60, 0);
		//fuck(ans);
		cout<<MOD(ans * poww(poww(2, n)-1, Mod-2))<<endl;
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'll f(ll)':
Main.cpp:47:20: warning: unused variable 'ans' [-Wunused-variable]
   47 |  ll numc=0, now=1, ans=0;
      |                    ^~~
Main.cpp: In function 'int main()':
Main.cpp:134:6: warning: unused variable 'numc' [-Wunused-variable]
  134 |   ll numc=0, now=1, ans=0;
      |      ^~~~
Main.cpp:134:14: warning: unused variable 'now' [-Wunused-variable]
  134 |   ll numc=0, now=1, ans=0;
      |              ^~~

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