# MATHL - Editorial

Setter- Raghav Bansal
Tester- Jatin Nagpal
Editorialist- Raghav Bansal

Easy

# PRE-REQUISITES:

Observation,Basic-Math

# PROBLEM:

Find the value of f(n) mod 1000000007.
Such That f(n)=1^{n}*2^{n-1}*3^{n-2} ------- n^{1}

# EXPLANATION:

Key to AC- After solving the function.

f(n)=n!*(n-1)!*(n-2)!--------1!.

We can store the products of facorials for all N upto 1000000 in O(N) and answer each query in O(1).

# SOLUTION

Setter
``````#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
#define mod 1000000007
int fac[1000005],an[1000005];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
fac[0]=1,an[0]=1;
f(i,1,1000003)
{
fac[i]=(fac[i-1]*i)%mod;
an[i]=(an[i-1]*fac[i])%mod;
}
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
cout<<an[n]<<'\n';
}
return 0;
}
``````

Time Complexity=O(N)
Space Complexity=O(N)

Feel free to Share your approach. Suggestions are welcomed as always had been.

8 Likes

WHY MY CODE IS GIVING TLE IN THIS PROBLEM
https://www.codechef.com/viewsolution/26674555

What is wrong with this approach?

#include
#include
#define ll unsigned long long int
#include
using namespace std;

ll power(ll a,ll b)
{
if(b==1 || a==1)
return a;
else if(b%2==0)
return ((power(a,b/2)%1000000007)(power(a,b/2)%1000000007))%1000000007;
else if(b%2==1)
return (a
(power(a,(b-1)/2)%1000000007)*(power(a,(b-1)/2)%1000000007))%1000000007;
}

main()
{

``````ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll a[n]={0};
ll s=1,p=n;
for(ll i=0;i<n;i++)
{
a[i]=power(s,p);
//	cout<<a[i]<<endl;
a[i]=a[i]%1000000007;
s++;p--;

}
ll ans=1;
for(ll i=0;i<n;i++)
{
ans*=a[i];
//	cout<<i+1<<" "<<a[i]<<endl;
ans=ans%1000000007;
}
cout<<ans<<endl;
}
``````

}

2 Likes

1 Like

Whats wrong with endl

I have never faced problem even with n^18 cases

1 Like

endl flushes the output buffer whereas ‘\n’ doesnt.

I used the same approach but instead used unordered_maps, also used “\n” instead of endl
but still passing only 1 subtask and the other shows TLE. Please tell where am I going wrong

here is my code: https://www.codechef.com/viewsolution/26681873

You are calculating products of factorials for each test case everytime. So time complexity for each test case is O(n).

they will calculated only once as i am storing them in maps instead of an array and then directly using them further when needed

Even after using “\n” i am getting tle
for ac we have to use both “\n” and ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

1 Like

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

int main() {

``````ios_base::sync_with_stdio(false);cin.tie(NULL);

long int fact=1;

long int ans[1000001];     ans[1] = 1;

for(int i=2;i<=1000001;i++)
{
fact=(fact*i)%1000000007;
ans[i] = (ans[i-1]*fact)%1000000007;
}
``````

int t;cin>>t; while(t–)
{ long int n;cin>>n;

``````    cout<<ans[n]<<endl;

}
``````

return 0 ;
}

My complexity is O(n+T) still getting TLE , Is this joke or something. I dont think there exist a better approach than this.

ok I got my error, it was just that i wasn’t putting ios::sync stuff at the beginning. Now it’s working

Bro use ‘\n’ .endl is flushing the buffer for 10^6 cases

Is (ab)%m = ((a%m)(b%m))%m ?

You are saying that I got a wrong ans just because a stupid endl…What the hell!! I think i am using endl since four years never got TLE. Again surprised by codechef.

3 Likes
1 Like

yes

1. ( a + b) % c = ( ( a % c ) + ( b % c ) ) % c
2. ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c
3. ( a – b) % c = ( ( a % c ) – ( b % c ) ) % c
4 Likes

Thanks man really appreciated .