ACM►刷题实战►CodeForces

Codeforces Round ##FF (Div. 1) - C

name

DZY Loves Fibonacci Numbers

discription

time limit per test:4 seconds
memory limit per test:256 megabytes
In mathematical terms, the sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation

$F_1 = 1; F_2 = 1; F_n = F_{n - 1} + F_{n - 2} (n > 2)$.
DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of n integers: $a_1, a_2, …, a_n$. Moreover, there are m queries, each query has one of the two types:

Format of the query “1 l r”. In reply to the query, you need to add $F_{i - l + 1}$ to each element ai, where l ≤ i ≤ r.
Format of the query “2 l r”. In reply to the query you should output the value of modulo 1000000009 (10^9 + 9).
Help DZY reply to all the queries.

input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 300000). The second line contains n integers $a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9)$ — initial array a.

Then, m lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality 1 ≤ l ≤ r ≤ n holds.

output

For each query of the second type, print the value of the sum on a single line.

sample input

4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3

sample output

17
12

hint

After the first query, a = [2, 3, 5, 7].
For the second query, sum = 2 + 3 + 5 + 7 = 17.
After the third query, a = [2, 4, 6, 9].
For the fourth query, sum = 2 + 4 + 6 = 12.

toturial

斐波那契数列在模$10^9+7$的时候,可以写成这样的形式 $F_n=276601605(691504013^n − 308495997^n)$因为5是一个二次剩余，于是题目就转化为了区间加上等比数列，区间和查询了，加等比数列我们可以直接记录首项然后合并懒惰标记,注意预处理快速幂就能过了。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;

#define rep(i,j,k) for(int i=(j);i<=(k);i++)

const int mod=1e9+9,mul=276601605,b0=691504013,b1=308495997;
const int maxn=3e5+55;

int qp[2][maxn];
void qpowini(){
    qp[0][0]=qp[1][0]=1;
    int b[2]={b0,b1};
    rep(i,0,1)rep(j,1,maxn-1) qp[i][j]=1ll*qp[i][j-1]*b[i]%mod;
}

int qpow(int a,int b){
    if(b>=maxn){
        int res=1;
        while(b){
            if(b&1) res=1ll*res*a%mod;
            a=1ll*a*a%mod;
            b>>=1;
        }
        return res;
    }
    if(a==b0) return qp[0][b];
    if(a==b1) return qp[1][b];
    assert(false);
}

int fenmu0=qpow((1-b0+mod)%mod,mod-2);
int fenmu1=qpow((1-b1+mod)%mod,mod-2);

int f0(int a1,int n){
    int fenzi=1ll*a1*(1-qpow(b0,n)+mod)%mod;
    return 1ll*fenzi*fenmu0%mod;
}
int f1(int a1,int n){
    int fenzi=1ll*a1*(1-qpow(b1,n)+mod)%mod;
    return 1ll*fenzi*fenmu1%mod;
}

#define ml ((l+r)>>1)
#define mr (ml+1)
int ls[maxn*2],rs[maxn*2],fst[2][maxn*2],sum[maxn*2],a[maxn],tot;

void pushup(int&u){sum[u]=(sum[ls[u]]+sum[rs[u]])%mod;}
void pushson(int&u,int l,int r,int d0,int d1){
    sum[u]=(0ll+sum[u]+f0(d0,r-l+1)+f1(d1,r-l+1))%mod;
    fst[0][u]=(fst[0][u]+d0)%mod;
    fst[1][u]=(fst[1][u]+d1)%mod;
}

void pushdown(int&u,int l,int r){
    pushson(ls[u],l,ml,fst[0][u],fst[1][u]);
    pushson(rs[u],mr,r,1ll*fst[0][u]*qpow(b0,ml-l+1)%mod,1ll*fst[1][u]*qpow(b1,ml-l+1)%mod);
    fst[0][u]=fst[1][u]=0;
}

void build(int&u,int l,int r){
    u=++tot;
    fst[0][u]=fst[1][u]=0;
    if(l==r){
        sum[u]=a[l];
        return;
    }
    build(ls[u],l,ml);
    build(rs[u],mr,r);
    pushup(u);
}

