Bzoj 近期题目题解

Bzoj 近期题目题解

Bzoj的简单题.我做过的题目.

1000: A+B Problem (模拟)

copy下面即可

#include <iostream>

using namespace std;

int  main()

{

    int a,b;

    cin >> a >> b;

    cout << a+b << endl;

    return 0;

}

1008: [HNOI2008]越狱 (容斥)

容斥一下就好了.注意有负数

// luogu-judger-enable-o2

#include <iostream>

#include <cstdio>

using namespace std;

long long fast_power(long long a,long long b,long long mod) {

    long long ans = 1;

    for(long long now = a;b;b >>= 1,now = now * now % mod) {

        if(b & 1) ans = ans * now % mod;

    }

    return ans % mod;

}

int main() {

    long long n,m;

    scanf("%lld%lld",&m,&n);

    printf("%lld",(fast_power(m,n,100003) - m * fast_power(m - 1,n - 1,100003) % 100003  + 100003) % 100003);

    return 0;

}

1012: [JSOI2008]最大数maxnumber (线段树)

线段树提前开好空间,编号依次往后挪就好了.

#include <iostream>

#include <cstdio>

#define ll long long

const ll maxN = 200000 + 7;

char s[3];

struct Node {

    ll l,r,maxx;

}tree[maxN << 2];

ll max(ll x,ll y) {

    return x > y ? x : y;

}

void updata(ll now) {

    tree[now].maxx = max(tree[now << 1].maxx,tree[now << 1 | 1].maxx);

    return ;

}

inline ll read() {

    ll x = 0,f = 1;char c = getchar();

    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}

    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}

    return x * f;

}

void build(ll l,ll r,ll now) {

    tree[now].l = l;tree[now].r = r;

    if(l == r) {tree[now].maxx = -0x7fffffff;return;}

    ll mid = (l + r) >> 1;

    build(l,mid,now << 1);

    build(mid + 1,r,now << 1 | 1);

    updata(now);

    return;

} 

void change(ll pos,ll val,ll now) {

    if(tree[now].l == tree[now].r) {

        tree[now].maxx = val;

        return;

    }

    ll mid = (tree[now].l + tree[now].r) >> 1;

    if(pos <= mid) change(pos,val,now << 1);

    else change(pos,val,now << 1 | 1);

    updata(now);

    return ;

}

ll query(ll l,ll r,ll now) {

    if(tree[now].l >= l && tree[now].r <= r) {

        return tree[now].maxx;

    }

    ll maxx = -0x7fffffff;

    ll mid = (tree[now].l + tree[now].r) >> 1;

    if(l <= mid)  maxx = max(maxx,query(l,r,now << 1));

    if(r > mid) maxx = max(maxx,query(l,r,now << 1 | 1));

    return maxx;

}

int main() {

    ll n,P;

    scanf("%lld%lld",&n,&P);

    char c;

    ll pos = 0,t = 0;

    build(1,n,1);

    for(ll i = 1,x;i <= n;++ i) {

        scanf("%s%lld",&s,&x);

        if(s[0] == 'A') {

            ll tmp = ( (x % P) + t % P ) % P;

            ++ pos;

            change(pos,tmp,1);

        }

        else {

            t = query(pos - x + 1,pos,1);

            printf("%lld\n",t);

        }

    }

    return 0;

}

1034: [ZJOI2008]泡泡堂BNB (贪心)

贪心即可.



#include <iostream>

#include <cstdio>

#include <algorithm>

#define X 100007

int n;

int work(int a[],int b[])

{

    int la = 1,lb = 1,ra = n,rb = n,ans = 0;

    while(la <= ra && lb <= rb)

    {

        if(a[la] > b[lb])++ la,++ lb,ans += 2;

        else if(a[ra] > b[rb])-- ra,-- rb,ans += 2;

        else{

            if(a[la] == b[rb])ans ++;

            ++ la,-- rb;

        }

    }

    return ans;

}

int a[X],b[X];

int main(){

    scanf("%d",&n);

    for(int i = 1;i <= n;++ i)

        scanf("%d",&a[i]);

    for(int i = 1;i <= n;++ i)

        scanf("%d",&b[i]);

    std::sort(a + 1,a + n + 1);

    std::sort(b + 1,b + n + 1);

    int ans = work(a,b);

    printf("%d %d",ans,2 * n - work(b,a));

}

1036: [ZJOI2008]树的统计Count (树链剖分)

树链剖分模板题.

// luogu-judger-enable-o2

#include <iostream>

#include <cstdio>

const int maxN = 3e5 + 7;

using namespace std;

