2

13 3

6 12 1

2 9 0

10 13 8

10 1

2 4 2
Sample Output

Case #1:

6

7

8

9

10

11

12

2

3

4

Case #2:

1

5

2

3

4

6

7

8

9

10

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<string>

#include<algorithm>

using namespace std;

#define INF 0x3f3f3f3f

#define ll __int64

#define N 100010

int n,m;

int ansl;

int ans[N];

struct SplayTree

{

    int ch[N][],pre[N],val[N],num[N],rev[N],sz[N];

    int top,root;

    inline void Rotate(int x,int c){

        int y=pre[x];

        ch[y][!c]=ch[x][c];

        if(ch[x][c]) pre[ch[x][c]]=y;

        pre[x]=pre[y];

        if(pre[y]) ch[pre[y]][ch[pre[y]][]==y]=x;

        ch[x][c]=y;

        pre[y]=x;

        PushUp(y);

        if(y==root) root=x;

    }

    inline void Splay(int x,int f){

        while(pre[x]!=f)

        {

            if(pre[pre[x]]==f) Rotate(x,ch[pre[x]][]==x);

            else

            {

                int y=pre[x],z=pre[y];

                int c=(ch[z][]==y);

                if(ch[y][c]==x) Rotate(x,!c),Rotate(x,c);

                else Rotate(y,c),Rotate(x,c);

            }

        }

        PushUp(x);

        if(f==) root=x;

    }

    inline void SplayKth(int k,int f){

        int x=root;

        k+=;

        while()

        {

            if(k==sz[ch[x][]]+) break;

            else if(k<=sz[ch[x][]]) x=ch[x][];

            else k-=sz[ch[x][]]+,x=ch[x][];

        }

        Splay(x,f);

    }

    inline void PushUp(int x){

        sz[x]=sz[ch[x][]]+sz[ch[x][]]+;

    }

    inline void NewNode(int &x,int c,int f){

        x=++top;

        sz[x]=;

        ch[x][]=ch[x][]=rev[x]=;

        val[x]=c;

        pre[x]=f;

    }

    inline void Build(int &x,int l,int r,int f){

        if(l>r) return;

        int m=(l+r)>>;

        NewNode(x,num[m],f);

        Build(ch[x][],l,m-,x);

        Build(ch[x][],m+,r,x);

        PushUp(x);

    }

    inline void Init(int n){

        top=pre[]=ch[][]=ch[][]=sz[]=rev[]=;

        val[]=INF;

        for(int i=;i<=n;i++) num[i]=i;

        Build(root,,n+,);

    }

    void Res()

    {

        int l,r,tt;

        scanf("%d%d%d",&l,&r,&tt);

        int len=r-l+;

        l--;

        SplayKth(l,);

        SplayKth(r+,root);

        int x=ch[ch[root][]][];

        ch[ch[root][]][]=;

        PushUp(ch[root][]);

        PushUp(root);

        tt++;

        SplayKth(tt-,);

        SplayKth(tt,root);

        ch[ch[root][]][]=x;

        pre[ch[ch[root][]][]]=ch[root][];

        PushUp(ch[root][]);

        PushUp(root);

    }

    void Print(int x){

        if(ch[x][]) Print(ch[x][]);

        if(val[x]>= && val[x]<=n)

            ans[++ansl]=val[x];

        if(ch[x][])  Print(ch[x][]);

    }

}t;

int main()

{

    int T,j,iCase=;

    scanf("%d",&T);

    while(T--)

    {

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

        t.Init(n);

        printf("Case #%d:\n",iCase++);

        while(m--) t.Res();

        ansl=;

        t.SplayKth(t.root,);

        t.Print(t.root);

        for(int i=;i<=;i++) cout<<ans[i]<<endl;

    }

    return ;

}

G: islands想吃糖果

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 24 Accepted: 0 Page View: 80

Description

daidao买了很多糖果带到实验室，里面有n颗，islands看到了很高兴马上准备吃。daidao数了一下实验室的人有m个(包括daidao)，问islands如果你能告诉我有多少种不同方案把这些糖果分给实验室的m个人，并且每人至少都要分一个，我就给你吃（对于2个方案，只要存在一个或一个以上的人分的数目不同就是2个不同的方案）。旁边的w703710691d说这可难不倒islands，再加上一个条件，要求每个人分的糖果的个数的最大公约数正好为k。（m个数的最大公约数是说有能整除这m个数中的最大的）。由于答案很大，daidao要求答案对1000000007取模。这下islands难住了，你能帮助islands吃到糖果吗。

Input

首先输入一个证书T表示测试数据组数（T<100）

接下来T行每行输入3个正整数,n,m,k。（ 0 < n,m,k < = 200）

Output

对于每组数据输出按照格式“Case #x: a”（不包括冒号）输出一行。其中x表示第x组测试数据，a表示对应的答案。 
Sample Input