void update(int&u,int l,int r,int ql,int qr,int d0,int d1){
    if(ql<=l&&r<=qr){
        pushson(u,l,r,1ll*d0*qpow(b0,l-ql)%mod,1ll*d1*qpow(b1,l-ql)%mod);
        return;
    }
    pushdown(u,l,r);
    if(ql<=ml) update(ls[u],l,ml,ql,qr,d0,d1);
    if(mr<=qr) update(rs[u],mr,r,ql,qr,d0,d1);
    pushup(u);
}

int query(int&u,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return sum[u];
    int res=0;
    pushdown(u,l,r);
    if(ql<=ml) res+=query(ls[u],l,ml,ql,qr);
    if(mr<=qr) res+=query(rs[u],mr,r,ql,qr);
    return res%mod;
}

int main(){
    qpowini();
    int n,m; scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",&a[i]);
    tot=0;
    int rt;
    build(rt,1,n);
    rep(i,1,m){
        int u,l,r; scanf("%d%d%d",&u,&l,&r);
        if(u==1) update(rt,1,n,l,r,1ll*mul*b0%mod,1ll*(mod-mul)*b1%mod);
        else printf("%d\n",query(rt,1,n,l,r));
    }
}
ACM►刷题实战►hdu

hdu6635

###name
Nonsense Time

###description
You a given a permutation $p_1,p_2,…,p_n$ of size n. Initially, all elements in p are frozen. There will be n stages that these elements will become available one by one. On stage i, the element $p_{k_i}$ will become available.

For each i, find the longest increasing subsequence among available elements after the first i stages.

###input
The first line of the input contains an integer T(1≤T≤3), denoting the number of test cases.

In each test case, there is one integer n(1≤n≤50000) in the first line, denoting the size of permutation.

In the second line, there are n distinct integers $p_1,p_2,…,p_n(1≤p_i≤n)$, denoting the permutation.

In the third line, there are n distinct integers $k_1,k_2,…,k_n(1≤k_i≤n)$, describing each stage.

It is guaranteed that $p_1,p_2,…,p_n$ and $k_1,k_2,…,k_n$ are generated randomly.

###output
For each test case, print a single line containing n integers, where the i-th integer denotes the length of the longest increasing subsequence among available elements after the first i stages.

###sample input
1
5
2 5 3 1 4
1 4 5 3 2

###sample output
1 1 2 3 3

###toturial
lis单调不减，所以我们可以直接采取倍增的思路，去尝试计算，即若存在ans[i]=ans[j]则所有ij之间的数，ans[k]=ans[i]=ans[j]他们都相等。可惜用树状数组写常数太大炸了，改正常写法才过

###code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;

const int maxn=5e4+55;
int p[maxn],k[maxn],ans[maxn],a[maxn],dp[maxn];
int N;

int getlis(int*a,int n){
    static int v[maxn];
    int tot=0;
    for(int i=1;i<=n;i++){
        int*it=lower_bound(v+1,v+tot+1,a[i]);
        if(it==v+tot+1) v[++tot]=a[i];
        else *it=a[i];
    }
    return tot;
}

int vis[maxn];
inline void solve(int n){
    if(n<5e3){
        for(int i=1;i<=n;i++) dp[i]=k[i]; sort(dp+1,dp+1+n);
        for(int i=1;i<=n;i++) a[i]=p[dp[i]];
    }
    else{
        for(int i=1;i<=N;i++) vis[i]=0;
        for(int i=1;i<=n;i++) vis[k[i]]=1;
        int tot=0;
        for(int i=1;i<=N;i++){
            if(vis[i]==0) continue;
            a[++tot]=p[i];
        }
    }
    ans[n]=getlis(a,n); //a[1,n]
}

//究极读入挂
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    char ch=nc();int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}