int pos[maxN],top[maxN],size[maxN],dep[maxN],fa[maxN];

int head[maxN],a[maxN],n,m,cut,maxsize;

struct Node{

    int l,r,sum,max;

}tree[maxN << 2];

struct edge{

    int v,nex;

}e[maxN << 1];

inline int read() {

    int x = 0,f = 1;char c = getchar();

    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}

    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}

    return x * f;

}

void add(int u,int v) {

    e[++ cut].nex = head[u];

    head[u] = cut;

    e[cut].v = v;

}

void build(int l,int r,int now) {

    tree[now].l = l;tree[now].r = r;

    if(l == r) {

        tree[now].max = tree[now].sum = 0;

        return;

    }

    int mid = (l + r) >> 1;

    build(l,mid,now << 1);

    build(mid + 1,r,now << 1 | 1);

    return;

}

void dfs1(int u) {

    size[u] = 1;

    for(int i = head[u];i;i = e[i].nex ) {

        int v = e[i].v;

        if(v == fa[u]) continue;

        fa[v] = u;dep[v] = dep[u] + 1;

        dfs1(v);

        size[u] += size[v];

    }

    return;

}

void dfs2(int u,int top1) {

    int k = 0;

    maxsize ++;

    pos[u] = maxsize;

    top[u] = top1;

    for(int i = head[u];i;i = e[i].nex) {

        int v = e[i].v;

        if(dep[v] > dep[u] && size[k] < size[v]) k = v;

    }

    if( !k )return;

    dfs2(k,top1);

    for(int i = head[u];i;i = e[i].nex) {

        int v = e[i].v;

        if(v != k && dep[v] > dep[u]) {

            dfs2(v,v);

        }

    }

    return;

} 

void change(int now,int pos,int val) {

    if(tree[now].l == tree[now].r) {

        tree[now].sum = tree[now].max = val;

        return;

    }

    int mid = (tree[now].l + tree[now].r) >> 1;

    if(pos <= mid) change(now << 1,pos,val);

    if(pos > mid) change(now << 1 | 1,pos,val);

    tree[now].sum = tree[now << 1].sum + tree[now << 1 | 1].sum;

    tree[now].max = max(tree[now << 1].max,tree[now << 1 | 1].max);

    return;

}

int querysum(int now,int l,int r) {

    if(tree[now].l >= l && tree[now].r <= r) return tree[now].sum;

    int mid = (tree[now].l + tree[now].r) >> 1;

    int Ans = 0;

    if(l <= mid) Ans += querysum(now << 1,l,r);

    if(r > mid) Ans += querysum(now << 1 | 1,l,r);

    return Ans;

} 

int querymax(int now,int l,int r) {

    if(tree[now].l >= l && tree[now].r <= r) return tree[now].max;

    int mid = (tree[now].l + tree[now].r) >> 1,total = -1e9;

    if(l <= mid) total = max(total,querymax(now << 1,l,r));

    if(r > mid) total = max(total,querymax(now << 1 | 1,l,r));

    return total;

}

int slovemax(int x,int y) {

    int ans = -1e9;

    while(top[x] != top[y]) {

        if(dep[top[x]] < dep[top[y]]) swap(x,y);

        ans = max(ans,querymax(1,pos[top[x]],pos[x]));

        x = fa[top[x]];

    }

    if(pos[x] > pos[y]) swap(x,y);

    ans = max(ans,querymax(1,pos[x],pos[y]));

    return ans;

}

int slovesum(int x,int y) {

    int ans = 0;

    while(top[x] != top[y]) {

        if(dep[top[x]] < dep[top[y]]) swap(x,y);

        ans += querysum(1,pos[top[x]],pos[x]);

        x = fa[top[x]];

    }

    if(pos[x] > pos[y]) swap(x,y);

    ans += querysum(1,pos[x],pos[y]);

    return ans;

}

int main() {

//	freopen("1.in","r",stdin);

//	freopen("1.out","w",stdout);

    int x,y;

    n = read();

    for(int i = 1;i < n;++ i) {

        x = read();y = read();

        add(x,y);add(y,x);

    }

    for(int i = 1;i <= n;++ i)

        a[i] = read();

    dfs1(1);dfs2(1,1);

    build(1,maxsize,1);

    for(int i = 1;i<= n;++ i)

        change(1,pos[i],a[i]);

    m = read();char ch[11];

    while(m -- ) {

        scanf("%s",ch);

        scanf("%d%d",&x,&y);

        if(ch[0] == 'C') change(1,pos[x],y);

        else {

            if(ch[1] == 'M') printf("%d\n",slovemax(x,y));

            else printf("%d\n",slovesum(x,y));

        }

    }

}

