I am struggling to form recurring relations for the below problem.

Bob's current semester is coming to an end and he is given N assignments numbered from 1 to N to complete to pass the semester.These assignments are from B subjects numbered from 1 to B . Bob will do these assignment in numerical order over multiple days. Bob will do atleast one assignment each day till he have no assignments left to do. Also Bob can do more than one assignments the same day but he doesn't want to do more than one assignments from same subject on the same day. Bob wants to know in how many ways he can complete these assignments under these conditions. Two ways are different if the number and type of assignment done on any day is not equal.

Given an integer array A , where 1 <= A[i] <= B referring i'th assignment belongs to A[i] subject and an integer B return the total number of ways modulo 1000000007.

Problem Constraints 1 ≤ N, B ≤ 100000 1 ≤ A[i] ≤ M

Input Format The first input is an integer array A. The second input in an integer B.

Output Format Return an integer modulo 1000000007.

Example Input Input - 1: A = [1, 2, 1, 2, 2] B = 2

Input - 2:

A = [1, 2, 3, 4, 5, 6] B = 6

Example Output Output - 1: 5

Output - 2:

32

I will appreciate any hint or solution for this one. I have spent around 6hrs on this but still not able to solve

CodePudding user response：

This should work. dp[i] denotes the number of possible ways to partition the array such that the last partition is closed at i.

#define FOR(i,a,b) for(long i=a;i<b;i  )
int mod=int(1e9 7);
void add_self(ll &A,const ll &B){
    A=(A B)%mod;
}
vector<ll> dp;

int solve(vector<int> &A, int B) {
        vector<int> frq(B 10,0);
    int n=A.size();
    vector<pair<int,int>> arr;
    FOR(i,0,A.size()){
      arr.pb({frq[A[i]],A[i]}); frq[A[i]]  ;
    }
    sort(arr.begin(),arr.end());
    dp=vector<ll>(n 1,0); dp[0]=1;
    vector<int> pos(n 1,0),pos2(B 1,0);
    FOR(i,0,arr.size()){
        pos[i 1]=pos2[arr[i].si];
        pos2[arr[i].si]=i 1;
    }
    vector<ll> pre(n 1,0); pre[0]=1;
    FOR(i,1,n 1){
        ll val=pre[i-1]; if(pos[i]){val=(val-pre[pos[i]-1] mod)%mod;}
        add_self(dp[i],val);
        add_self(pre[i],dp[i] pre[i-1]);
    }
    return dp[n];
}

CodePudding user response：

//Brute Force Approach
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
void solve(int n,int a[],int b,set<int>& s,int start,int end,int &count)
{
    if(end==n || start==n){
        count  ;
        return;
    }
    //for(int tem:s)cout<<"S1"<<count<<" "<<tem<<" ";
    cout<<endl;
    if(s.find(a[end])==s.end())
    {
        s.insert(a[end]);
        solve(n,a,b,s,start,end 1,count);
    }
    s.clear();
    s.insert(a[end]);
    solve(n,a,b,s,end,end 1,count);
}
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i  )cin>>a[i];
    int b;
    cin>>b;
    int count=0;
    set<int> s;
    s.insert(a[0]);
    solve(n,a,b,s,0,1,count);
    cout<<"ans "<<count<<endl;
    return 0;
}