法法【牛客tracker 每日一题】

法法

时间限制：1秒 空间限制：256M

知识点：枚举

题目描述

设A AA是一个1 ∼ n 1∼n1∼n的排列，其中第i ii项为A i A_iAi​

设f ( A ) = A 1 A 2 A 3 ⋯ A n f(A)=A_1^{{{{A_2}^{A_3}}^{⋯}}^{A_n}}f(A)=A1A2​A3​⋯An​​

换句话说：

f ( A 1 , A 2 , A 3 , … , A n ) = { A 1 , x = 1 A 1 f ( A 2 , A 3 , … , A n ) , x > 1 f({A_1,A_2,A_3,…,A_n})= \begin{cases} A_1, \quad x=1\\ A_1^{f({A_2,A_3,…,A_n})}, \quad x>1 \end{cases}f(A1​,A2​,A3​,…,An​)={A1​,x=1A1f(A2​,A3​,…,An​)​,x>1​

求1 ∼ n 1∼n1∼n的全排列的f ff的和

答案对2 22取模

输入描述：

第一行输入一个整数T TT，表示数据组数
之后T TT行，第i + 1 i+1i+1行有一个整数n i n_ini​，表示第i ii次询问

输出描述：

一共T TT行，第i ii行有1 11个整数，表示第i ii次询问的答案

示例1

输入：

1 3

输出：

0

说明：

1 ( 2 3 ) = 1 1^{(2^3)}=11(23)=1
1 ( 3 2 ) = 1 1^{(3^2)}=11(32)=1
2 ( 1 3 ) = 2 2^{(1^3)}=22(13)=2
2 ( 3 1 ) = 8 2^{(3^1)}=82(31)=8
3 ( 1 2 ) = 3 3^{(1^2)}=33(12)=3
3 ( 2 1 ) = 9 3^{(2^1)}=93(21)=9

备注：

数据范围
1 ≤ n ≤ 10 18 1 ≤ n ≤ 10^{18}1≤n≤1018
1 ≤ T ≤ 10 1 ≤ T ≤ 101≤T≤10

解题思路

本题核心是数论规律推导 + 模运算简化，无需暴力枚举全排列（n nn极大无法枚举），直接通过奇偶性分析得出答案。由于答案对2 22取模，仅需判断数值的奇偶性：

1. 幂塔运算模2 22性质：奇数的任意次幂为1 11，偶数的正整数次幂为0 00；
2. 分类讨论：n = 1 n=1n=1时，唯一排列结果为1 11，总和模2 = 1 2=12=1；n = 2 n=2n=2时，两个排列结果之和为1 11，模2 = 1 2=12=1；
3. 当n ≥ 3 n≥3n≥3时，1 ˜ n 1 \~\ n1˜n的全排列中，所有幂塔结果的总和恒为偶数，模2 22结果为0 00。
   基于此规律直接输出答案，时间复杂度O ( 1 ) O(1)O(1)，完美适配n ≤ 10 18 n≤10^{18}n≤1018的超大数据范围。

总结

核心逻辑：利用模2 22运算的奇偶性简化幂塔计算，推导得出固定规律：n < 3 n<3n<3答案为1 11，n ≥ 3 n≥3n≥3答案为0。
关键操作：数论性质分析、超大数规律直接判定。
效率保障：常数级时间复杂度，轻松处理10 18 10^{18}1018范围的输入。

代码内容

#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;intmain(){ll t;cin>>t;while(t--){ll n;cin>>n;cout<<"01"[n<3]<<endl;}return0;}