1051: [HAOI2006]受欢迎的牛 (tarjan)

tarjan 缩点,被所有牛指向的就是受欢迎的牛们

#include <iostream>

#include <cstdio>

#define max(a,b) a > b ? a : b

#define min(a,b) a > b ? b : a

const int maxN = 10000 + 7;

const int maxM = 50000 + 7;

int dfn[maxN],low[maxN];

int cnt;//时间戳

int belong[maxN],num;//锁点

int ska[maxN],top; //栈

int cu[maxN];

int Size[maxN];

inline int read() {

    int x = 0,f = 1;char c = getchar();

    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}

    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}

    return x * f;

}

struct Node{

    int v,nex;

}Map[maxM];

int head[maxN],G;

inline void add_Node(int u,int v) {

    Map[++ G] = (Node) {v,head[u]};

    head[u] = G;

}

void dfs(int u) {

    dfn[u] = low[u] = ++ cnt;

    ska[++ top] = u;

    for(int i = head[u];i;i = Map[i].nex) {

        int v = Map[i].v;

        if(!dfn[v]) {

            dfs(v);

            low[u] = min(low[u],low[v]);

        }else if(!belong[v]) low[u] = min(low[u],dfn[v]);

    }

    if(dfn[u] == low[u]) {

        num ++;

        while(ska[top] != u) belong[ska[top --]] = num,Size[num] ++;

        belong[ska[top --]] = num;

        Size[num] ++;

    }

}

int main() {

    int n,m;

    scanf("%d%d",&n,&m);

    int u,v;

    for(int i = 1;i <= m;++ i) {

        scanf("%d%d",&u,&v);

        add_Node(u,v);

    }

    for(int i = 1;i <= n;++ i)

        if(!dfn[i]) dfs(i);

    for(int i = 1;i <= n;++ i) {

        int bel = belong[i];

        for(int j = head[i];j;j = Map[j].nex) {

            int v = Map[j].v;

            int belv = belong[v];

            if(belv != bel) cu[bel] ++;

        }

    }

    int tmp = 0,id;

    for(int i = 1;i <= num;++ i) {

        if(!cu[i]) tmp ++,id = i;

    }

    if(tmp > 1) return puts("0"),0;

    printf("%d",Size[id]);

    return 0;

}

1059: [ZJOI2007]矩阵游戏 (二分图匹配)

二分图匹配,将行,列中的黑白子连边.

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

const int maxN = 2000 + 7;

const int maxM = 2000000 + 7;

const int inf = 0x7fffffff;

using namespace std;

int f[507][507];

struct Node {

    int v,nex,w;

}map[maxM];

int dep[maxN],head[maxN],S,t,num,n,maxsize;

int id[maxN];

inline int read() {

    int x = 0,f = 1;char c = getchar();

    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}

    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}

    return x * f;

}

void init() {

    maxsize = 0;

    num = -1;

    memset(head,-1,sizeof(head));

    return;

}

void add_Node(int u,int v,int w) {

    map[++ num].v = v;

    map[num].w = w;

    map[num].nex = head[u];

    head[u] = num;

    return ;

}

void add(int u,int v,int w) {

    add_Node(u,v,w);

    add_Node(v,u,0);

}

bool bfs() {

    queue<int>q;

    memset(dep,0,sizeof(dep));

    while(!q.empty()) q.pop();

    q.push(S);

    dep[S] = 1;

    do{

        int u = q.front();

        q.pop();

        for(int i = head[u];i != -1;i = map[i].nex) {

            int v = map[i].v;

            if( !dep[v] && map[i].w) {

                q.push(v);

                dep[v] = dep[u] + 1;

            }

        }

    }while(!q.empty());

    if(dep[t]) return true;

    return false;

}

int min(int a,int b) {

    return a > b ? b : a;

}

int dfs(int now,int dist) {

    if(now == t) return dist;

    for(int i = head[now];i != -1;i = map[i].nex) {

        int v = map[i].v;

        if(dep[v] == dep[now] + 1 && map[i].w) {

            int di = dfs(v,min(dist,map[i].w));

            if(di) {

                map[i].w -= di;

                map[i ^ 1].w += di;

                return di;

            }

        }

    }

    return 0;

}

void Dinic() {

    int Ans = 0;

    while(bfs()) {

        while(int d = dfs(S,inf)) {

            Ans += d;

        }

    }

    if(Ans == n) puts("Yes");

    else puts("No");

    return;

}

