PROBLEM LINK:
Practice
Contest
Author: Pratik
Tester: Arjun
Editorialist: Pratik
DIFFICULTY:
HARD.
PREREQUISITES:
Bit-Manupulation, popcounts.
PROBLEM:
Popcount p(x)p(x) of a number xx is defined as the number of set bits in xx.
For any sequence s(s1,s2,s3…sk)s(s1,s2,s3…sk) of size kk, let f(s)f(s) be defined as the sum of popcount of all its elements. More formally,
f(s)=∑i=1kp(si)f(s)=∑i=1kp(si)
.
A positive integer N is given . N can be split into several positive integers that can be represented as sequence u(u1,u2,u3…um)u(u1,u2,u3…um) of arbitrary size mm. Formally,
∑i=1mui=n∑i=1mui=n
where ui>0ui>0 . You need to find ∑f(u)∑f(u) over all such valid sequences. See samples to understand better.
Since the answer can be large, print its modulo 1000000007(109+7).
EXPLANATION:
In the third test case, N=4 , which can be represented as a sum of these distinct sequences,
u=[1,1,1,1],thus,f(u)=4u=[1,1,1,1],thus,f(u)=4
u=[1,2,1],thus,f(u)=3u=[1,2,1],thus,f(u)=3
u=[1,1,2],thus,f(u)=3u=[1,1,2],thus,f(u)=3
u=[2,1,1],thus,f(u)=3u=[2,1,1],thus,f(u)=3
u=[2,2],thus,f(u)=2u=[2,2],thus,f(u)=2
u=[1,3],thus,f(u)=3u=[1,3],thus,f(u)=3
u=[3,1],thus,f(u)=3u=[3,1],thus,f(u)=3
u=[4],thus,f(u)=1u=[4],thus,f(u)=1
So , ??f(u)f(u)=2222 .
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define int ll
#define ld long double
const int MAX = 5010;
const int mod = 1e9+7;
int pre[MAX];
int power(int x , int y){
if(y == 0)
return 1;
int val = power(x,y/2)%mod;
if((y%2) == 0){
return (valval)%mod;
}
return (((valval)%mod)*x)%mod;
}
int setBits(int n){
int ans = 0;
while(n>0){
if((n&1) == 1)
ans++;
n=n/2;
}
return ans%mod;
}
void solve()
{
int n;
cin>>n;
// for(int n=1;n<500;n++){
// cout<<n<<" ";
int ans = 0;
for(int i=1;i<=n;i++){
int idx = n-i;
int mul =0;
if(idx == 1)
mul = 2;
else if(idx == 0)
mul = 1;
else mul = ((idx+3)power(2,idx-2)) %mod;
// cout<<i<<" "<<mul<<endl;
ans += (mulsetBits(i))%mod;
ans%=mod;
}
cout<<ans<<endl;
// }
}
int32_t main() {
#ifndef ONLINE_JUDGE
freopen(“InputA.txt”, “r”, stdin);
// freopen(“error.txt”, “w”, stderr);
freopen(“OutputA.txt”, “w”, stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int test=1;
cin>>test;
int tc=1;
while(test–)
{
// cout<<“Case #”<<tc<<": ";
tc++;
solve();
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mod 1000000007
#define vi vector
#define pp pair<ll, ll>
#define ff first
#define ss second
#define all(n) n.begin(),n.end()
using namespace std;
void init()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
}
int main()
{
init();
vector<ll> v1(5001), v2(5001), sum(5001);
v1[1] = 1;
v1[2] = 3;
sum[1] = 1;
sum[2] = 4;
v2[1] = 1;
v2[2] = sum[1] + v1[1] + __builtin_popcountll(2);
for(ll i=3; i<=5000; i++) {
v1[i] = (sum[i-1] + v2[i-1] + __builtin_popcountll(i))%mod;
sum[i] = sum[i-1] + v1[i];
v2[i] = (v2[i-1]*2 + __builtin_popcountll(i))%mod;
}
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
cout<<v1[n]%mod<<"\n";
}
return 0;
}