Blog

Problem link

আলোচনাঃ
আমাকে code দেয়াই আছে, তবে ঐ code টাকে এমনভাবে modify করা লাগবে যেন overflow না করে।
এর আগে আমদের নিচের ব্যাপারটা জানা লাগবে-

Also you can check this article.

চিত্র থেকে বুঝা যাচ্ছে , (a*b)%mod বের করা আর ((a%mod)*(b%mod))%mod বের করা একই জিনিস। তাহলে কোনটা করবো?

2nd টা করবো always.কারণ যাতে overflow না করে। তেমনিভাবে addition,substraction
এও একই জিনিস করা যাবে। তবে division এর ক্ষেত্রে তা করা যাবে না।

উত্তরঃ

তো আমাদের problem এ যেহেতু addition করা লাগবে আর এখানে যেহেতু overflow হওয়ার chance
আছে তাই আমরা 2nd উপায়ে যোগ করবো।

আচ্ছে তাহলে code করে submit দিলেই তো AC হবে। এ আর এমন কি?

কিন্তু problem হচ্ছে এভাবে করলে TLE দিচ্ছে। কারণ এখানে একবার calculate করা জিনিস অনেক বার
calculate করছে যার কারণে TLE দিচ্ছে। তো আমদের DP করা লাগবে তাহলে এই problem আর হবে না।
কারণ dynamic programming এ আমরা একটা জিনিস যদি আগেই calculate করা হয় তখন তাকে আমরা
একটা memory তে save করে রাখি। পরে যদি সেই জিনিসটা আবার calcullate করার দরকার পরে তখন
আমরা আবার calculate না করে আগের calculate করা value return করে দেই। এতে আমদের
অনেক time কম লাগে।

আর এখানে যেহেতু 100 টা test case আছে তাই আমদের প্রতি case এ memset() করা লাগবে যাতে
আগের calculate করা value dp[] array তে জমা না থাকে।

আর (fn(n)+MOD)%MOD এভাবে print করার কারণ হচ্ছে যাতে result overflow করে negative
value না আসে। এটা convention.এটা safety এর জন্য করা ভালো।

আর int &ret=dp[n] লেখার কারণ হচ্ছে যাতে আমাকে বার বার dp[n] লেখা না লাগে। আর এটা কিভাবে
কাজ করে? আসলে &ret এর মধ্যে dp[n] এর memory address থাকে। এর ফলে আমরা ঐ memory
address এ যেই value থাকে তাকে check করি। যদি দেখি -1 নেই তাহলে বুঝতে পারবো এই value
আগেই calculate করেছি। তখন ঐ n এর জন্য আবার calculate না করে আগের calculate
করা value সরাসরি return করে দেই।

এই problem er ক্ষেত্রে আমদের কোনো result ই -1 হবে না। তাই আমরা -1 দিয়ে আগে memset()
করে নিয়েছি। তার আমাকে এমন কোনো value দিয়ে memset() করা লাগবে যেন ঐ value টা আমার
answer হবার কোনো chance না থাকে।

C++ Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e4+10;
#define pii pair<int,int>
#define MOD 10000007
int t,a, b, c, d, e, f, n,cs=1;
int dp[N];
 
int fn(int n){
 
    if(n==0) return a%MOD;
    if(n==1) return b%MOD;
    if(n==2) return c%MOD;
    if(n==3) return d%MOD;
    if(n==4) return e%MOD;
    if(n==5) return f%MOD;
 
    int &ret=dp[n]; // save referance of dp[n] into &ret
    if(ret!=-1) return ret;
 
    ret=fn(n-1)%MOD+fn(n-2)%MOD+fn(n-3)%MOD+fn(n-4)%MOD+fn(n-5)%MOD+fn(n-6)%MOD;
    return ret;
}
 
int main(){
 
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&n);
        memset(dp,-1,sizeof(dp));
        // (fn(n)+MOD)%MOD for overflow issue
        printf("Case %d: %d\n",cs++,(fn(n)+MOD)%MOD);

    }
}

Related Problem : LightOj – 1259 – Goldbach`s Conjecture