int main() {

    int T;

    T = read();

    while(T --) {

        init();

        n = read();

        for(int i = 1;i <= n;++ i)

            for(int j = 1;j <= n;++ j)

                f[i][j] = read();

        S = ++ maxsize;

        for(int i = 1;i <= n;++ i)

            id[i] = ++ maxsize;

        for(int i = 1;i <= n;++ i)

            id[n + i] = ++ maxsize;

        t = ++ maxsize;

        for(int i = 1;i <= n;++ i)

            add(S,id[i],1);

        for(int i = 1;i <= n;++ i)

            add(id[i + n],t,1);

        for(int i = 1;i <= n;++ i)

            for(int j  = 1;j <= n;++ j)

                if(f[j][i]) add(id[j],id[i + n],1);

        for(int i = 1;i <= n;++ i)

            for(int j = 1;j <= n;++ j)

                if(f[i][j]) add(id[i],id[j + n],1);

        Dinic();

    }

}

1355: [Baltic2009]Radio Transmission (KMP)

\(n - nex[n]\)是最小循环节.

#include <iostream>

#include <cstdio>

using namespace std;

const int maxN = 1000000 + 7;

int len2;

char s2[maxN];

int nex[maxN];

void get_nex() {

    int p = 0;nex[1] = 0;

    for(int i = 2;i <= len2;++ i) {

        while(s2[i] != s2[p + 1] && p > 0) p = nex[p];

        if(s2[i] == s2[p + 1]) p ++;

        nex[i] = p;

    }

    printf("%d",len2 - nex[len2]);

    return ;

}

int main() {

    scanf("%d",&len2);

    cin >> (s2 + 1);

    get_nex();

    return 0;

}

1192: [HNOI2006]鬼谷子的钱袋 (二进制)

二进制即可

#include <iostream>

#include <cstdio>

int main(){

    int n,tot = 0;

    scanf("%d",&n);

    while(n){

        n >>= 1;

        tot ++;

    }

    printf("%d",tot);

}

1407: [Noi2002]Savage (exgcd,数论)

枚举\(m\),然后\(exgcd\)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

struct shadow

{

    int c,p,l;

}s[1000];

int x,y;

int gcd(int a,int b) {

	return !b ? a : gcd(b,a % b);

}

void exgcd(int a,int b,int &x,int &y) {

	if(!b) {

		x = 1;

		y = 0;

		return;

	}

	exgcd(b,a % b,x,y);

	int tmp = x;

	x = y;

	y = tmp - a / b * x;

}

int n;

bool work(int m)

{

    int a,b,c,t,x,y;

    for(int i = 1;i <= n;i ++)

    {

        for(int j = i + 1;j <= n;j ++)

        {

            a = s[i].p - s[j].p;

            c = s[j].c - s[i].c;

            b = m;

            t = gcd(a,b);

            if(c % t == 0)

            {

                a /= t;b /= t;c /= t;

                exgcd(a,b,x,y);

                b = abs(b);

                x = ( (c * x) % b + b ) % b;

                if(!x)

                    x += b;

                if(x <= min(s[i].l,s[j].l))

                    return 0;

            }

        }

    }

    return 1;

}

int main()

{

    cin >> n;

    int maxx = 0;

    for(int i = 1;i <= n;i ++)

    {

        cin >> s[i].c >> s[i].p >> s[i].l;

        maxx = max(maxx,s[i].c);

    }

    for(int i = maxx;;i ++)

        if(work(i))

        {

            cout << i << endl;

            return 0;

        }

    return 0;

}

1477: 青蛙的约会 (exgcd,数论)

\(exgcd\)

#include <iostream>

#include <cstdio>

#define ll long long

using namespace std;

inline ll read() {

    ll x = 0,f = 1;char c = getchar();

    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}

    while(c >= '0' && c <= '9') {x = x * 10 + c- '0';c = getchar();}

    return x * f;

}

ll gcd(ll a,ll b) {

    return !b ? a : gcd(b ,a % b);

}

ll exgcd(ll a,ll b,ll &x,ll &y) {

    if( !b ) {

        x = 1;

        y = 0;

        return a;

    }

    ll g = exgcd(b,a % b,x,y);

    ll tmp = x;

    x = y;

    y = tmp - (a / b) * y;

    return g;

}

ll x,y,x1,y1,k1,L;

int main() {

    x = read();y = read();x1 = read();y1 = read();L = read();

    if(x1 < y1) {

        swap(x1,y1);

        swap(x,y);

    }

    ll tmpx,tmpy,g;

    if((y - x) % gcd((x1 - y1),L) != 0) {

        printf("Impossible");

        return 0;

    }

    g = exgcd(x1 - y1,L,tmpx,tmpy);

    tmpx = tmpx * (y - x) / g;

    L = L / g;

    tmpx = (tmpx % L + L) % L;

    printf("%lld",tmpx);

    return 0;

}

