ACM模板

ACM模板

构建一下自己的模板吧，不然不常用的又忘了。

树状数组

struct BIT {///树状数组 ll c[maxn]; void add(int x,ll d){ while(x<=n+1){ c[x]+=d; c[x]%=MOD; x+=lowbit(x); } } ll query(int x){ ll ans=0; while(x){ ans+=c[x]; ans%=MOD; x-=lowbit(x); } return ans; }}bit;

字典树

struct Trie { //定义名为 Trie 的结构体类型 int sz; //节点编号 Trie() { sz = 1; //初始化 memset(ch[0], 0, sizeof(ch[0])); } int idx(char c) { return c - 'a'; //返回字母 c 的序值 } void insert(char *s) { //构造单词*s 对应的 Trie 树 int u = 0, n = strlen(s); //根节点编号为 0，计算字符串 s 的长度 n for(int i = 0; i < n; i++) { //依次插入字串的每一个字母 int c = idx(s[i]); //计算第 i 个字母的序值 if(!ch[u][c]) { //若节点 u 编号为 c 的子节点空 memset(ch[sz], 0, sizeof(ch[sz])); //节点 sz 为叶节点 val[sz] = 0; //sz 的访问次数为 0 ch[u][c] = sz++; //sz 设为节点 u 编号为 c 的子节点，设 下一个节点编号 sz++ } u = ch[u][c]; //取节点 u 序值为 c 的子节点编号，该节点的访问次数+1 val[u]++; } } void query(char *s) { //计算和输出单词*s 的最短前缀 int u = 0, n = strlen(s); //从根出发，计算单词*s 的长度 for(int i = 0; i < n; i++) { //依次搜索*s 的每个字母 putchar(s[i]); //第 i 个字母作为前缀字符输出 int c = idx(s[i]); //计算第 i 个字母的序数值 c if(val[ch[u][c]] == 1) return ; //若 u 的序数值 c 的子节点仅被访问一次，则退出 u = ch[u][c]; //继续沿序数值 c 的子节点搜索下去 } }};

组合数

ll fac[maxn];void init(){ fac[0] = 1; for(int i = 1; i < maxn; i++) { fac[i] = fac[i - 1] * i % mod; }}ll infac(ll x){ return qpow(x, mod - 2, mod);}ll C(ll n, ll m){ if(n < m) return 0; return fac[n] * infac(fac[m]) % mod * infac(fac[n - m]) % mod;}

素数筛

int cnt;int prime[maxn];bool isprime[maxn];void Prime(){ for(int i=2;i

FFT

#include using namespace std;typedef pairPII;const int N = 2e5 + 7, mod = 1e9 + 7;const double PI = acos(-1.0);struct Complex{ double x, y; Complex (double x = 0, double y = 0) : x(x), y(y) { } Complex operator + (const Complex &t) { return Complex (x + t.x, y + t.y); } Complex operator - (const Complex &t) { return Complex (x - t.x, y - t.y); } Complex operator * (const Complex &t) { return Complex (x * t.x - y * t.y, x * t.y + y * t.x); }}A[N], B[N], C[N];void FFT(Complex *A, double type){ for(int i = 0; i < limit; ++ i) if(i < RR[i]) swap(A[i], A[RR[i]]); for(int mid = 1; mid < limit; mid <<= 1) { Complex wn(cos(PI / mid), type * sin(PI / mid)); for(int len = mid << 1, pos = 0; pos < limit; pos += len) { Complex w(1, 0); for(int k = 0; k < mid; ++ k, w = w * wn) { Complex x = A[pos + k]; Complex y = w * A[pos + mid + k]; A[pos + k] = x + y; A[pos + mid + k] = x - y; } } } if(type == -1) { for(int i = 0; i <= limit; ++ i) A[i].x /= limit; }}//a'[i] = a[n - 1 - i];int main(){ scanf("%d", &n); for(int i = 0; i < n; ++ i) { int x, y; scanf("%d%d", &x, &y); A[n - 1 - i].x = x; B[i].x = y; } L = 0, limit = 1; while(limit <= n * 2) limit <<= 1, L ++ ; for(int i = 0; i < limit; ++ i) { RR[i] = (RR[i >> 1] >> 1) | ((i & 1) << (L - 1)); } FFT(A, 1), FFT(B, 1); for(int i = 0; i < limit; ++ i) { C[i] = A[i] * B[i]; } FFT(C, -1); for(int i = n - 1; i >= 0; -- i) { printf("%d\n", (int)(C[i].x + 0.5)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。