MATHL - Editorial

editorial
, ,
42

yeah but that contest is yesterday night but you solved today ?? :thinking:

1 Like
43

Lol. Gonna include it in my temp as well.

44

@syntaxhacker bro u tried NMN from Yesterday?

45

no im reading that editorial now . im not that level though

47

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
#define mod 1000000007
typedef long long ll;

int main() {
int t;
cin>>t;
ll fact[MAX+1];
ll dp[MAX+1];
fact[0] = 1;
dp[0] = 1;
for(ll i=1;i<=MAX;i++) {
fact[i] = (i*fact[i-1])%mod;
dp[i] = (fact[i]*dp[i-1])%mod;
}

while(t--) {
    int n;
    cin>>n;
    cout<<dp[n]<<'\n';
}

}

whats wrong with this,it gives TLE

48

Use fast I/O (20 chars)

1 Like
49

Another way to think about it in terms of f(x):
f(x) = f(x-1)*(1*2*3...*x) = f(x-1)*(x!)

1 Like
50

Yeah ! And looks clean :slightly_smiling_face:

1 Like
51

It’s a nice observation though :smiley: can reduce my answer to one loop.

1 Like
52

what is the difference between power and powermod in your program?why i am getting wrong answer when i am using powermod in place of power function?

54

Actually that fucntion is wrongly wriiten. I have not called powermod function anywhere in the program.It is giving bug values for greater powers.Powermod function is using recursive logic to calculate power whereas power function doesn’t.
The function named power is running well. :smiley:

55

how to solve for this formula. I can’t derive this formula. i.e.

f(n)=n!∗(n−1)!∗(n−2)!−−−−−−−−1!.

56

what may be the reason for those bug value please tell me i think it is correct i have seen some tutorial of fermat theorem

57

For any n its recursive function can be written as
f(n)=f(n−1)∗(1∗2∗3∗4…∗n) with f(0)=1

1 Like
58

For those interested, this f(n) is simply the SuperFactorial function of n

Read more here : SuperFactorial

2 Likes
60

what’s wrong with this approach
t=int(input())
m=1000000007
for i in range(t):
n=int(input())
c=1
sqrt=int(n**(1//2))
if(n%2==0):
for i in range(1,sqrt+(n//2-sqrt)+1):
c=c*((i**(n-(i-1)))(n-(i-1))i)
else:
for i in range(1,sqrt+(int(n//2)-sqrt)+1):
c=c((i*(n-(i-1)))(n-(i-1))i)
c=c((int(n//2)+1)*(int(n//2)+1))
print(c%m)

61

Try to make your solution time efficient. O(n) for every testcase will give TLE.

62

whats wrong with this approach???

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
ll dp1[100000000];
ll dp2[100000000];
ll findsol(ll n)
{
dp1[0] = 1;
dp2[0] = 1;
for(ll i = 1 ;i < n;i++)
{
dp1[i] = dp1[i-1]*(i+1);
dp1[i] %= mod;
dp2[i] = dp2[i-1]*dp1[i];
dp2[i] %= mod;
}
return dp2[n-1];
}
int main() {
int t;
cin>>t;
while(t–)
{
ll n;
cin>>n;
cout<<findsol(n)<<’\n’;
}
}

63

Use Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

64

I am getting TLE and WA even if I am using the fast exponentiation method
here is the link to my solution

https://www.codechef.com/viewsolution/38346909

plz, help me with this.