#include <bits/stdc++.h>
using namespace std;

const int MOD = 20123;
int stair[10005][105]; // 是否有楼梯
int num[10005][105];   // 指示牌数字
int stair_cnt[10005];  // 【优化】预处理：记录每一层一共有多少个楼梯

int main(){
    int n, m;
    cin >> n >> m;
    
    // 输入并统计每层楼梯总数
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> stair[i][j];
            if(stair[i][j] == 1) {
                stair_cnt[i]++; // 统计这一层有多少个楼梯
            }
            cin >> num[i][j];
        }
    }
    
    int ans = 0;
    int cur;
    cin >> cur; // 起始房间号
    
    for(int i = 0; i < n; i++){
        // 1. 累加答案,记得及时取mod防止溢出
        ans = (ans%MOD + num[i][cur]%MOD) % MOD;
        
        // 2. 【核心优化】计算实际需要找第几个有楼梯的房间
        // 公式：(x - 1) % total + 1
        int step = (num[i][cur] - 1) % stair_cnt[i] + 1;
        
        // 3. 模拟寻找（现在 step 最大只有 100，不会超时）
        while(step > 0){
            // 如果当前房间有楼梯
            if(stair[i][cur] == 1){
                step--; // 目标减少一个
                if(step == 0) break; // 找到了，就停在当前 cur，不需要再 cur++
            }
            
            // 没找到或者还要继续找，移动到下一间
            cur++;
            if(cur == m) cur = 0; // 绕圈
        }
        
        // 循环结束时，cur 正好停在有楼梯的那个房间，直接进入下一层循环(i++)即可
    }
    
    cout << ans << endl;
    return 0;
}

P1706 这道题（NOIP 2012 普及组 T2）是一道非常经典的模拟题，但是如果你真的老老实实按照题目说的去“转圈圈”，你只能拿一半的分数。

这道题考察的是模拟结合简单的数学优化（取模）。

下面是几个关键的思路提示：

1. 最大的坑：指示牌上的数字 $x$ 很大！

题目中说指示牌上的数字 $x$ 最高可以达到 $10^6$（一百万）。

• 如果不优化：假设某层楼只有 2 个楼梯，但是指示牌上写着 1,000,000。如果你写一个循环傻傻地转 100 万次圈去找楼梯，这层楼你就要跑很久。一共有 10,000 层楼，总运算量会爆炸，导致 TLE（超时）。
• 数学规律：
  • 这层楼一共有 $M$ 个房间，假设其中有 $cnt$ 个房间有楼梯。
  • 我们要找第 $x$ 个有楼梯的房间。
  • 因为房间是围成一圈的，转一圈又回到了原点。
  • 所以，找第 $x$ 个有楼梯的房间，其实等价于找第 $(x - 1) \% cnt + 1$ 个有楼梯的房间。
  • 原理：就好比只有 3 个楼梯，找第 4 个其实就是找第 1 个。利用取模运算，我们可以把查找次数限制在 $M$（100）以内，速度提升一万倍！

2. 核心逻辑步骤

你需要按层模拟，从第 1 层一直走到第 $N$ 层：

1. 预处理：在读入数据的时候，统计每一层一共有多少个楼梯（记为 stair_count），这在后面的取模运算中必须用到。
2. 累加密钥：到了某个房间，先把指示牌上的数字 $x$ 加到最终答案 ans 里（注意题目要求 ans 随时取模 20123）。
3. 计算步数：算出实际需要走的步数 step = (x - 1) % stair_count + 1。
   • 注意：这里为什么要 -1 再 +1？因为取模的结果是 0 到 cnt-1，而我们要找的是第 1 个到第 cnt 个。
4. 找房间（模拟）：从当前房间出发，逆时针查找（下标 j++），如果遇到有楼梯的房间，step 减 1。当 step 减到 0 时，当前的房间就是终点。
5. 上楼：在这个房间坐电梯上楼，位置不变，进入下一层的循环。

3. 数据存储建议

• $N \le 10000$，$M \le 100$。
• 你可以开一个二维数组 bool has_stairs[10005][105] 存是否有楼梯。
• 再开一个二维数组 int number[10005][105] 存指示牌数字。
• 最好再开一个一维数组 int stairs_per_floor[10005] 存每层楼楼梯的总数，方便直接调用。

4. 易错点提示

