PROBLEM LINK:
Author: Sobhagya singh dewal
Tester: Sankalp Gupta
DIFFICULTY:
MEDIUM
PREREQUISITES:
Maths, Binomial theorem
PROBLEM:
f_{n}=\ \sum_{r=1}^{\infty} \frac{(r)^{n}}{2^{r}}
QUICK EXPLANATION:
We just need to transform this to another form using some basic maths, so replace r by (r+1), start limit from 0, and apply binomial expansion on (r+1)^n
EXPLANATION:
f_{n}=\sum_{r=1}^{\infty} \frac{r^{n}}{2^{r}}
f_{n}=\frac{1}{2} \sum_{r=0}^{\infty} \frac{(r+1)^{n}}{2^{r}}
f_{n}=\frac{1}{2} \sum_{r=0}^{\infty} \frac{1}{2^{r}} \sum_{i=0}^{n} \binom{n}{i} * r^{i}
f_{n}=\frac{1}{2} \sum_{i=0}^{n} \binom{n}{i} * \sum_{r=0}^{\infty} \frac{r^{i}}{2^{r}}
f_{n}=\frac{1}{2} \sum_{i=0}^{n} \binom{n}{i} * \sum_{r=1}^{\infty} \frac{r^{i}}{2^{r}}+\frac{1}{2}
We can write
f_{n}=\sum_{r=1}^{\infty} \frac{r^{n}}{2^{r}}
then
f_{n}=\frac{1}{2} \sum_{i=0}^{n} \binom{n}{i} * f_{i}+\frac{1}{2},
so
f_{n}=\sum_{i=0}^{n-1} \binom{n}{i} * f_{i}+1,
using this d p formula we can get the answer in O\left(n^{2}\right).
SOLUTIONS:
Setter’s Solution
#include<bits/stdc++.h>
#define int long long int
int mod=1e9+7;
using namespace std;
vector<int>fac,inv,ifac;
void pre()
{
fac.push_back(1);fac.push_back(1);
ifac.push_back(1);ifac.push_back(1);
inv.push_back(0);inv.push_back(1);
for(int i=2;i<=6000;i++)
{
fac.push_back(fac.back()*i%mod);
inv.push_back(mod-(inv[mod%i]*(mod/i)%mod));
ifac.push_back(ifac.back()*inv.back()%mod);
}
}
int ncr(int n,int r)
{
if(n<r || n<=0)
return 0;
if(r==0)
return 1;
return (((fac[n]*ifac[r])%mod)*ifac[n-r])%mod;
}
int32_t main()
{
pre();
int dp[6000];
dp[0]=1;
for(int i=1;i<=6000;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
dp[i]=(dp[i]+ncr(i,j)*dp[j])%mod;
}
}
int tt;
cin>>tt;
while(tt--)
{
int nn;
cin>>nn;
cout<<dp[nn]<<"\n";
}
}
Tester's Solution
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vvl vector<vll>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii >
#define vpll vector<pll >
#define ff first
#define ss second
#define PI 3.14159265358979323846
#define fastio ios_base::sync_with_stdio(false) , cin.tie(NULL) ,cout.tie(NULL)
ll power(ll a,ll b){ ll res=1; while(b>0){ if(b&1) res*=a; a*=a; b>>=1;} return res; }
ll power(ll a,ll b,ll m){ ll res=1; while(b>0){ if(b&1) res=(res*a)%m; a=(a*a)%m; b>>=1;} return res;}
bool pp(int a,int b) {return a>b;}
using namespace std;
ll m=1e9+7;
ll dp[6002],fac[6002],inv[6002];
ll mul(ll a,ll b){
return (a*b)%m;
}
ll bino(ll n,ll k){
ll res=fac[n];
res = mul(res,inv[k]);
res = mul(res,inv[n-k]);
return res;
}
void solve(){
fac[1]=fac[0]=1;
for(ll i=2;i<=6000;i++)
fac[i]=mul(fac[i-1],i);
for(ll i=0;i<=6000;i++){
inv[i]=power(fac[i],m-2,m);
}
//cout<<"ff\n";
dp[1]=dp[0]=2;
for(ll i=2;i<=6000;i++){
ll s=0;
for(ll j=1;j<=i;j++){
s = (s+mul(bino(i,j),dp[i-j]))%m;
}
dp[i]=s;
//cout<<"y\n";
}
}
int main()
{
fastio;
int t;
cin>>t;
assert(t<=1e5&&t>0);
solve();
while(t--){
ll n;
cin>>n;
assert(n>0&&n<=6000);
// solve(n);
cout<<dp[n]<<"\n";
}
return 0;
}