bzoj上现在找不到这题，所以目前只是过了样例，没有测
2054: 疯狂的馒头
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 715 Solved: 298
Description
Input
第一行四个正整数N，M，p，q
Output
一共输出N行，第i行表示第i个馒头的最终颜色（如果最终颜色是白色就输出0）。
Sample Input
4 3 2 4
Sample Output
2
2
3
0
2
3
0
HINT
用并查集维护当前馒头之后第一个白馒头的位置，初始f[x]=x
倒着处理，这样一个馒头只会染一次。
详见代码
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
int f[mxn];
int co[mxn];
int n,m,p,q;
int find(int x){
return f[x]==x? x:x=find(f[x]);
}
int main(){
int i,j;
scanf("%d%d%d%d",&n,&m,&p,&q);
for(i=;i<=n;i++)f[i]=i;
for(i=m;i>=;i--){
int s=(i*p+q)%n+;//边界
int t=(i*q+p)%n+;
if(s>t)swap(s,t);
for(j=find(s);j<=t;j=find(j)){
co[j]=i;
f[j]=j+;
}
}
for(i=;i<=n;i++){
printf("%d\n",co[i]);
}
return ;
}