1798: [Ahoi2009]Seq 维护序列seq (线段树)

线段树模板题

// luogu-judger-enable-o2

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

#define ll long long

const ll maxN = 1e5 + 7;

ll n,m,P;

ll a[maxN];

inline ll read() {

    ll x = 0,f = 1;char c = getchar();

    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}

    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}

    return x * f;

}

struct Node{

    struct emmmm{

        ll l,r,sum,tag,lazy;

    }tree[maxN << 2];

    inline void updata(ll now) {

        tree[now].sum = (tree[now << 1].sum + tree[now << 1 | 1].sum) % P;

        return;

    } 

    void build(ll now,ll l,ll r) {

        tree[now].l = l;tree[now].r = r;

        tree[now].lazy = 0;

        tree[now].tag = 1;

        if(l == r) {

            tree[now].sum = a[l];

            return;

        }

        ll mid = (l + r) >> 1;

        build(now << 1,l,mid);

        build(now << 1 | 1,mid + 1,r);

        updata(now);

    }

    void pushdown(ll now) {

        ll tag = tree[now].tag;

        ll lazy = tree[now].lazy;

        tree[now << 1].lazy = (tree[now << 1].lazy * tag + lazy) % P;

        tree[now << 1 | 1].lazy = (tree[now << 1 | 1].lazy * tag + lazy) % P;

        tree[now << 1].tag = (tree[now << 1].tag * tag) % P;

        tree[now << 1 | 1].tag = (tree[now << 1 | 1].tag * tag) % P;

        tree[now << 1].sum = (tree[now << 1].sum * tag + (tree[now << 1].r - tree[now << 1].l + 1) * lazy) % P;

        tree[now << 1 | 1].sum = (tree[now << 1 | 1].sum * tag + (tree[now << 1 | 1].r - tree[now << 1 | 1].l + 1) * lazy) % P;

        tree[now].tag = 1;

        tree[now].lazy = 0;

        return;

    }

    void muladd(ll l,ll r,ll k,ll now) {

        if(tree[now].l >= l && tree[now].r <= r) {

            tree[now].tag = (tree[now].tag * k) % P;

            tree[now].lazy = (tree[now].lazy * k) % P;

            tree[now].sum = (tree[now].sum * k) % P;

            return ;

        }

        if(tree[now].tag != 1 || tree[now].lazy) pushdown(now);

        ll mid = (tree[now].r + tree[now].l) >> 1;

        if(mid >= l) muladd(l,r,k,now << 1);

        if(mid < r) muladd(l,r,k,now << 1 | 1);

        updata(now);

    }

    ll query(ll l,ll r,ll now) {

        if( tree[now].l >= l && tree[now].r <= r )

            return tree[now].sum % P;

        ll mid = (tree[now].l + tree[now].r) >> 1;

        ll Ans = 0;

        if(tree[now].tag != 1 || tree[now].lazy) pushdown(now);

        if(mid >= l) Ans += query(l,r,now << 1);

        if(r > mid) Ans += query(l,r,now << 1 | 1);

        return Ans % P;

    }

    void addadd(ll l,ll r,ll k,ll now) {

        if(tree[now].l >= l && tree[now].r <= r) {

            tree[now].lazy = (tree[now].lazy + k) % P;

            tree[now].sum = (tree[now].sum + (tree[now].r - tree[now].l + 1) * k ) % P;

            return;

        }

        if(tree[now].tag != 1 || tree[now].lazy) pushdown(now);

        ll mid = (tree[now].l + tree[now].r) >> 1;

        if(mid >= l) addadd(l,r,k,now << 1);

        if(mid < r) addadd(l,r,k,now << 1 | 1);

        updata(now);

        return;

    }

}stree;

int main() {

    n = read();P = read();

    for(ll i = 1;i <= n;++ i)

        a[i] = read();

    stree.build(1,1,n);

    m = read();

    for(ll i = 1,opt,l,r;i <= m;++ i) {

        opt = read();l = read();r = read();

        if(opt == 1) {

            ll x = read();

            stree.muladd(l,r,x,1);

        }

        if(opt == 2) {

            ll x = read();

            stree.addadd(l,r,x,1);

        }

        if(opt == 3)

            printf("%d\n",stree.query(l,r,1));

    }

    return 0;

}

2208: [Jsoi2010]连通数 (bitset)

\(bitset\)优化

#include <bitset>

#include <cstdio>

#include <iostream>

const int X = 2005;

std::bitset<X>g[X];

char z[X];