int main(){
    int t=read();
    while(t--){
        int n=read(); N=n;
        for(int i=1;i<=n;i++) p[i]=read();
        for(int i=1;i<=n;i++) k[i]=read();
        solve(1); solve(n);
        set<int>se; se.insert(n);

        int cur=1;
        while(cur<n){
            int begin=*se.begin();
            if(cur+1==begin){
                cur=begin;
                se.erase(begin);
            }
            else if(ans[begin]==ans[cur]){
                while(cur<begin) ans[++cur]=ans[begin];
                se.erase(begin);
            }
            else{
                int x=(cur+begin)>>1;
                solve(x); se.insert(x);
            }
        }
        for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ');
    }
}
ACM►刷题实战►牛客

2019牛客多校7H

###name
Pair

###descirption
Given three integers A, B, C. Count the number of pairs <x,y> (with
1≤x≤A and 1≤y≤B)such that at least one of the following is true:

  • (x and y) > C
  • (x xor y) < C
    (“and”, “xor” are bit operators)

###input
The first line of the input gives the number of test cases, T (T≤100). T test cases follow.

For each test case, the only line contains three integers A, B and C.
$1≤A,B,C≤10^9$

###output
For each test case, the only line contains an integer that is the number of pairs satisfying the condition given in the problem statement.

###sample input
3
3 4 2
4 5 2
7 8 5

###sample output
5
7
31

###toturial
可以直接dfs搜索，然后记忆化加速，写起来很复杂，但是能过

###code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
 
typedef  long long ll;
 
typedef pair<pair<int,int>,pair<int,int>> pair4;
inline pair4 mp(int a,int b,int c,int d){return make_pair(make_pair(a,b),make_pair(c,d));}
 
map<pair4,ll> hashxor,hashand;
ll gxor(ll a,ll b,ll hi,ll c){//       ^<c
    if(a==-1||b==-1)return 0;
    if(hi<=1) {
        ll ct=0;
        for(ll i=0;i<=a;i++){
            for(ll j=0;j<=b;j++){
                if((i^j)<c) ct++;
            }
        }
        return ct;
    }
 
    if(hashxor.find(mp(a,b,hi,c))!=hashxor.end()) return hashxor[mp(a,b,hi,c)];
 
    ll a0=a>=hi-1?hi-1:a;// bg with 0
    ll b0=b>=hi-1?hi-1:b;// bg with 1
    ll a1=a>=hi?(a&(hi-1)):-1;
    ll b1=b>=hi?(b&(hi-1)):-1;
    if(c&hi) return hashxor[mp(a,b,hi,c)]=(a0+1)*(b0+1)+(a1+1)*(b1+1)+gxor(a0,b1,hi>>1,c&(hi-1))+gxor(a1,b0,hi>>1,c&(hi-1));
    else return hashxor[mp(a,b,hi,c)]=gxor(a0,b0,hi>>1,c&(hi-1))+gxor(a1,b1,hi>>1,c&(hi-1));
}
 
ll gand(ll a,ll b,ll hi,ll c){//  &>c
    if(a==-1||b==-1)return 0;
    if(hi<=1) {
        ll ct=0;
        for(ll i=0;i<=a;i++){
            for(ll j=0;j<=b;j++){
                if((i&j)>c) ct++;
            }
        }
        return ct;
    }
 
    if(hashand.find(mp(a,b,hi,c))!=hashand.end()) return hashand[mp(a,b,hi,c)];
 
    ll a0=a>=hi-1?hi-1:a;// bg with 0
    ll b0=b>=hi-1?hi-1:b;// bg with 1
    ll a1=a>=hi?(a&(hi-1)):-1;
    ll b1=b>=hi?(b&(hi-1)):-1;
    if(c&hi) return hashand[mp(a,b,hi,c)]=gand(a1,b1,hi>>1,c&(hi-1));
    else return hashand[mp(a,b,hi,c)]=(a1+1)*(b1+1)+gand(a0,b1,hi>>1,c&(hi-1))+gand(a1,b0,hi>>1,c&(hi-1))+gand(a0,b0,hi>>1,c&(hi-1));
}
 
