约瑟夫环变式
设f[i][j]表示处理i个人,按照处理顺序,倒数第j个人是谁
则有f[i][j]=(f[i-1][j]+k)%i
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define MAXN 500005 using namespace std; int f[MAXN][4]; int n,k; void solve(){ scanf("%d%d",&n,&k); int b[3]={0}; int t=-1; for(int i=2;i>=0;i--){ for(int j=1;j<=k;j++){ (t+=1)%=3; while(b[t]){ (t+=1)%=3; } } f[3][i]=t; b[t]=1; } for(int i=4;i<=n;i++){ for(int j=0;j<=2;j++){ f[i][j]=(f[i-1][j]+k)%i; } } printf("%d %d %d\n",f[n][2]+1,f[n][1]+1,f[n][0]+1); } int main() { // freopen("data.in","r",stdin); int T; scanf("%d",&T); while(T--){ solve(); } return 0; }
原文:http://www.cnblogs.com/w-h-h/p/7863040.html