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