ll f(ll a,ll b,ll hi,ll c){// &>c ^<c
    if(hi<=1){
        ll ct=0;
        for(ll i=0;i<=a;i++){
            for(ll j=0;j<=b;j++){
                if((i&j)>c||(i^j)<c) ct++;
            }
        }
        return ct;
    }
    ll a0=a>=hi-1?hi-1:a;// bg with 0
    ll b0=b>=hi-1?hi-1:b;// bg with 1
    ll a1=a>=hi?(a&(hi-1)):-1;
    ll b1=b>=hi?(b&(hi-1)):-1;
    if(c&hi) return (a0+1)*(b0+1)+(a1+1)*(b1+1)+gxor(a0,b1,hi>>1,c&(hi-1))+gxor(a1,b0,hi>>1,c&(hi-1));// ^ ^  & &
    else return (a1+1)*(b1+1)+gand(a0,b1,hi>>1,c&(hi-1))+gand(a1,b0,hi>>1,c&(hi-1))+f(a0,b0,hi>>1,c&(hi-1));
}
 
 
ll debug(ll a,ll b,ll c){
    hashxor.clear();
    hashand.clear();
 
    ll hi=max({a,b,c});
    while(hi&(hi-1)) hi&=hi-1;
    return f(a,b,hi,c)+1-min(a+1,c)-min(b+1,c);
}
 
ll baoli(ll a,ll b,ll c){
    ll ct=0;
    for(ll i=1;i<=a;i++){
        for(ll j=1;j<=b;j++){
            if((i&j)>c||(i^j)<c) ct++;
        }
    }
    return ct;
}
 
int main(){
//    srand(time(NULL));
//    int up=300;
//    while(true){
//        int i=rand()%20000+1;
//        int j=rand()%20000+1;
//        int k=rand()%20000+1;
//        int fuck1=baoli(i,j,k);
//        int fuck2=debug(i,j,k);
//        cout<<i<<" "<<j<<" "<<k<<" "<<" "<<fuck1<<" "<<fuck2<<endl;
//        if(fuck1!=fuck2){
//            cout<<baoli(i,j,k)<<endl;
//            cout<<debug(i,j,k)<<endl;
//            cout<<i<<j<<k<<endl;
//            getchar();
//        }
//
//
//    }
    ll a,b,c,t;
    scanf("%lld",&t);
    while(t--){
        hashxor.clear();
        hashand.clear();
 
        scanf("%lld%lld%lld",&a,&b,&c);
        ll hi=max({a,b,c});
        while(hi&(hi-1)) hi&=hi-1;
        printf("%lld\n",f(a,b,hi,c)+1-min(a+1,c)-min(b+1,c));
    }
}

###toturial2
考虑数位dp

###code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define REP(i,j,k) for(int i=(j);i<=(k);i++)
ll dp[33][2][2][3][3],A[33],B[33],C[33];

ll cmp(ll a,ll b){
    if(a<b) return -1;
    if(a==b) return 0;
    return 1;
}

ll dfs(ll bit,ll la,ll lb,ll ad,ll xr){
    if(bit==-1) return ad==1||xr==-1;
    ll&res=dp[bit][la][lb][ad+1][xr+1];
    if(res!=-1) return res;
    res=0;
    REP(i,0,la?A[bit]:1) REP(j,0,lb?B[bit]:1) res+=dfs(bit-1,la&&i==A[bit],lb&&j==B[bit],ad?ad:cmp(i&j,C[bit]),xr?xr:cmp(i^j,C[bit]));
    return res;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(dp,-1,sizeof(dp));
        ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c);
        REP(i,0,30) A[i]=bool(1<<i&a),B[i]=bool(1<<i&b),C[i]=bool(1<<i&c);
        printf("%lld\n",dfs(30,1,1,0,0)+1-min(a+1,c)-min(b+1,c));
    }
}

ACM►刷题实战►牛客

2019牛客多校7E

###name
Find the median

###descirption
Let median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array [10,3,2,3,2] is 3 Median of the array [1,5,8,1] is 1

At first, you’re given an empty sequence. There are N operations. The i-th operation contains two integers$L_i$and$R_i$.This means that adding $R_i-L_i+1$ integers $L_i,L_i+1,…,R_i$into the sequence. After each operation, you need to find the median of the sequence.

###input
The first line of the input contains an integer N(1≤N≤400000)as described above.

The next two lines each contains six integers in the following format, respectively:

  • $X_1X_2A_1B_1C_1M_1$
  • $Y_1Y_2A_2B_2C_2M_2$

