IOICJ 89 Tool Man ( DP )

Problem Description:
You are given an array A consisting of N elements. You know that they are K different people's orders, where some consecutive elements are what they have ordered. You also know that every order was ordered by some one, and every person ordered some thing. However, no one would buy the same elements more than once. Show the number of valid ways modulo 900720143.

Constraints:
1≤T≤100
1≤N≤1e5
1≤K≤min(20,N)
1≤ai≤1e5
Sigma{ N } ≤ 8e5
TL: 2000 ms

Sample Input:
5
8 3
3 2 5 2 5 7 6 5
5 2
100000 1 2 3 4
7 4
1 2 3 4 2 5 1
3 3
5 1 4
2 1
1021 1021

Sample Output:
3
4
19
1
0

Solution:
Preprocess :
lb[ i ] : minimum index such that A[ lb[ i ], i ) does not contain duplicate values ( 1 based )
dp[ i ][ j ] : number of valid ways to arrange the first n elements to the first i people
dp[ i ][ j ] = Sigma{ dp[ i - 1 ][ lb[ j ], j ) }, which could be accelerated with dynamic prefix sum

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector< int > vi;

const int INF = 0x3f3f3f3f;

const int MAXN = ( int ) 1e5;
const int MAXK = 20;
const int MOD = 900720143;

int N, K;
vi A;

void init(){
  cin >> N >> K;
  A = vi( N );
  for( int i = 0; i < N; ++i ){
    cin >> A[ i ];
  }
}

ll dp[ MAXK + 1 ][ MAXN + 1 ];
ll pdp[ MAXK + 1 ][ MAXN + 1 ];

void preprocess(){
  for( int i = 0; i <= K; ++i ){
    for( int j = 0; j <= N; ++j ){
      dp[ i ][ j ] = pdp[ i ][ j ] = 0;
    }
  }
  pdp[ 0 ][ 0 ] = dp[ 0 ][ 0 ] = 1;
  for( int i = 0; i + 1 <= N; ++i ){
    pdp[ 0 ][ i + 1 ] += pdp[ 0 ][ i ];
  }
  vi lb( N + 1 ); // [ lb[ i ], i ), where lb[ i ] is minimum and range is valid
  set< int > bag;
  for( int i = 1, ptr = 0; i <= N; ++i ){
    while( bag.count( A[ i - 1 ] ) ){
      bag.erase( A[ ptr ] );
      ++ptr;
    }
    bag.emplace( A[ i - 1 ] );
    lb[ i ] = ptr;
  }
  for( int i = 1; i <= K; ++i ){
    for( int j = 1; j <= N; ++j ){
      dp[ i ][ j ] = pdp[ i - 1 ][ j - 1 ];
      if( lb[ j ] != 0 ){
        ( dp[ i ][ j ] -= pdp[ i - 1 ][ lb[ j ] - 1 ] ) %= MOD;
      }
      pdp[ i ][ j ] = pdp[ i ][ j - 1 ];
      ( pdp[ i ][ j ] += dp[ i ][ j ] ) %= MOD;
    }
  }
}

void solve(){
  int ans = dp[ K ][ N ];
  if( ans < 0 ) ans += MOD;
  cout << ans << endl;
}

signed main(){
  ios::sync_with_stdio( 0 );
  int T; cin >> T;
  for( int ti = 0; ti < T; ++ti ){
    init();
    preprocess();
    solve();
  }
  return 0;
}