• 取模对象：计算步数时，是用 $x$ 对该层楼梯总数取模，而不是对 $M$ 取模，也不是对 20123 取模。
• 答案取模：题目要求输出的是密钥对 20123 取模的结果。要注意 $x$ 本身很大，累加时就要注意取模，或者最后取模。
• 循环边界：房间号是 $0$ 到 $M-1$。在模拟找房间时，下标增加后要记得对 $M$ 取模（pos = (pos + 1) % M），实现“绕圈”的效果。

加油！只要处理好这个取模优化，这就是一道简单的模拟题。

---

请检查这个答案的错误在哪里?

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int stair[10000][100]={0};//1000W个int是40mb，这里只有100W=4mb，内存足够
    int num[10000][100]={0};//懒得用pair，直接再开一个数组
    //初始化每层楼
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>stair[i][j];//是否有楼梯
            cin>>num[i][j];//对应的指示牌数字
        }
    }
    int ans=0;//答案秘钥，注意累加最终会很大所以每次相加都要mod20123来减小
    int cur;
    cin>>cur;//当前（起始）房间号
    for(int i=0;i<n;i++){
        //对于第i层楼，找到房间号对应的数字，加到ans上(取mod意义下)，再跳到num指示的楼梯向上
        ans=ans%20123+num[i][cur]%20123;//和的余数等于余数的和 错误2 这里结果没有及时对整体取mod导致最后答案ans会漏取模
        //找到第num[i][cur]个有楼梯的房间,当前是cur
        int cnt=0;//错误1 这里下面的循环查找有什么问题？
        do{
            do{
                cur++;//坑点3 这里一开始就cur++会错过当前cur刚好是梯子的情况（题目条件x>0所以没事）
                if(cur>=m){
                    cur=0;
                }
            }while(stair[i][cur]==0);
            //找到了一个梯子
            cnt++;
        }while(cnt<num[i][cur]);
        //找到了第cnt==num[i][cur]个梯子
        //当前i,cur就应该向上走到i+1层cur号房
        continue;
    }
    cout<<ans<<endl;
}

你的代码有两个主要错误：一个是逻辑错误（会导致结果不对），另一个是算法效率问题（会导致超时 TLE）。

1. 致命错误：超时 (TLE) —— 没有利用取模优化

问题描述： 题目中指示牌上的数字 $x$ 最大可达 $10^6$（一百万）。 你的代码逻辑是：

do {
    // 一步一步模拟走
    cnt++;
} while(cnt < num[i][cur]);

如果这一层只有 2 个楼梯，但指示牌写着 1,000,000。你的程序会在这一层转几十万圈。总共有 10,000 层，总运算量高达 $10^{10}$ 次，肯定会超时（通常限制是 $10^8$ 次）。

修正方法： 利用数学规律。在一个只有 $k$ 个楼梯的层里找第 $x$ 个楼梯，等价于找第 (x-1) % k + 1 个楼梯。 你需要先统计每一层一共有多少个楼梯，记为 total_stairs。 然后将要走的步数优化为：step = (num[i][cur] - 1) % total_stairs + 1。 这样每层最多只走 $M$（100）步。

2. 逻辑错误：跳过了当前房间

问题描述： 题目要求：“如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。” 你的代码逻辑是：

do{
    cur++; // 先向后移动
    ...
} while(stair[i][cur]==0);

这意味着你无条件地跳过了起始的 cur 房间。如果起始房间正好有楼梯，你的程序会把它忽略，去寻找“下一个”，导致计数错位。

修正方法： 先判断当前房间有没有楼梯，如果有，计数器就要减 1。然后再移动。或者在循环中先检查再移动。

3. 小细节：取模写法

ans = ans%20123 + num[i][cur]%20123;

这样写 ans 有可能会超过 20123（比如 $20000 + 20000 = 40000$）。虽然不会导致 int 溢出，但为了严谨和防止后续错误，标准写法应该是：

ans = (ans + num[i][cur]) % 20123;

为了防止ans + num[i][cur]溢出，可以先对相加的数取mod再累相加。

ans = (ans%20123 + num[i][cur]%20123) % 20123;

---

修改后的 AC 代码参考

#include <bits/stdc++.h>
using namespace std;

const int MOD = 20123;
int stair[10005][105]; // 是否有楼梯
int num[10005][105];   // 指示牌数字
int stair_cnt[10005];  // 【优化】预处理：记录每一层一共有多少个楼梯