These values are used to generate $L_i,R_i$as follows:

We define:

  • $X_i=(A_1X_{i-1}+B_1X_{i-2}+C_1)module\quad M_1,for\quad i=3\quad to\quad N$
  • $Y_i=(A_2Y_{i-1}+B_2Y_{i-2}+C_2)module\quad M_1,for\quad i=3\quad to\quad N$

We also define:

  • $L_i=min(X_i,Y_i)+1,for\quad i=1\quad to\quad N$
  • $R_i=max(x_i,Y_i)+1,for\quad i=1\quad to\quad N$

Limits:
$1≤N≤400000$
$0≤A_1,B_1,C_1,X_1,X_2<M_1$
$0≤A_2,B_2,C_2,Y_1,Y_2<M_2$
$1≤M1,M2≤10^9$

###output
You should output N lines. Each line contains an integer means the median.

###sample input
5
3 1 4 1 5 9
2 7 1 8 2 9

###sample output
3
4
5
4
5

###hint
L = [3, 2 ,4, 1, 7]
R = [4, 8, 8, 3, 9]

###toturial
离散化区间后用权值线段树维护区间和,直接在树上二分答案

###code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;

vector<int>disc;
int getid(int x){return lower_bound(disc.begin(),disc.end(),x)-disc.begin();}

#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn = 8e5+55;
int ls[maxn*2],rs[maxn*2],add[maxn*2],tot;//update用了几次，就要乘以多少
long long siz[maxn*2];

void maketrue(int&u){if(u==0) u=++tot,ls[u]=rs[u]=siz[u]=add[u]=0;}
void pushup(int u,int l,int r){siz[u]=siz[ls[u]]+siz[rs[u]];}
void pushdown(int u,int l,int r){
    maketrue(ls[u]);
    maketrue(rs[u]);
    add[ls[u]]+=add[u];
    add[rs[u]]+=add[u];
    siz[ls[u]]+=add[u]*(disc[ml+1]-disc[l]);
    siz[rs[u]]+=add[u]*(disc[r+1]-disc[mr]);
    add[u]=0;
}

void update(int&u,int l,int r,int ql,int qr){//把u按照pre复制，然后更新pos
    maketrue(u);
    if(ql<=l&&r<=qr){
        siz[u]+=disc[r+1]-disc[l];
        add[u]++;
        return;
    }
    pushdown(u,l,r);
    if(ml>=ql)update(ls[u],l,ml,ql,qr);
    if(mr<=qr)update(rs[u],mr,r,ql,qr);
    pushup(u,l,r);
}

int query(int&u,int l,int r,long long k){
    maketrue(u);
    if(l==r) {
        int ct=siz[u]/(disc[l+1]-disc[l]);
        return disc[l]-1+(k+ct-1)/ct;
    }
    pushdown(u,l,r);
    if(siz[ls[u]]>=k) return query(ls[u],l,ml,k);
    else return query(rs[u],mr,r,k-siz[ls[u]]);
}

int main(){
    long long n,x1,x2,a1,b1,c1,m1,y1,y2,a2,b2,c2,m2;
    scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld%lld",&n,&x1,&x2,&a1,&b1,&c1,&m1,&y1,&y2,&a2,&b2,&c2,&m2);
    vector<int> x(n+1),y(n+1);
    x[1]=x1; x[2]=x2;
    y[1]=y1; y[2]=y2;
    for(int i=3;i<=n;i++){
        x[i]=(1ll*a1*x[i-1]+1ll*b1*x[i-2]+c1)%m1;
        y[i]=(1ll*a2*y[i-1]+1ll*b2*y[i-2]+c2)%m2;
    }
    for(int i=1;i<=n;i++) {
        x[i]++,y[i]++;
        if(x[i]>y[i]) swap(x[i],y[i]);
    }
    for(int i=1;i<=n;i++) disc.push_back(x[i]),disc.push_back(y[i]+1);
    disc.push_back(-2e9),disc.push_back(2e9);
    sort(disc.begin(),disc.end());
    disc.erase(unique(disc.begin(),disc.end()),disc.end());

    tot=0;
    long long sum=0;
    int rt=0;
    for(int i=1;i<=n;i++){
        sum+=y[i]-x[i]+1;
        update(rt,1,disc.size(),getid(x[i]),getid(y[i]+1)-1);
        printf("%d\n",query(rt,1,disc.size(),(sum+1)/2));
    }
}
ACM►学习笔记►数学

