逃跑路线【牛客tracker 每日一题】
逃跑路线
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
“没想到吧J O J O JOJOJOJO，这就是我的逃跑路线！”
已知牛牛从( 0 , 0 ) (0,0)(0,0)点开始进行n nn次逃跑，每次逃跑都是沿着x轴正半轴方向移动。若第i ii次逃跑前的坐标是( x 0 , 0 ) (x_0,0)(x0,0)，逃跑的距离是a [ i ] a[i]a[i]，那么第i ii次逃跑后牛牛的位置就到达了( x 0 + a [ i ] , 0 ) (x_0+a[i],0)(x0+a[i],0)。请问牛牛进行完nn次逃跑后，横坐标& ( 2 1 − 1 ) & ( 2 2 − 1 ) & … & ( 2 n − 1 ) \&(2^1−1)\&(2^2−1)\&…\&(2^n−1)&(21−1)&(22−1)&…&(2n−1)的值是多少，& \&&为与运算。
输入描述：
第一行一个正整数n nn，其中n ≤ 100 n≤100n≤100。
接下来n nn行，每行一个正整数a [ i ] a[i]a[i]，a [ i ] ≤ 10 10000 a[i]≤10^{10000}a[i]≤1010000，数据中不会有前导零。
输出描述：
输出牛牛进行完n nn次逃跑后，横坐标& ( 2 1 − 1 ) & ( 2 2 − 1 ) & … & ( 2 n − 1 ) \&(2^1-1)\&(2^2-1)\&…\&(2^n-1)&(21−1)&(22−1)&…&(2n−1)的值。
示例1
输入：
3 1 2 1输出：
0解题思路
本题核心是数学公式化简 + 大数奇偶性判断，规避超大数求和的复杂运算。首先化简连续与运算：( 2 1 − 1 ) & ( 2 2 − 1 ) & … & ( 2 n − 1 ) = 1 (2^1-1) \& (2^2-1) \& \dots \& (2^n-1) = 1(21−1)&(22−1)&…&(2n−1)=1，因此最终答案等价于总位移和的奇偶性（总和对 2 取模）。由于输入的a [ i ] a[i]a[i]是长度高达10 4 10^4104的超大数，无法直接存储求和，而一个数的奇偶性仅由最后一位数字决定，因此只需读取每个数字的最后一位，累加所有最后一位的值后对 2 取模，结果即为答案。算法时间复杂度O ( 总数字长度 ) O(\text{总数字长度})O(总数字长度)，极简高效，完美适配超大数的输入约束。
总结
核心逻辑：连续与运算化简为 1，问题转化为求总和的奇偶性；大数奇偶性仅看最后一位。
关键操作：提取每个超大数的最后一位、累加取模 2。
效率保障：无需处理完整大数，仅操作最后一位，计算量极小，无超时风险。
代码内容
#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;llread(){ll s=0,bj=0;charch=getchar();while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();returnbj?-s:s;}voidprintnum(ll x){if(x>9)printnum(x/10);putchar(x%10^48);}voidprint(ll x,charch){if(x<0){putchar('-');x=-x;}printnum(x);putchar(ch);}ll n;ll l;charc[10005];ll s;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);n=read();for(ll i=1;i<=n;i++){scanf("%s",c+1);l=strlen(c+1);s=(s+c[l]-'0')%2;}print(s,'\n');return0;}