int main(){
    int n, m;
    cin >> n >> m;
    
    // 输入并统计每层楼梯总数
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> stair[i][j];
            if(stair[i][j] == 1) {
                stair_cnt[i]++; // 统计这一层有多少个楼梯
            }
            cin >> num[i][j];
        }
    }
    
    int ans = 0;
    int cur;
    cin >> cur; // 起始房间号
    
    for(int i = 0; i < n; i++){
        // 1. 累加答案
        ans = (ans + num[i][cur]) % MOD;
        
        // 2. 【核心优化】计算实际需要找第几个有楼梯的房间
        // 公式：(x - 1) % total + 1
        int step = (num[i][cur] - 1) % stair_cnt[i] + 1;
        
        // 3. 模拟寻找（现在 step 最大只有 100，不会超时）
        while(step > 0){
            // 如果当前房间有楼梯
            if(stair[i][cur] == 1){
                step--; // 目标减少一个
                if(step == 0) break; // 找到了，就停在当前 cur，不需要再 cur++
            }
            
            // 没找到或者还要继续找，移动到下一间
            cur++;
            if(cur == m) cur = 0; // 绕圈
        }
        
        // 循环结束时，cur 正好停在有楼梯的那个房间，直接进入下一层循环(i++)即可
    }
    
    cout << ans << endl;
    return 0;
}

总结

这道题是典型的“模拟 + 数学优化”。以后遇到“在一个圈里转很多很多圈”的题目，一定要条件反射地想到 取模 (%) 来优化时间。

---

请详细解释这里的公式

// 2. 【核心优化】计算实际需要找第几个有楼梯的房间
// 公式：(x - 1) % total + 1
int step = (num[i][cur] - 1) % stair_cnt[i] + 1;

这是一个非常经典且重要的数学处理技巧，叫做 “将 1-based（从1开始的）编号映射到循环区间”。

在 OI 和编程中，我们经常遇到“转圈圈”的问题。为了让你彻底理解，我把这个公式拆解成三个步骤来讲。

1. 为什么要用这个公式？

场景： 假设这一层楼一共有 3 个有楼梯的房间（total = 3）。 指示牌上写着要找第 x 个有楼梯的房间。

如果不优化就用暴力循环，指示牌写着 100，你就要转 33 圈多，非常慢。 我们想利用取模（%）直接算出它等价于找第几个。

2. 直接用 % 会出什么问题？

我们直觉上觉得用 x % 3 就可以了，但请看下面的例子：

• 找第 1 个：$1 \% 3 = 1$ $\rightarrow$ 没问题，找第 1 个。
• 找第 2 个：$2 \% 3 = 2$ $\rightarrow$ 没问题，找第 2 个。
• 找第 3 个：$3 \% 3 = \mathbf{0}$ $\rightarrow$ 出问题了！ 我们想要的是“第 3 个”，但结果变成了 0。在 1-based 计数中，0 是没有意义的。
• 找第 4 个：$4 \% 3 = 1$ $\rightarrow$ 没问题，等价于找第 1 个。

核心矛盾： 取模运算 % 的结果范围是 [0, total-1]。 而我们实际想要的结果范围是 [1, total]。 当 $x$ 是 total 的倍数时，直接取模会变成 0，而不是我们期望的 total。

3. 公式的推导：(x - 1) % total + 1

为了解决上面的“0”的问题，我们采用**“减 1，取模，再加 1”**的策略：

1. x - 1：把原本从 1 开始的编号，临时平移变成从 0 开始。
   • 范围从 [1, 2, 3] 变成了 [0, 1, 2]。
2. % total：在从 0 开始的体系下进行取模。
   • 0 的倍数取模后还是 0，这样就顺滑了。
3. + 1：把结果平移回去，变回从 1 开始的编号。

让我们带入刚才出问题的“找第 3 个”试一试：

• $x = 3, total = 3$
• Step 1: $3 - 1 = 2$
• Step 2: $2 \% 3 = 2$
• Step 3: $2 + 1 = \mathbf{3}$
• 结果正确！

再试一下“找第 4 个”：

• $x = 4, total = 3$
• Step 1: $4 - 1 = 3$
• Step 2: $3 \% 3 = 0$
• Step 3: $0 + 1 = \mathbf{1}$
• 结果正确！

4. 总结

在编程中，凡是涉及到循环数组、约瑟夫环、周期性查找等问题，只要下标是从 1 开始计数的，在做“绕圈优化”时，都要使用这个通用公式：

$$\text{等效位置} = (x - 1) \% n + 1$$