int main(){

    int n;

    scanf("%d",&n);

    for(int i = 0;i < n;++ i){

        scanf("%s",z);

        for(int j = 0;j < n;++ j)

            g[i][j] = (z[j] == '1' || i == j);

    }

    for(int k = 0;k < n;++ k){

        for(int i = 0;i < n;++ i){

            if(g[i][k])g[i] |= g[k];

        }

    }

    int s = 0;

    for(int i = 0;i < n;++ i)

        s += g[i].count();

    printf("%d\n",s);

}

2875: [Noi2012]随机数生成器 (矩阵快速幂)

矩阵快速幂 + 快速乘

#include <iostream>

#include <cstdio>

#include <cstring>

#define ll long long

ll m,a,c,x0,n,g;//模数 a c 第0项 n 第n项模除g

struct emm{

    ll s[4][4];

    emm() {memset(s,0,sizeof(s));}

}ans;

long long mul(long long a,long long b)

{

    long long res=0;

    for(;b;b>>=1)

    {

        if(b&1)res=(res+a)%m;

        a=(a<<1)%m;

    }

    return res;

}

emm operator * (const emm &a,const emm &b) {

    emm c;

    for(ll i = 1;i <= 2;++ i)

        for(ll j = 1;j <= 2;++ j)

            for(ll k = 1;k <= 2;++ k)

                c.s[i][j] = ( c.s[i][j] + mul(a.s[i][k] , b.s[k][j])) % m;

    return c;

}

void fast_pow() {

    emm now;

    ans.s[1][1] = ans.s[2][2] = 1;

    now.s[1][1] = a;

    now.s[2][1] = c;

    now.s[2][2] = 1;

    for(;n;n >>= 1,now = now * now) {

        if(n & 1) ans = ans * now;

    }

    emm c;

    c.s[1][1] = x0;c.s[1][2] = 1;

    c = c * ans;

    std::cout << c.s[1][1] % g;

} 

int main() {

    std::cin >> m >> a >> c >> x0 >> n >> g;

    fast_pow();

    return 0;

}

3224: Tyvj 1728 普通平衡树 (splay)

splay模板

#include <bits/stdc++.h>

const int N = 1e6 + 10;

int ch[N][3], fa[N], size[N], cnt[N], key[N];

int Size, Root;

#define gc getchar()

inline int read() {

    int x = 0, f = 1; char c = gc;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc;}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;

    return x * f;

}

void Clear(int x) {

    ch[x][1] = ch[x][0] = cnt[x] = size[x] = fa[x] = key[x] = 0;

}

void Update(int x) {

    if (x) {

        size[x]=cnt[x];

        if (ch[x][0]) size[x]+=size[ch[x][0]];

        if (ch[x][1]) size[x]+=size[ch[x][1]];

    }

}

bool Get(int x) {

    return ch[fa[x]][1] == x;

}

void Rotate(int x) {

    int fax = fa[x], grfa = fa[fax], w = Get(x);

    ch[fax][w] = ch[x][w ^ 1];

    fa[ch[x][w ^ 1]] = fax;

    ch[x][w ^ 1] = fax;

    fa[fax] = x;

    fa[x] = grfa;

    ch[grfa][ch[grfa][1] == fax] = x;

    Update(fax);

    Update(x);

}

void Splay(int x) {

    for(int fax; fax = fa[x]; Rotate(x))

        if(fa[fax]) Rotate((Get(x) == Get(fax)) ? fax : x);

    Root = x;

}

void Insert(int x) {

    if(! Root) {

        Size ++;

        Root = Size;

        ch[Root][1] = ch[Root][0] = fa[Root] = 0;

        size[Root] = cnt[Size] = 1;

        key[Root] = x;

        return ;

    }

    int now = Root, fanow = 0;

    while(1) {

        if(x == key[now]) {

            cnt[now] ++;

            Update(now), Update(fanow);

            Splay(now);

            return ;

        }

        fanow = now;

        now = ch[now][key[now] < x];

        if(!now) {

            Size ++;

            ch[Size][0] = ch[Size][1] = 0;

            fa[Size] = fanow;

            ch[fanow][x > key[fanow]] = Size;

            size[Size] = cnt[Size] = 1;

            key[Size] = x;

            Update(fanow);

            Splay(Size);

            return;

        }

    }

}

int Pre() {

    int now = ch[Root][0];

    while(ch[now][1]) now = ch[now][1];

    return now;

}

int Nxt() {

    int now = ch[Root][1];

    while(ch[now][0]) now = ch[now][0];

    return now;

}

