digiter
- 浏览: 118644 次
- 性别:
- 来自: 北京
-
最新评论
文章列表
写了两三个版本，最后这个效率最高
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " & ...
源自http://watashi.ws/blog/1515/zojmonthly1010/
inline long long mul(long long lhs, long long rhs) {
long long lhs2 = lhs % 100000;
long long rhs2 = rhs % 100000;
return ((lhs / 100000 * rhs2 + rhs / 100000 * lhs2) * 100000 + lhs2 * rhs2) % MOD;
}
import java.util.*;
import java.io.*;
import java.math.*;
class Fraction {
BigInteger a = BigInteger.ZERO, b = BigInteger.ONE;
Fraction() { }
Fraction(BigInteger a, BigInteger b)
{
BigInteger d = a.gcd(b);
a = a.divide(d); b = b.divide(d);
if (b.c ...
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " << (v) <& ...
// Treap
// Tested: bjtu1057, hdu1004, pku1002
typedef int KEY;
typedef int VALUE;
struct node_t {
int ch[2], pr;
KEY key;
VALUE value;
} T[maxn];
int size; // init: size = 0
int new_node() {
T[size].ch[0] = T[size].ch[1] = -1, T[size].pr = rand();
return size++;
}
struct treap_t ...
typedef LL matrix[55][55];
void ident(int size, matrix x)
{
for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j)
x[i][j] = (i == j ? 1 : 0);
}
void copy(int size, matrix x, matrix y)
{
for (int i = 0; i < size; ++i)
for (int j = 0; j ...
最大团模板
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#define out(v) cout << #v << ": " << (v) << endl
#defin ...
计算Jacobi符号
- 博客分类：
- ICPC
Quadratic reciprocity
The Jacobi symbol, (m/n), is defined whenever n is an odd number. It has the following properties that enable it to be easily computed.
* (a/n) = (b/n) if a = b mod n.
* (1/n) = 1 and (0/n) = 0.
* (2m/n) = (m/n) if n = ±1 mod 8. Otherwise (2m/n) = -(m/n).
* (Qua ...
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader 可以 read 读入一个字符 或者 readLine 读入一行
BufferedWriter 可以 write 写一个字符、一个字符串 或者 newLine 结束一行，flush 刷新缓冲区
标准数独，精确覆盖
// pku3076.cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": ...
“精确覆盖”问题
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " << ...
“多重覆盖”或“重复覆盖”问题
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v &l ...
推导公式的题目，矩阵幂关键就在于构造系数矩阵
备忘：
S(n, k) - S(n - 1, k) = Fn ^ k
当Fn能够线性表示的时候，S(n, k) = S(n - 1, k) + Fn ^ k 不也是线性表示嘛!
Fn ^ k = sigma( C(k, i) * a^i * b^(k-i) * Fn-1^i * Fn-2^(k-i) ) 其中0 <= i <= k
备忘2：
构造矩阵系数的时候，要用 += 把相应的项的系数加上去，而不是直接 =
备忘3：
快速幂的复杂度很低，所以基本不用考虑常数
#include <cstdio>
#inclu ...
/*
* Author: rush
* Created Time: 2010年07月28日 星期三 09时29分05秒
* File Name: icpc/hdu3486.cpp
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <ma ...
// bjtu1394.cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " & ...