Why O(M+N) when there are N integers each requiring M operations? so M * N?
You cannot just simply carry out the remainder of ((10^9)*(10^9)) divided by m.
Here’s the code snippet for mod of multiplication of such large values.
unsigned long long mulmod(unsigned long long a,unsigned long long b,unsigned long long c){
if(a<=1000000000ULL && b<=1000000000ULL){
unsigned long long ret = ((a%c)*(b%c))%c;
return ret;
}
unsigned long long ret = 0ULL;
a=a%c;
while(b > 0ULL){
if(b&1ULL) {
ret = (ret+a)%c;
}
a = (a<<1ULL)%c;
b>>=1ULL;
}
return ret%c;
}##
- Heading
2 Likes
Awesome problem…
Let’s store the sum of 1∗1!+2∗2!+…x∗x! for each x≤M. We can compute it in O(M).
Can you tell me how can you compute this where m = 10,000,000
I am also having trouble seeing how computing each i*i! up to 10**7 is possible in time allowance. I understand each iteration is a single additional multiplication, but even the following is timing out for me at 5+ seconds:
import time
s = time.clock()
for i in range(10**7):
x = i*i
print(time.clock()-s)
It seems that the ‘alternative’ formula (x+1)!-1 is completely necessary? No? Thanks!
Hi,
I have re-attempted this problem in C++ using the idea of precomputing all the factorial values until the value of M (maximum value of mod)…
However I’m getting WA on the last sub-task and also on 1st subtask of task 3:
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
//We compute all the factorials up to the modulo max value
/* the product will contain M on it, which means its value will always be 0 mod M */
#define MAXFACT 19999999
long long int precalc[MAXFACT]={0LL};
void PreComputeModdedFactorials(int m)
{
precalc[0]=1;
for(int i = 1; i <= MAXFACT; i++)
precalc[i] = (i%m*precalc[i-1]%m)%m;
}
long long int prodVal(unsigned long long int x)
{
if(x<=MAXFACT)
return precalc[x+1];
else
return 0;
}
long long int negval(int m)
{
return m-1; // -1 mod M = M-1
}
long long int divparcel(unsigned long long int x, int m)
{
if(x%2==0)
return (x%m*(x/2)%m*(x+1)%m)%m;
else
return (x%m*x%m*((x+1)/2)%m)%m;
}
long long int f(unsigned long long int x, int m)
{
return (((divparcel(x,m)%m+negval(m)%m)%m)+prodVal(x))%m;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
cin >> n >> m;
PreComputeModdedFactorials(m);
vector<unsigned long long> v(n);
for(int i = 0; i < n; i++)
cin >> v[i];
unsigned long long ans = 0ULL;
for(int i = 0; i < n; i++)
{
//cout << prodVal(v[i]) << endl;
ans = (ans%m + f(v[i], m)%m)%m;
}
cout << ans%m << endl;
return 0;
}
In advance, sorry for the “mod spam”, but, besides that, is there anything wrong with the code? If yes, what? =))
Best,
Bruno
Is this correct? To handle the divison parcel?
unsigned long long int divparcel(unsigned long long int x, int m)
{
if(x%2==0)
return (((x%m*(x/2)%m)%m)*(x+1)%m)%m;
else
return ((x%m*x%m)%m*((x+1)/2)%m)%m;
}WHAT IS WRONG IN MY CODE … I M NOT GETTING IT
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define size6 10000003
#define size5 100001
#define s(n) n=Scan_f()
#define loop(i,N) for(i=0;i<N;i++)
#define pll(n) printf("%lld\n",n)
typedef long long int ulli;
inline unsigned long long int Scan_f()
{
int c;
do
c = fgetc(stdin);
while ( (c < ‘0’ || c > ‘9’) && c != EOF );
unsigned long long int a = 0;
while ( c >= '0' && c <= '9' )
{
a = a*10 + (c - '0');
c = fgetc(stdin);
}
return a;
}
ulli i,N,K,memofact[size6]= {0} ,memofinal[size6]= {0};
ulli fact(ulli n)
{
if(n==1) return 1;
{
ulli x;
if(memofact[n]!=0) return memofact[n];
{
x=(n*(fact(n-1)))%K;
memofact[n]=x;
return x;
}
}
}
ulli modulo(ulli n)
{
ulli y;
if(n%2==0)
{
y=n/2;
y%=K;
y*=((n+1)%K);
y%=K;
y*=((n)%K);
y%=K;
}
else
{
{
y=(n+1)/2;
y%=K;
y*=((n)%K);
y%=K;
y*=((n)%K);
y%=K;
}
}
return y;
}
ulli tag=10000;
ulli calc(ulli n)
{
if(n==1) return 2%K;
{
ulli x;
if(memofinal[n]!=0) return memofinal[n];
{
while(n>tag)
{
x=fact(tag);
tag+=1000;
}
ulli y;
x=(fact(n+1)-1)%K;
y=modulo(n);
x=(x+y)%K;
memofinal[n]=x;
return x;
}
}
}
int main()
{
memofact[1]=1;
s(N);
s(K);
// memofinal[0] fOR STOREING NO.
{
ulli ans=0;
{
loop(i,N)
{
s(memofinal[0]);
if(memofinal[0]>=(K-1))
ans=(ans+modulo(memofinal[0]))%K;
else
ans=(ans+calc(memofinal[0]))%K;
}
pll(ans);
}
}
return 0;
}
please Explain this (i!=0, for i>=M)
Good proof for 1∗1!+2∗2!+…+x∗x! = (x+1)!−1:
Let Sum = 1∗1!+2∗2!+…+x∗x!
Add (1! + 2! + … + x!) to both sides.
Sum + (1! + 2! + … + x!) = (1.1! + 1!) + (2.2! + 2!) + (3.3! + 3!) + … + (x.x! + x!)
Sum + (1! + 2! + … + x!) = (2!) + (3!) + (4!) + … + (x+1)!
Sum = (x+1)! - 1.
2 Likes
please help me out. what is wrong in my code
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll S1(ll x, ll m)
{
if(x%2 == 0)
return ((x/2)%m * x%m * (x+1)%m)%m;
else
return (x%m * x%m * ((x+1)/2)%m)%m;
}
ll S2(ll fact[], ll max, ll x, ll m)
{
if(x <= max+1)
return (fact[x+1]-1+m)%m;
else
return (m-1);
}
int main()
{
ll n,m;
scanf("%lld%lld",&n,&m);
ll p[n];
ll max = 1;
for(ll i=0;i<n;i++)
{
scanf("%lld",&p[i]);
max = (max < p[i] && p[i] < m)?p[i]:max;
}
ll fact[max+2];
fact[0] = 1;
for(ll i=1;i<=max+1;i++)
fact[i] = (fact[i-1]%m * i%m)%m;
ll sum = 0;
for(ll i=0;i<n;i++)
sum = (sum%m + (S1(p[i],m)%m + S2(fact,max,p[i],m)%m)%m)%m;
printf("%lld\n",sum);
return 0;
}My solution is failing on test case 7. All other cases are passing. What might be the issue?
I am unable to figure this out.
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<map>
#include<climits>
#include<vector>
#include<algorithm>
using namespace std;
long long precompute[10000001];
// calculating i+1 ! in precompute[i]
void pre_compute(int m) {
precompute[0] = 0;
precompute[1] = 2;
for (long long i = 2; i<m; i++) {
precompute[i] = precompute[i-1]*(i+1);
precompute[i] %= m;
}
}
long long fun(long long x, int m) {
long long ans = ((x%m) * ((x+1)%m))/2;
ans %= m;
ans *= (x%m);
ans %= m;
if (x > m)
x = m-1;
ans += (precompute[x] - 1);
ans %= m;
return ans;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
pre_compute(m);
long long temp;
long long sum = 0;
for(int i = 0; i < n; i++) {
scanf("%lld",&temp);
sum += fun(temp, m);
sum %= m;
}
printf("%lld\n",sum);
return 0;
}I am just wondering whether complexity of your solution is \mathcal{O}(n^2). The calculation of fact seems like taking \mathcal{O}(n) for each iteration. I am not completely sure about this as I don’t understand the lambda syntax of python.
1 Like
Hi @dpraveen, good catch, maybe that’s an issue… I will try to switch to C++ and use some factorial pre-processing of some sort to see if it’s possible to pass the first and second subtasks like that 
Thanks!! Also, is it something extra needed to pass the last subtask?
EDIT; nvm re-read the editorial, found the trick which was missing me! Nice one
Can you please elaborate your doubt? What part you did not understand?
You should ask your question as an actual question in the Forum. You most probably won’t get an answer if you post your question as an answer to another question
to calculate ( a / b ) % m you need to find multiplicative inverse of 2 modulo m and to calculate that m and b must me coprime.
As said above (AB)%M=((A%M)(B%M)%M)…so lets consider a case where we need to calculate the factorial of 5.What we will do is calculate the factorial and perform the modulo operation on it.
fact=1; for i=1 to i<=5: fact=((fact%M)*(i%M))M; do it this way and you will get the correct answer.
Note : M here being the number whose modulo the answer should be.