from math import *
def quoti(x,m):
return ((x*x*x + x*x)/2)%m
def fact(x,m):
return reduce(lambda x,y: (x*y)%m , [i for i in range(1,x+2)])
def negterm(m):
return m-1
n,m = map(int, raw_input().split())
L = map(int,raw_input().split())
ans = 0
for i in range(n):
#print ans
ans += (quoti(L[i],m) + fact(L[i],m) + negterm(m))
print int(ans%m)
Any help?
I know that the above code could not be of use for the larger sub-tasks but, with some tweaks maybe it would pass the 1st and 2nd subtasks…
Did we need to use the Totient Function to compute the modular inverse of 2 modulo M if M was not a prime number? How could/should we approach this?
I was at a loss at this and the editorial is not very clear really…
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;
}##
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!
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? =))
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;
}
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.
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