我不是大富翁【牛客tracker 每日一题】

我不是大富翁

时间限制：2秒 空间限制：128M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

提到大富翁游戏！就想到环！！就想到经典的约瑟夫问题！！！作为经典问题，其出彩的展示了数学思维在实际问题中的应用，启发了一代又一代的算竞人。
好了，不要再约瑟夫了，都是经典问题害的你，没法正常的玩大富翁游戏。现在，让我们来愉快的玩大富翁吧！

R a b b i t RabbitRabbit拿到了一张环形的大富翁地图，地图被平均划分为了n nn个地块，地块的编号以1 11为起点，顺时针进行排布。即1 11号地块的顺时针方向依次为2 , 3 , … … 2, 3, ……2,3,……号地块；1 11号地块的逆时针方向依次为n , n − 1 , … … n , n−1, ……n,n−1,……号地块（由于是环形的，所以1 11号地块与n nn号地块相邻，如下图所示）。

游戏过程如下：系统会给定一个长度为m mm的行动力序列a 1 , a 2 , … , a m a_1,a_2,…,a_ma1​,a2​,…,am​，在第i ( 1 ≦ i ≦ m ) i (1≦i≦m)i(1≦i≦m)回合，R a b b i t R RabbitRRabbitR都需要移动a i a_iai​个地块，但是他可以自由选择移动的方向（换句话说，可以自由选择是向逆时针还是顺时针方向移动a i a_iai​个地块）。
在游戏的开始时，R a b b i t RabbitRabbit位于1 11号地块，他想知道是否存在这样一种移动方式，使得m mm个回合后他依旧在1 11号地块。

输入描述：

每个测试文件仅有一组测试数据。
第一行输入两个整数n nn和m ( 1 ≦ n , m ≦ 5000 ) m (1≦n, m≦5000)m(1≦n,m≦5000)表示地块数量和行动回合数。
第二行输入m mm个整数a 1 , a 2 , … , a m ​ ( 0 ≦ a i ≦ 2 ⋅ 10 5 ) a_1,a_2,…,a_m​ (0≦a_i≦2⋅10^5)a1​,a2​,…,am​​(0≦ai​≦2⋅105)表示行动力序列。

输出描述：

如果m mm个回合后R a b b i t RabbitRabbit依旧在1 11号地块，则输出Y E S YESYES；否则，请输出N O NONO。您可以以任何大小写形式输出答案，例如，y E s 、 y e s yEs 、yesyEs、yes和Y e S YeSYeS都将被视为肯定的回答。

示例1

输入：

360 3 120 120 120

输出：

YES

示例2

输入：

50 5 30 0 10 10 10

输出：

yES

示例3

输入：

114 5 14 1 9 1 9

输出：

no

备注：

如果您需要使用P y t h o n PythonPython解题，我们建议您在提交时选择p y p y 2 pypy2pypy2或p y p y 3 pypy3pypy3。

解题思路

本题是环形可达性动态规划的经典模型，核心是逐回合维护可能停留的位置集合，利用模运算处理环形移动，最终检查起点是否仍在集合中。

1. 问题等价转化

• 环形地块：n nn个地块编号1 ∼ n 1 \sim n1∼n，顺时针移动加、逆时针移动减。将地块编号改为0 ∼ n − 1 0 \sim n-10∼n−1（起点变为0 00），移动后的位置用模n nn运算表达。
• 方向选择：每回合给定步数a i a_iai​，可以选择+ a i +a_i+ai​或− a i -a_i−ai​，即下一位置为( c u r r e n t + a i ) m o d n (current + a_i) \bmod n(current+ai​)modn或( c u r r e n t − a i ) m o d n (current - a_i) \bmod n(current−ai​)modn（确保非负）。
• 可达性状态：记第i ii回合后可能位于哪些地块。初始仅在0 00号地块。若最终0 00号地块可达，则答案为YES。

2. 算法实现：逐回合 DP

1. 状态表示：用一个布尔数组x表示当前回合可能的位置，长度n nn，x[pos]=1表示可以到达该位置。初始x[0]=1。
2. 状态转移：
   • 每回合新建布尔数组t（全零），遍历j ∈ [ 0 , n − 1 ] j \in [0, n-1]j∈[0,n−1]，若x[j]==1，则将t[(j + a[i]) % n]和t[(j - a[i] % n + n) % n]置为 1。
   • 用t替换x，进入下一回合。
3. 结果判定：m mm回合后，若x[0]为真则输出YES，否则输出NO。

3. 复杂度分析

• 时间复杂度：O ( n × m ) O(n \times m)O(n×m)。n , m ≤ 5000 n, m \le 5000n,m≤5000，最大操作次数约2.5 × 10 7 2.5 \times 10^72.5×107，在 2 秒时限内可行。
• 空间复杂度：O ( n ) O(n)O(n)，两个长度为n nn的布尔数组滚动使用。

总结

将环形移动转化为模n nn的加减操作，用逐回合 DP 维护所有可能到达的位置集合。由于n , m n, mn,m不大，直接模拟所有可能路径即可，无需贪心或数学构造。

代码简要说明

1. 输入处理：读入n , m n, mn,m和行动力数组a aa。
2. DP 数组初始化：vector<ll> x(n)作为当前回合可达状态，x[0]=1表示起点。
3. 逐回合转移：
   • 创建临时数组t(n)。
   • 遍历j jj，若x[j]==1，计算(j + a[i]) % n和((j - a[i]) % n + n) % n，在t中标记。
   • swap(x, t)更新状态。
4. 结果输出：检查x[0]的值，输出YES或NO。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;voidS(){ll n,m;cin>>n>>m;vector<ll>a(m);for(ll i=0;i<m;i++)cin>>a[i];vector<ll>x(n);x[0]=1;for(ll i=0;i<m;i++){vector<ll>t(n);for(ll j=0;j<n;j++){if(x[j]==1){t[(j+a[i])%n]=1;t[((j-a[i])%n+n)%n]=1;}}swap(x,t);}if(x[0])cout<<"YES\n";elsecout<<"NO\n";}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T=1;while(T--)S();return0;}