对应到这道题的代码：

• $x$ 就是 num[i][cur]（指示牌上的大数字）。
• $n$ 就是 stair_cnt[i]（这一层楼梯的总数）。
• 算出来的 step 就是我们需要在这一层实际寻找的次数（最大不会超过 $M$）。

---

那是不是0开始的就直接%3就可以了？

完全正确！你的直觉非常敏锐。

如果计数是从 0 开始的（例如数组下标 0, 1, 2 ... n-1），那么确实不需要那两个 1，直接取模即可。

这是因为编程语言里的取模运算 %，它的结果范围本来就是 [0, n-1]，这和 0-based（从0开始） 的下标系统是天然契合的。

1. 对比一下就看懂了

假设一圈有 3 个人，我们要找第 x 个人。

情况 A：从 0 开始编号 (0, 1, 2) —— 比如数组下标

直接用 x % 3：

• 第 0 个 $\to 0 \% 3 = \mathbf{0}$ （正确）
• 第 1 个 $\to 1 \% 3 = \mathbf{1}$ （正确）
• 第 2 个 $\to 2 \% 3 = \mathbf{2}$ （正确）
• 第 3 个（回到开头） $\to 3 \% 3 = \mathbf{0}$ （正确）

结论：target = x % n。这是最完美的公式。

情况 B：从 1 开始编号 (1, 2, 3) —— 比如生活中的第几个

如果你还直接用 x % 3：

• 第 1 个 $\to 1 \% 3 = 1$ （正确）
• 第 2 个 $\to 2 \% 3 = 2$ （正确）
• 第 3 个 $\to 3 \% 3 = \mathbf{0}$ （错误！ 我们想要 3，不是 0）

结论：所以必须用 (x - 1) % n + 1 来把结果“强行”修正回 1 到 n 的范围。

---

2. 实战中的应用场景

在 OI 竞赛中，这两种情况你会交替遇到，关键看题目怎么定义：

1. 移动坐标/数组下标：

   • 题目：在一个长度为 $N$ 的环形数组上，从位置 $i$ 往后走 $k$ 步。
   • 因为数组下标是 $0 \sim N-1$，所以新位置就是：

     next_pos = (i + k) % N; 
     

   • 直接模，不需要加减 1。

2. 数数/第几个：

   • 题目：有 $N$ 个人围成一圈，报数，找第 $k$ 个人。
   • 人们习惯说“第 1 个人”，不说“第 0 个人”。
   • 这时候就要用 (k - 1) % N + 1。

3. 一个 C++ 的隐藏坑（负数取模，结果是负数，需要调整为非负数）

虽然 0 开始的时候直接 % 很爽，但在 C++ 中有一个巨大的坑要注意：负数取模。

如果你是往回走（索引减小），或者 $x$ 是负数：

• 在数学上，$-1 \pmod 3 = 2$（倒着退一步就是最后一个）。
• 但在 C++ 中，-1 % 3 的结果是 -1！这会导致数组下标越界。

万能修正公式（防负数）： 不管是从 0 开始往后走还是往前走，最安全的写法是：

// 在 0 ~ n-1 的圈里移动
ans = (x % n + n) % n;

• 如果 $x$ 是正数，+n 再 %n 没影响。
• 如果 $x$ 是负数（比如 -1），-1 + 3 = 2，2 % 3 = 2，这就变成了正确的正数下标。

总结：

• 从 0 开始：直接 % n（如果涉及减法，用 (x % n + n) % n）。
• 从 1 开始：用 (x - 1) % n + 1。

C++ :

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#define N 20123
using namespace std;
int n,m,x;
long long sum;
struct ad
{
	int a[105],b[105];
	int c;
}q[10005];
int main()
{
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		q[i].c=0;
		for(int j=0;j<m;j++)
		{
		  scanf("%d%d",&q[i].a[j],&q[i].b[j]);
		  if(q[i].a[j]!=0) q[i].c++;
		}
	}
	scanf("%d",&x);
	for(int i=1;i<=n;i++)
	{
		sum=(sum+q[i].b[x])%N;
		int j=q[i].b[x]%q[i].c;
		if(j==0)j=q[i].c;
		while(1)
		{			
			if(q[i].a[x])j--;
			if(j==0)break;
			x=(x+1)%m;
		}
		//cout<<x<<' '<<sum<<endl;
	}
	cout<<sum;
	//while(1);
	return 0;
}