两分数间分母最小的分数

给你两个分数,让你找一个分数在他们俩之间,要求分母最小,

这个问题很显然，我们应该转移到Stern Brocot Tree上面去做,对于给定的两个分数，我们把他们在树上标记出来，可能他们不在树的同一层，但是我们可以找到一个合适的层数，并且把他们标记在这一层，可能标记后，他们之间没有其他分数，那我们就选择更深的一层，直到他们在同一层，且中间有其他数字。

这时我们来分析答案在哪，首先很容易证明答案就在他们俩之间的那些分数之间，因为这些分数已经满足了值在他们俩之间，对于另一个要求-分母最小，这就要求我们在这些分数中取出一个分母最小的。

有一个很简单的做法可以帮助我们找到答案，那就是，把这些可能的答案全部标记为红色，真正的答案就是这些标记的lca。

当我们发现答案是lca的时候，我们也发现了另一个现象，分子分母具有轮换对称性当分母取到最小值的时候，分子可能有多个解，如果我们选择了最小的分子，我们将得到一个分数 $\frac{a1}{b1}$ 我们发现如果不考虑分母最小，此时的分子也是所有解中最小的分子。

换句话说，在$(\frac{u}{v},\frac{x}{y})$中所有分母最小的分数中选择一个分子最小的分数和$(\frac{u}{v},\frac{x}{y})$中所有分子最小的分数中选择一个分母最小的分数，选出的结果一定是相同的。

于是我们就可以利用此特征来解决上诉问题了，代码如下，若区间包含了一个整数z，那么答案一定是$\frac{z}{1}$,否则我们可以将区间向左移动，理由是，尽管分子变了，但是区间移动不影响分母的大小，再根据分母最小时的分子最小的答案 等于 分子最小时分母最小的答案 即分母能唯一确定分子，通过区间移动后的分母的最小值推出区间移动前的分母最小值，进而推出区间移动前的分子的最小值，我们就能解决这个问题了。
用辗转相除加速。

1
2
3
4
5
6
7
8
void solve(ll u1,ll u2,ll&r1,ll&r2,ll v1,ll v2){ // u1/u2<r1/r2<v1/v2
    if((u1+u2-1)/u2<=v1/v2) r1=(u1+u2-1)/u2,r2=1;
    else{
        ll d=u1/u2; //u1/u2-d<r1/r2-d<v1/v2-d
        solve(v2,v1-v2*d,r2,r1,u2,u1-u2*d);
        r1+=d*r2;
    }
}
ACM►刷题实战►hdu

hdu6624

###name
fraction

###descirption
Many problems require printing the probability of something. Moreover, it is common that if the answer is $\frac{a}{b}$, you should output $a×b^{−1}(modp)$ (p is a prime number). In these problems, you cannot know the exact value of the probability. It’s so confusing!!! Now, we want to reverse engineer the exact probability from such calculated output value x. We do so by guessing the probability is the one with the minimum b such that $a×b^{−1}=x(modp)$. Now we invite you to solve this problem with us!
You are given two positive integers p and x, where p is a prime number.
Please find the smallest positive integer b such that there exist some positive integer a satisfying $a\lt b$ and a≡bx(modp).

###input
The first line contains an integer T indicating there are T tests. Each test consists of a single line containing two integers: p,x.

  • $1≤T≤2×10^5$
  • $3≤p≤10^{15}$
  • p is a prime
  • $1\lt x\lt p$

###output
For each test, output a line containing a string represents the fraction $\frac{a}{b}$ using the format “a/b” (without quotes).

###sample input
3
11 7
998244353 554580197
998244353 998244352

###sample output
2/5
8/9
499122176/499122177

