Sunday 30 October 2016

Spoj PUCMM210

LOGIC:

As we already have our strategy first try to write brute force solution if you are unable to figure out optimized solution.
Here brute force solution will look like:

Function(N) {
          For i = 1 to N {
                F_value_at_i  += (i * i * i)
                S_value_at_i  += (S_value_at_i_minus_1 + F_value_at_i)
                Take mode if required
         }
         return S_value_at_N
}

so we can always call Function(N) for each test case so time complexity will be O(N * T)
and it can be huge because N is at most 10^6 and T is at most 10^5 so it will be timeout.

If we look at Function we can say that we are doing repeated work so to remove repetition we will precompute and keep in cache. (Basic of DP(Dynamic Programming) :) )

Below you can see code also

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////

#define MXN 1000000
#define MOD 1000000003
long long F[MXN + 2];
long long Sum[MXN + 2];

int main()
{
Sum[0] = F[0] = 0;
for(int i = 1; i <= MXN; ++i) {
long long temp = i;
temp *= i;
if(temp >= MOD) 
temp %= MOD;
temp *= i;
if(temp >= MOD)
temp %= MOD;
F[i] = F[i - 1] + temp;
if(F[i] >= MOD)
F[i] %= MOD;

Sum[i] = Sum[i - 1] + F[i];
if(Sum[i] >= MOD)
Sum[i] %= MOD;
}

int T;
scanf("%d", &T);

while(T--) {
int N;
scanf("%d", &N);
printf("%lld\n", Sum[N]);
}

    return 0;
}



Happy Coding :)

No comments:

Post a Comment