UVA 11536 - Smallest Sub-Array

/*

    講符合要求的子序列 從兩端縮短 ，得到最小值

*/

#include<cstdio>

#include<cstring>
#include<map>
using namespace std;
int vis[1000001];
int f[1000001];
int n,m,k;
int init()
{
    memset(f,0,sizeof(f));
}
int main()
{
    init();
    int t,count=1;
    scanf("%d",&t);
    while(t--)
    {
        memset(vis,0,sizeof(vis));
        scanf("%d%d%d",&n,&m,&k);
        if(k<=3)
        {
            printf("Case %d: %d\n",count++,k);
            continue;
        }
        for(int i = 0; i<=3; i++)
            f[i] = i;
        vis[1] = vis[2] = vis[3] = 1;
        int ans=0,res=3,mp=11000000;
        for(int l=1,r=4; r<=n; r++)
        {
            f[r] = (f[r-1]+f[r-2]+f[r-3])%m+1;
            if(!vis[f[r]])
            {
                vis[f[r]]=1;
                if(f[r]>=1&&f[r]<=k)
                    res++;
            }
            else
            {
                vis[f[r]]++;
            }
            if(res==k)
            {
                mp = min(mp,r-l+1);
            }
            while(l<=r)
            {
                if(f[l]>=1&&f[l]<=k&&vis[f[l]]==1)
                    break;
                vis[f[l]]--;
                l++;
                if(res==k)
                {
                    mp = min(mp,r-l+1);
                }
            }
        }
        if(mp!=11000000)
            printf("Case %d: %d\n",count++,mp);
        else printf("Case %d: sequence nai\n",count++);
    }
    return 0;
}