###toturial
$$
a≡bx(modp)
\\Leftrightarrow bx-pk=a
\\Leftrightarrow 0\lt bx-pk\lt b
\\Leftrightarrow \frac{p}{x}\lt \frac{b}{k}\lt \frac{p}{x-1}
$$
等价于求一个分子最小的分数，其值在$(\frac{p}{x},\frac{p}{x-1})$,欧几里得辗转相除即可

###code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve(ll u1,ll u2,ll&r1,ll&r2,ll v1,ll v2){ // u1/u2<r1/r2<v1/v2
    if((u1+u2-1)/u2<=v1/v2) r1=(u1+u2-1)/u2,r2=1;
    else{
        ll d=u1/u2; //u1/u2-d<r1/r2-d<v1/v2-d
        solve(v2,v1-v2*d,r2,r1,u2,u1-u2*d);
        r1+=d*r2;
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ll p,x; scanf("%lld%lld",&p,&x);
        ll b,k; solve(p,x,b,k,p,x-1);
        printf("%lld/%lld\n",b*x-p*k,b);
    }
}
ACM►刷题实战►洛谷

P2444

###name
病毒

###descirption
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。

任务：
请写一个程序：
1.在文本文件WIR.IN中读入病毒代码；
2.判断是否存在一个无限长的安全代码；
3.将结果输出到文件WIR.OUT中。

###input
在文本文件WIR.IN的第一行包括一个整数n(n≤2000)，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。

###output
在文本文件WIR.OUT的第一行输出一个单词：
TAK——假如存在这样的代码；
NIE——如果不存在。

###sample input
3
01
11
00000

###sample output
NIE

###toturial
&emsp;&emsp;建立ac自动机后，判断trans是否构成环即可

###code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+5;
int trans[maxn][2],fail[maxn],ed[maxn],ban[maxn];
int root,cnt;

inline int new_node(){
    //fail指针不需要初始化,因为在bfs的时候他被更新
    for(int i=0;i<2;i++)trans[cnt][i]=0;
    ed[cnt]=0;
    ban[cnt]=0;
    return cnt++;
}

void ini(){
    cnt=0;
    root=new_node();
}

void extend(char*buf){
    int len=(int)strlen(buf+1);
    int u=root;
    for(int i=1;i<=len;i++){
        if(trans[u][buf[i]-'0']==0)
            trans[u][buf[i]-'0']=new_node();
        u=trans[u][buf[i]-'0'];
    }
    ed[u]++;
}

void get_fail(){
    queue<int>q;
    q.push(root);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=0;i<2;i++){
            if(trans[u][i]==0){
                trans[u][i]=-abs(trans[fail[u]][i]);//采用负数来表示非树边。。
            }
            else{
                q.push(trans[u][i]);
                fail[trans[u][i]]=abs(trans[fail[u]][i]);
                if(u==root)fail[trans[u][i]]=root;
            }
        }
        if(ban[fail[u]]==1) ban[u]=1;
        if(ed[u]!=0) ban[u]=1;
    }
}

int ins[maxn];
bool dfs(int u=root){// return ture if have huan
    ins[u]=1;
    for(int i=0;i<2;i++){
        if(ban[abs(trans[u][i])]) continue;
        if(ins[abs(trans[u][i])]) return true;
        if(dfs(abs(trans[u][i]))) return true;
    }
    ins[u]=0;
    return false;
}

char s[maxn];

int main(){
    int n; scanf("%d",&n);
    ini();
    while(n--){
        scanf("%s",s+1);
        extend(s);
    }
    get_fail();
    if(dfs()) puts("TAK");
    else puts("NIE");
}
ACM►刷题实战►hdu

hdu6625

###name
three arrays

###descirption
There are three integer arrays a,b,c. The lengths of them are all N. You are given the full contents of a and b. And the elements in c is produced by following equation: c[i]=a[i] XOR b[i] where XOR is the bitwise exclusive or operation.

Now you can rearrange the order of elements in arrays a and b independently before generating the array c. We ask you to produce the lexicographically smallest possible array c after reordering a and b. Please output the resulting array c.

###input
The first line contains an integer T indicating there are T tests.

