{"problem":{"name":"[USACO23OPEN] Rotate and Shift B","description":{"content":"**Note: The time limit for this problem is 4s, 2x the default.** To celebrate the start of spring, Farmer John's $N$ cows have invented an intriguing new dance, where they stand in a circle and re-or","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9185"},"statements":[{"statement_type":"Markdown","content":"**Note: The time limit for this problem is 4s, 2x the default.**\n\nTo celebrate the start of spring, Farmer John's $N$ cows have invented an intriguing new dance, where they stand in a circle and re-order themselves in a predictable way.\n\nSpecifically, there are $N$ positions around the circle, numbered sequentially from $0$ to $N-1$, with position $0$ following position $N-1$.  A cow resides at each position.  The cows are also numbered sequentially from $0$ to $N-1$.  Initially, cow $i$ starts in position $i$.  You are told a set of $K$ positions $0=A_1<A_2<\\dots<A_K<N$ that are \"active\", meaning the cows in these positions are the next to move.\n\nIn each minute of the dance, two things happen.  First, the cows in the active positions rotate: the cow at position $A_1$ moves to position $A_2$, the cow at position $A_2$ moves to position $A_3$, and so on, with the cow at position $A_K$ moving to position $A_1$.  All of these $K$ moves happen simultaneously, so the after the rotation is complete, all of the active positions still contain exactly one cow.  Next, the active positions themselves shift:\n$A_1$ becomes $A_1+1$, $A_2$ becomes $A_2+1$, and so on (if $A_i = N-1$ for some active position, then $A_i$ circles back around to $0$).\n\nPlease calculate the order of the cows after $T$ minutes of the dance.\n\n## Input\n\nThe first line contains three integers $N, K$ and $T$.\n\nThe second line contains $K$ integers representing the initial set of active positions\n$A_1,A_2, \\dots, A_K$.  Recall that $A_1 = 0$ and that these are given in increasing order.\n\n## Output\n\nOutput the order of the cows after $T$ minutes, starting with the cow in position $0$, separated by\nspaces.\n\n[samples]\n\n## Note\n\nFor the example above, here are the cow orders and $A$ for the first four timesteps:\n```\nInitial, T = 0: order = [0 1 2 3 4], A = [0 2 3]\nT = 1: order = [3 1 0 2 4]\nT = 1: A = [1 3 4]\nT = 2: order = [3 4 0 1 2]\nT = 2: A = [2 4 0]\nT = 3: order = [2 4 3 1 0]\nT = 3: A = [3 0 1]\nT = 4: order = [1 2 3 4 0]\n```\n\n$1 \\leq K \\leq N \\leq 2 \\cdot 10^5$, $1\\le T\\le 10^9$.\n\n- Inputs 2-7: $N \\leq 1000, T \\leq 10000$.\n- Inputs 8-13: No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9185","tags":["模拟","数学","倍增","USACO","2023"],"sample_group":[["5 3 4\n0 2 3\n","1 2 3 4 0\n"]],"created_at":"2026-03-03 11:09:25"}}