inline int Find(int x) {

    int now = Root, Ans = 0;

    while(1) {

        if(x < key[now]) now = ch[now][0];

        else {

            Ans += (ch[now][0] ? size[ch[now][0]] : 0);

            if(x == key[now]) {

                Splay(now);

                return Ans + 1;

            }

            Ans += cnt[now];

            now = ch[now][1];

        }

    }

}

inline int Findx(int x) {

    int now = Root;

    while(1) {

        if(ch[now][0] && x <= size[ch[now][0]]) now = ch[now][0];

        else {

            int imp = (ch[now][0] ? size[ch[now][0]] : 0) + cnt[now];

            if(x <= imp) return key[now];

            x -= imp;

            now = ch[now][1];

        }

    }

}

void Delete(int x) {

    int my = Find(x);

    if(cnt[Root] > 1) cnt[Root] --, Update(Root);

    else if(!ch[Root][1] && !ch[Root][0]) Clear(Root), Root = 0;

    else if(!ch[Root][0]) {

        int befroot = Root;

        Root = ch[Root][1];

        fa[Root] = 0;

        Clear(befroot);

    }

    else if(!ch[Root][1]) {

        int befroot = Root;

        Root = ch[Root][0];

        fa[Root] = 0;

        Clear(befroot);

    }

    else {

        int left = Pre(), befroot = Root;

        Splay(left);

        ch[Root][1] = ch[befroot][1];

        fa[ch[befroot][1]] = Root;

        Clear(befroot);

        Update(Root);

    }

    return ;

}

int main() {

    int T = read();

    for(; T; T --) {

        int opt = read(), x = read();

        if(opt == 1) Insert(x);

        else if(opt == 2) Delete(x);

        else if(opt == 3) std:: cout << Find(x) << "\n";

        else if(opt == 4) std:: cout << Findx(x) << "\n";

        else if(opt == 5) {

            Insert(x);

            std:: cout << key[Pre()] << "\n";

            Delete(x);

        } else {

            Insert(x);

            std:: cout << key[Nxt()] << "\n";

            Delete(x);

        }

    }

    return 0;

}

3555: [Ctsc2014]企鹅QQ (hash)

hash

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#define base 233

#define ull unsigned long long

using namespace std;

const int maxN = 30000 + 7;

ull hashe[maxN][200 + 7];

ull hs[maxN];

ull pw[maxN];

char s[maxN][200 + 7];

int n,L;

void init() {

    pw[0] = 1;

    for(int i = 1;i <= L;++ i)

        pw[i] = pw[i - 1] * base;

}

int main() {

    int tmp;

    scanf("%d%d%d",&n,&L,&tmp);

    init();

    for(int i = 1;i <= n;++ i)

        scanf("%s",s[i] + 1);

    for(int i = 1;i <= n;++ i)

        for(int j = 1;j <= L;++ j)

            hashe[i][j] = hashe[i][j - 1] * base + s[i][j];

    int k = 0;

    for(int i = 1;i <= L;++ i) {

        for(int j = 1;j <= n;++ j) {

            hs[j] = hashe[j][i - 1] * pw[L - i] + hashe[j][L] - hashe[j][i] * pw[L - i];

        }

        bool flag = 0;

        sort(hs + 1,hs + n + 1);

        int t = 1;

        for(int j = 2;j <= n;++ j) {

            if(hs[j] != hs[j - 1]) t = 1;

            else {

                k += t ++;

            }

        }

    }

    printf("%d",k);

    return 0;

}

4034: [HAOI2015]树上操作 (树链剖分)

树链剖分模板题

#include <iostream>

#include <algorithm>

#include <cstdio>

const int maxN = 1e5 + 7;

#define ll long long

using namespace std;

inline ll read() {

    ll x = 0,f = 1;char c = getchar();

    while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}

    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}

    return x * f;

}

ll n,m,R;

ll a[maxN];

struct Node{

    ll l,r,w,lazy;

}tree[maxN << 2];

void pushdown(ll now) {

    ll lazy = tree[now].lazy;

    tree[now].lazy = 0;

    tree[now << 1].lazy = (tree[now << 1].lazy + lazy );

    tree[now << 1 | 1].lazy = (tree[now << 1 | 1].lazy + lazy) ;

    tree[now << 1].w += (tree[now << 1].r - tree[now << 1].l + 1) * lazy ;

    tree[now << 1 | 1].w += (tree[now << 1 | 1].r - tree[now << 1 | 1].l + 1) * lazy ;

    return;

} 

void updata(ll now) {

    tree[now].w = (tree[now << 1].w + tree[now << 1 | 1].w) ;

}

