Raising Modulo Numbers
求a^b对m取模
思路 ： 快速幂
Raising Modulo Numbers - POJ 1995 - Virtual Judge (vjudge.net)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in = new StreamTokenizer(reader);
static String next() throws IOException {
in.nextToken();
return in.sval;
}
/**
* 获取数字
*/
static int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public static void main(String[] args) throws IOException {
numbers();
}
public static void numbers() throws IOException {
int n = nextInt();
for (int i = 0; i < n; i++) {
int m = nextInt();
int num = nextInt();
int ans = 0;
for (int j = 0; j < num; j++) {
int a = nextInt();
int b = nextInt();
int solved = solved(a, b, m);
ans = (ans + solved) % m;
}
System.out.println(ans);
}
}
public static int solved(long a, long b, int m) {
if (a == 0 || a == 1) {
return (int) a;
}
if (b == 0) {
return 1;
}
long ans = 1;
while (b > 0) {
if ((b & 1) == 1) {
ans = ans * a % m;
}
a = a * a % m;
b >>= 1;
}
return (int) ans;
}
}
类似题 ： 剑指 Offer 16. 数值的整数次方 - 力扣（LeetCode）
public double myPow(double x, int n) {
if (x == 0 || x == 1) {
return x;
}
if (n == 0) {
return 1;
}
double ans = 1.0;
long b = Math.abs((long) n);
while (b > 0) {
if ((b & 1) == 1) {
ans = ans * x;
}
x *= x;
b >>= 1;
}
return n > 0 ? ans : 1 / ans;
}
最短Hamilton路径
暴力枚举时间复杂度O(n*n!)
思路：二进制状态压缩 O(n^2 * 2^n)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in = new StreamTokenizer(reader);
static String next() throws IOException {
in.nextToken();
return in.sval;
}
/**
* 获取数字
*/
static int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public static void main(String[] args) throws IOException {
hamilton();
}
static int N, M;
static int f[][];
static void hamilton() throws IOException {
N = nextInt();
M = 1 << N;
f = new int[M][N];
for (int i = 0; i < f.length; i++) {
for (int i1 = 0; i1 < f[i].length; i1++) {
f[i][i1] = Integer.MAX_VALUE>>1; //防止溢出
}
}
f[1][0] = 0;
int[][] w = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
w[i][j] = nextInt();
}
}
for (int i = 1; i < M; i++) {
for (int j = 0; j < N; j++) {
if (((i >> j) & 1) == 1) {
for (int k = 0; k < N; k++) {
if ((((i ^ (1 << j)) >> k) & 1) == 1) {
f[i][j] = Math.min(f[i][j], f[i ^ (1 << j)][k] + w[k][j]);
}
}
}
}
}
System.out.println(f[M - 1][N - 1]);
}
}
起床困难综合症
[P2114 NOI2014] 起床困难综合症 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
package Uva.basic;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in = new StreamTokenizer(reader);
static String next() throws IOException {
in.nextToken();
return in.sval;
}
/**
* 获取数字
*/
static int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}
public static void main(String[] args) throws IOException {
getUp();
}
static Node[] nodes;
public static void getUp() throws IOException {
int n = nextInt();
int m = nextInt();
nodes = new Node[n];
for (int i = 0; i < n; i++) {
String s = next();
int val = nextInt();
int type = s.equals("AND") ? 1 : (s.equals("OR") ? 2 : 3);
nodes[i] = new Node(type, val);
}
int ans = 0, val = 0;
for (int i = 30; i >= 0; i--) {
int res0 = cal(i, 0);
int res1 = cal(i, 1);
if (val + (1 << i) <= m && res0 < res1) {
ans += 1 << i;
val += 1 << i;
} else {
ans += res0 << i;
}
}
System.out.println(ans);
}
public static int cal(int bit, int now) {
for (int i = 0; i < nodes.length; i++) {
int x = nodes[i].val >> bit & 1;
if (nodes[i].type == 1) {
now &= x;
} else if (nodes[i].type == 2) {
now |= x;
} else {
now ^= x;
}
}
return now;
}
static class Node {
int type;
int val;
public Node(int type, int val) {
this.type = type;
this.val = val;
}
}
}
成对变换
通过计算可以发现，对于非负整数n:
当n为偶数时，n xor 1等于n ＋ 1。
当n为奇数时，n xor 1等于n 一1。
因此，“0与1” “2与3” “4与5”…关于 xor 1运算构成“成对变换”。
这一性质经常用于图论邻接表中边集的存储。在具有无向边(双向边)的图中把一对正反方向的边分别存储在邻接表数组的第n 与n＋1位置（其中n为偶数)，就可以通过xor 1的运算获得与当前边(x,y)反向的边(y,x)的存储位置。
lowbit运算
lowbit(x)是x的二进制表达式中最低位的1所对应的值
lowbit(n) = n & (~n ＋1) =n & (-n)