UVa 1274-Shuffle

テーマリンク
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=513&page=show_problem&problem=3326
【タイトルの大意】
音楽プレーヤーを聴いています。ランダム再生方式を採用しています。ランダム再生の原理は、まずランダムに1つの1〜nの配列を作成し、その後、この順序で曲を再生します。このシーケンスのすべての曲を再生した後、再びランダムに1～nの配列を作成し、再生を続けます。
今はあなたに歴史記録を再生します。この歴史記録は不完全です。記録を始める時、すでに一部の歌が流れましたが、記録されていません。
今あなたに1段のいつからの音楽の歴史の記録を放送して、およびプレーヤーの中で全部でいくつの歌があります。
歴史の記録の中で第1首の歌はあるランダムリストの中の第数首かもしれなくて、全部でいくつの可能性がありますか？
【考え方】
先に前処理を行い、1つのbookで記録し、ok【i】はi番目の位置から始まる連続s個数を表しても同じではないですか？
そして、最初の曲はx曲目で、先にs-x曲が同じではないかを確認します。これも先に処理して判断してもいいです。
その後xからx、x+s、x+2*sを判断します。全部条件を満たせばいいですか？
【コード】

/*
 *
 * UVa 12174 - Shuffle
 *
 */
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 100010;

int s, n;
int arr[MAXN];
int cnt[MAXN];
bool first[MAXN], ok[MAXN];


//    
inline void init(){
    memset(first, 0, sizeof(first));
    memset(ok, 0, sizeof(ok));
    memset(cnt, 0, sizeof(cnt));

    first[0] = true;
    int i;
    for(i=0; i<s && i<n && !cnt[arr[i]]; ++i){
        first[i+1] = true; 
        cnt[arr[i]] = 1;
    }
    if(i==n && i<s && first[i]){
        while(i++<s)
            first[i] = true;
    }

    memset(cnt, 0, sizeof(cnt));
    ok[n] = true;
    int count=0;

    for(int i=n-1; i>=0; --i){

        if(cnt[arr[i]]++ == 0){
            ++count;
        }

        if(count == s || n-i<s&&n-i==count){
            ok[i] = true;
        }

        if(i+s-1<n){
            if(--cnt[arr[i+s-1]] == 0){
                --count;
            }
        }
    }
}

bool check(int st){
    while(st < n){
        if(!ok[st]) return false;
        st += s; 
    }
    return true;
}

int main(){
    int nCase;
    scanf("%d", &nCase);
    while(nCase--){
       

        scanf("%d%d", &s, &n);

        for(int i=0; i<n; ++i)
            scanf("%d", &arr[i]);

        init();
        int ans = 0;
        for(int i=0; i<s; ++i)
            if(first[i] && check(i))
                ++ans;
        printf("%d
", ans);

    }
    return 0;
}