MATHL - Editorial

PROBLEM LINKS:

Practice
Contest

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

DIFFICULTY:

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. :slight_smile:

8 Likes

WHY MY CODE IS GIVING TLE IN THIS PROBLEM
HERE IS LINK.PLEASE ANYONE ANSWER.I HAVE DONE THE SAME WAY AS EXPLAINED IN EDITORIAL
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;
}

}

Use \n instead of endl

2 Likes

Use ‘\n’ instead of endl

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)
tle link: https://www.codechef.com/viewsolution/26687278
AC link: https://www.codechef.com/viewsolution/26687267

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

https://codeforces.com/blog/entry/43780#targetText=But%20there%20is%20a%20huge,a%20flush%2C%20which%20actually%20unnecessary.

please go and read once .

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 .