题目链接&＃xff1a;
题意&＃xff1a;有 n 个人围成一个圈&＃xff0c;从 1 开始报到第 k 个人出环&＃xff0c;问第 m 个出环的人是谁&＃xff0c;n、m、k <&＃61; 1e18 且 min&＃xff08;m&＃xff0c;k&＃xff09;<&＃61; 2e6。
题解&＃xff1a;容易得出O&＃xff08;m&＃xff09;的递推公式 f[n][m] &＃61; &＃xff08;f[n-1][m-1] &＃43; k - 1&＃xff09;% n &＃43; 1&＃xff0c;初始状态 f[n-m&＃43;1][1]容易得出&＃xff0c;当 m 小的时候用该公式计算。考虑 k 大 m 小的情况下&＃xff0c;递推式的取膜很多情况下没有用到&＃xff0c;可以用乘法代替加法加速递推的过程&＃xff1a;
当前状态为f[a][b] &＃61; c&＃xff0c; 经过 x 次加法后的状态为 f[a&＃43;x][b&＃43;x] &＃61; c &＃43; k * x&＃xff0c;假设经过 x 次加法之后需要取模&＃xff0c;有
c &＃43; k * x > a &＃43; x → x > &＃xff08;a - c&＃xff09;/ &＃xff08;k - 1&＃xff09;
得到该不等式后便可以计算出另一种情况了&＃xff0c;还要注意 k &＃61; 1 需要特判。
1 #include
2 using namespace std;
3 #define ll long long
4 #define ull unsigned long long
5 #define mst(a,b) memset((a),(b),sizeof(a))
6 #define mp(a,b) make_pair(a,b)
7 #define pi acos(-1)
8 #define pii pair
9 #define pb push_back
10 const int INF &＃61; 0x3f3f3f3f;
11 const double eps &＃61; 1e-6;
12 const int MAXN &＃61; 2e6 &＃43; 10;
13 const int MAXM &＃61; 1e8 &＃43; 10;
14 const ll mod &＃61; 1e9 &＃43; 7;
15
16 ll f[MAXN];
17
18 int main() {
19 #ifdef local
20 freopen("data.txt", "r", stdin);
21 // freopen("data.txt", "w", stdout);
22 #endif
23 int cas &＃61; 1;
24 int t;
25 scanf("%d",&t);
26 while(t--) {
27 ll n,m,k;
28 scanf("%lld%lld%lld",&n,&m,&k);
29 printf("Case #%d: ",cas&＃43;&＃43;);
30 if(m <&＃61; k) {
31 f[1] &＃61; k % (n - m &＃43; 1);
32 if(f[1] &＃61;&＃61; 0) f[1] &＃61; n - m &＃43; 1;
33 for(ll i &＃61; 2; i <&＃61; m; i&＃43;&＃43;)
34 f[i] &＃61; (f[i - 1] &＃43; k - 1) % (n - m &＃43; i) &＃43; 1;
35 printf("%lld\n",f[m]);
36 } else {
37 if(k &＃61;&＃61; 1) printf("%lld\n",m);
38 else {
39 ll a &＃61; n - m &＃43; 1, b &＃61; 1;
40 ll c &＃61; k % a, x &＃61; 0;
41 if(c &＃61;&＃61; 0) c &＃61; a;
42 while(b &＃43; x <&＃61; m) {
43 a &＃43;&＃61; x, b &＃43;&＃61; x, c &＃43;&＃61; k * x;
44 c %&＃61; a;
45 if(c &＃61;&＃61; 0) c &＃61; a;
46 x &＃61; (a - c) / (k - 1) &＃43; 1;
47 }
48 c &＃43;&＃61; (m - b) * k;
49 c %&＃61; n;
50 if(c &＃61;&＃61; 0) c &＃61; n;
51 printf("%lld\n",c);
52 }
53 }
54 }
55 return 0;
56 }
京公网安备 11010802041100号