void build(ll l,ll r,ll now) {

    tree[now].l = l;tree[now].r = r;

    if(l == r) return;

    ll mid = (l + r ) >> 1;

    build(l,mid,now << 1);

    build(mid + 1,r,now << 1 | 1);

}

void Inter_add(ll l,ll r,ll now,ll val) {

    if(tree[now].l >= l && tree[now].r <= r) {

        tree[now].w += (tree[now].r - tree[now].l + 1) * val;

        tree[now].lazy += val;

        return;

    }

    pushdown(now);

    ll mid = (tree[now].l + tree[now].r) >> 1;

    if(l <= mid) Inter_add(l,r,now << 1,val);

    if(r > mid) Inter_add(l,r,now << 1 | 1,val);

    updata(now);

    return;

}

ll query(ll l,ll r,ll now) {

    if(tree[now].l >= l && tree[now].r <= r) {

        return 	tree[now].w ;

    }

    if(tree[now].lazy)pushdown(now);

    ll Ans = 0;

    ll mid = (tree[now].l + tree[now].r) >> 1;

    if(l <= mid) Ans += query(l,r,now << 1) ;

    if(r > mid ) Ans += query(l,r,now << 1 | 1);

    return Ans ;

}

void change(ll pos,ll val,ll now) {

    if(tree[now].l == tree[now].r) {

        tree[now].w = val ;

        return;

    }

    ll mid = (tree[now].l + tree[now].r) >> 1;

    if(pos <= mid) change(pos,val,now << 1);

    else change(pos,val,now << 1 | 1);

    updata(now);

    return ;

}

struct qode {

    ll v,nex;

}map[maxN << 1];

ll size[maxN],pos[maxN],top[maxN],dep[maxN],fa[maxN],maxsize,num;

ll head[maxN];

void add(ll u,ll v) {

    map[ ++ num].v = v;

    map[num].nex = head[u];

    head[u] = num;

    return;

}

void dfs1(ll u) {

    size[u] = 1;

    for(ll i = head[u];i;i = map[i].nex) {

        ll v = map[i].v;

        if(v == fa[u]) continue;

        fa[v] = u;dep[v] = dep[u] + 1;

        dfs1(v);

        size[u] += size[v];

    }

}//预处理树的大小,父亲节点和深度. 

void dfs2(ll u,ll top1) {

    ll k = 0;

    maxsize ++;

    pos[u] = maxsize;

    top[u] = top1;

    for(ll i = head[u];i;i = map[i].nex) {

        ll v = map[i].v;

        if(dep[v] > dep[u] && size[v] > size[k]) k = v;

    }

    if(!k) return;

    dfs2(k,top1);

    for(ll i = head[u];i;i = map[i].nex) {

        ll v = map[i].v;

        if(dep[v] > dep[u] && v != k) dfs2(v,v);

    }

    return;

}//求重儿子,在线段树中的位置. 

void sloveadd(ll u,ll v,ll val) {

    while(top[u] != top[v]) {

        if(dep[top[u]] < dep[top[v]]) swap(u,v);

        Inter_add(pos[top[u]],pos[u],1,val);

        u = fa[top[u]];

    }

    if(pos[u] > pos[v]) swap(u,v);

    Inter_add(pos[u],pos[v],1,val);

    return ;

}//区间修改 

ll slovequery(ll u,ll v) {

    ll sum = 0;

    while(top[u] != top[v]) {

        if(dep[top[u]] < dep[top[v]]) swap(u,v);

        sum += query(pos[top[u]],pos[u],1);

        u = fa[top[u]];

    }

    if(pos[u] > pos[v]) swap(u,v);

    sum += query(pos[u],pos[v],1);

    return sum;

}//区间查询. 

int main() {

    n = read();m = read();

    for(int i = 1;i <= n;++ i)

        a[i] = read();

    for(ll i = 1,u,v;i < n;++ i) {

        u = read();v = read();

        add(u,v);add(v,u);

    }

    R = 1;

    dfs1(R);dfs2(R,R);

    build(1,maxsize,1);

    for(ll i = 1;i <= n;++ i)

        change(pos[i],a[i],1);

    for(ll i = 1,opt;i <= m;++ i) {

        opt = read();

        if(opt == 1) {

        	ll u,val;

            u = read();val = read();

        	Inter_add(pos[u],pos[u],1,val);

        }

        if(opt == 3) {

            ll u,v;

            u = read();

            printf("%lld\n",slovequery(u,1));

        }

        if(opt == 2) {

            ll x,z;

            x = read();z = read();

            Inter_add(pos[x],pos[x] + size[x] - 1,1,z);

    	}

    }

    return 0;

}

巴特西

Bzoj 近期题目一句话题解