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? =))
Thanks for the prompt reply but, that doesnt seem to be the problem… I’ve changed the return type to ULL and added yet another mod just to be sure and I only get WA on those 3 flies… weird
Hey @xellos0, nice, thanks for the tip, so… how can I fix that above code?
"This means, we can reduce the task to multiply 3 numbers up to 10^7 (the modulo value) by doing modulo M for each of the numbers before multiplication. "
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%mx%m)%m*((x+1)/2)%m)%m;
}
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;
}
Just use parentheses, Luke. (And use them correctly. You added them everywhere except where you needed them.)
x/2 is not up to 1e7. x/2 is up to 5e18. (x/2)%M is up to 1e7. It’s b*(x/2)=c, not b*((x/2)%M)=c (note the parentheses).
((((x%m)((x/2)%m))%m)((x+1)%m))%m is the right way. Or just store x,x/2,x+1 in separate variables first, mod these variables and then multiply them while modding again, if you want a cleaner code.
@knb_dtu Occam’s razor: don’t use more than necessary. Anything more than ((a%m)*(b%m))%m is unnecessary. (How much time would you waste during a contest by overcomplicating things like this?)
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;
}
weird