Each test consists of three lines. The first line contains one positive integer N denoting the length of arrays a,b,c. The second line describes the array a. The third line describes the array b.

  • T≤1000

  • $1≤N≤10^5$

  • integers in arrays a and b are in the range of [0,230).

  • at most 6 tests with N>100

###output
For each test, output a line containing N integers, representing the lexicographically smallest resulting array c.

###sample input
1
3
3 2 1
4 5 6

###sample output
4 4 7

###toturial
&emsp;&emsp;对于每一个数来说，能够与他匹配最优的数个数可能很多，但是值肯定只有一个，我们以这种关系建图，把数组a的数放在左边，数组b的数放在右边，建立出来的图一定是二分图。
&emsp;&emsp;易证此二分图中可能存在环，若有环，可能有多个数，但必定只有两个值，且这两个值一定是最佳匹配，我们将所有的最佳匹配去掉以后，剩下的是dag图，我们对此图逆拓扑排序，得到的结果即为答案，用栈模拟，字典树加速即可

###code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;

int read(){int x;scanf("%d",&x);return x;}
const int maxn=1e5+5;
int trans[maxn*61][2],s[maxn*61],tot;

inline int newnode(){
    tot++;
    trans[tot][0]=trans[tot][1]=s[tot]=0;
    return tot;
}

inline void insert(int rt,int x){
    int cur=rt; s[cur]++;
    for(int j=29;j>=0;j--){
        int nex=(1<<j&x)>>j;
        if(trans[cur][nex]==0) trans[cur][nex]=newnode();
        cur=trans[cur][nex]; s[cur]++;
    }
}

inline void erase(int rt,int x){
    int cur=rt; s[cur]--;
    for(int j=29;j>=0;j--){
        int nex=(1<<j&x)>>j;
        cur=trans[cur][nex]; s[cur]--;
    }
}

inline int find(int rt,int x){
    int cur=rt,res=0;
    for(int j=29;j>=0;j--){
        int nex=(1<<j&x)>>j;
        if(s[trans[cur][nex]]==0) nex^=1;
        cur=trans[cur][nex];
        res|=nex<<j;
    }
    return res;
}

int a[maxn],b[maxn];

int main(){
    int ti=read();
    while(ti--){
        int n=read();
        tot=0;
        int rta=newnode(),rtb=newnode();
        for(int i=0;i<n;i++) insert(rta,a[i]=read());
        for(int i=0;i<n;i++) insert(rtb,b[i]=read());
        vector<int> ans;
        stack<int> stk;
        while(ans.size()!=n){
           // getchar();
            if(stk.empty()) stk.push(find(rta,214340));
            int top=stk.top(); stk.pop();
            if((stk.size()&1)==0){// in a
                int priority=find(rtb,top);
                //cout<<top<<" "<<priority<<endl;
                if(!stk.empty()&&stk.top()==priority){
                    ans.push_back(priority^top);
                  //  cout<<ans.back()<<endl;
                    stk.pop();
                    erase(rta,top);
                    erase(rtb,priority);
                }
                else{
                    stk.push(top);
                    stk.push(priority);
                }
            }
            else{// in b
                int priority=find(rta,top);
               // cout<<top<<" "<<priority<<endl;
                if(!stk.empty()&&stk.top()==priority){
                    ans.push_back(priority^top);
                   // cout<<ans.back()<<endl;

                    stk.pop();
                    erase(rtb,top);
                    erase(rta,priority);
                }
                else{
                    stk.push(top);
                    stk.push(priority);
                }
            }
        }
        sort(ans.begin(),ans.end());
        for(int i=0;i+1<ans.size();i++){
            printf("%d ",ans[i]);
        }
        printf("%d\n",ans.back());
    }
}
ACM►老Blog迁移►reading_problem

51NOD1055

转移自老blog

51NOD1055

链接

题意

        N个不同的正整数A[i]，找出由这些数组成的最长的等差数列。N<=1e4,A[i]<=1e9

题解

        dp[i][j]代表最后两项的下标为i和j,i<j, dp[i][j] <--- dp[k][i] if(a[k]+a[j]==2*a[i])
        从大到小枚举j,则k单调，故复杂度O(n)。