AC. 梦想

frank_c1

2016多校联合训练6

发布于2016年08月04日 | 暂无评论 | 1,083阅读 | 比赛经历

今天题目好丧病啊……

早上听闻人手不足，有一种浓浓的要滚粗的感觉。

最后发现排名还不错，做了五道居然有rank 15，真不容易。

切了四道感觉还是不错的。感谢大爷们把思博题都让我A。

补题啦~

1001. A Boring Question

求

\sum_{1 \le k_1,k_2,...,k_m \le n} \sum_{j=1} ^ {m-1} {{k_{j+1} \choose k_j}} \mod 10 ^ 9 + 7

1 \le T \le 10000, 0 \le n \le 10 ^ 9, 2 \le m \le 10 ^ 9

这题可能需要一些高超的数学推导技巧。不过我们发现公式这样复杂，肯定有一些奥妙重重的规律。

我们小范围打表后可以发现，同一纵列是有明显的递推关系的。且第i列的递推公式为

f(0) = 1, f(n) = mf(n-1) + 1

结合高中数学知识可以推出通项是

f(n) = \frac{m ^ {n+1} -1} {m - 1}

时间复杂度O(T\log n)。

1001
C++
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
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
    
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
const int mo=(int)(1e9)+7;
 
LL pow_mod(LL b,LL p,LL k) {
    LL res=1;
    for(;p;p>>=1) {
        if(p&1) res=res*b%k;
        b=b*b%k;
    }
    return res;
}
 
void solve() {
    int n,m;
    read(n);read(m);
    printf("%lld\n",(pow_mod(m,n+1,mo)+mo-1)*pow_mod(m-1,mo-2,mo)%mo);
}
 
int main() {
    int T;
    read(T);
    while(T--) solve();
    return 0;
}

1002. A Simple Chess

有一枚棋子，初始在(1,1)，要走到(n,m)。

棋子在(x,y)时可以走到(x+2,y+1)或者(x+1,y+2)，不能出界。有r个坏点，棋子不能走到坏点上。

求(1,1)走到(n,m)的方案数，答案对110119取模。保证(1,1)不是坏点。

1 \le n,m \le 10 ^ {18}, 1 \le r \le 100

这是一道经典问题。

一开始意识模糊了一下方程写错了。坑了一会儿才搞对。

先将点去重后按x - y排序。设点1是(1,1)，f(i)是点1走到点i的方案数，则

f(i) = ways(1,i) - \sum_{j=2} ^ {i-1} {ways(j,i)f(j)}

ways(i,j)指点i走到点j的方案数。我们发现在每个点只有两种选择，我们先列个方程算出两种跳法各需要多少次，不妨设为a次和b次，则ways就是{a + b \choose a}。

至于组合数，我们发现模数奥妙重重，肯定是Lucas啦。

时间复杂度O(r ^ 2 \log n)。

1002
C++
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
123
124
125
126
127
128
129
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
    
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
struct point {
    LL x,y;
    point(LL a=0,LL b=0):x(a),y(b) {}
} p[1005];
 
bool operator < (point a,point b) {
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
 
bool operator == (point a,point b) {
    return a.x==b.x && a.y==b.y;
}
 
LL n,m;
int r,tot;
 
LL pow_mod(LL b,LL p,LL k) {
    LL res=1;
    for(;p;p>>=1) {
        if(p&1) res=res*b%k;
        b=b*b%k;
    }
    return res;
}
 
const int mo=110119;
LL fac[mo],ivf[mo];
 
inline void addnode(LL x,LL y) {
    ++tot;p[tot].x=x;p[tot].y=y;
}
 
LL C(LL a,LL b) {
    LL na=a%mo,nb=b%mo;
    if(na<nb) return 0;
    LL tmp=(fac[na]*ivf[na-nb]%mo)*ivf[nb]%mo;
    if(a<mo && b<mo) return tmp;
    return C(a/mo,b/mo)*tmp%mo;
}
 
inline LL calc(int a,int b) {
    LL x=p[b].x-p[a].x,y=p[b].y-p[a].y;
    if((x+y)%3!=0) return 0;
    LL c=(x+y)/3;x-=c;y-=c;
    if(x<0 || y<0) return 0;
    return C(x+y,x);
}
 
inline bool check(int a,int b) {
    if(!(p[a].x<p[b].x && p[a].y<p[b].y)) return 0;
    return 1;
}
 
LL f[1005];
int kase=0;
void solve() {
    tot=0;int fl=0;
    REP(i,1,r) {
        LL x,y;
        read(x);read(y);
        if(x==n && y==m) fl=1;
        addnode(x,y);
    }
    if(fl) {
        printf("Case #%d: 0\n",++kase);
        return;
    }
    addnode(n,m);addnode(1,1);
    sort(p+1,p+tot+1);
    tot=unique(p+1,p+tot+1)-p-1;
    f[1]=1;
    REP(i,2,tot) {
        f[i]=calc(1,i);
        REP(j,2,i-1) if(check(j,i)) {
            f[i]=(f[i]-(f[j]*calc(j,i)%mo)+mo)%mo;
        }
    }
    printf("Case #%d: %lld\n",++kase,f[tot]);
}
 
int main() {
    ivf[0]=fac[0]=1;
    REP(i,1,mo-1) {
        fac[i]=fac[i-1]*i%mo;
        ivf[i]=ivf[i-1]*pow_mod(i,mo-2,mo)%mo;
    }
    while(scanf("%lld%lld%d",&n,&m,&r)==3) solve();
    return 0;
}

1003. A Simple Nim

给定n堆石子，第i堆有a_i个。

每次玩家有两种操作。第一种是选取一堆，取走其中若干个石子。第二种是将一堆石子分成三堆，每堆非空。

求是否先手必胜。

1 \le T \le 100, 1 \le n \le 10 ^ 6, 1 \le a_i \le 10 ^ 9

设某堆有x个石子的SG值是SG(x)。

结合定义，有

SG(x) = mex\{SG(0),SG(1),...,SG(x-1),SG(i) \; xor \; SG(j) \; xor \; SG(k) \; | \; i + j + k = x\}

发现数据范围奥妙重重。于是我们小范围打个表，发现SG(8k + 7) = 8k + 8, SG(8k + 8) = 8k + 7, k \in N，其他SG(x) = x。求一发SG和即可。

时间复杂度O(Tn)。

1003
C++
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
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
    
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
void solve() {
    int n,cnt=0;
    read(n);
    REP(i,1,n) {
        int a;
        read(a);
        if(a%8==0) a--;
        else if((a+1)%8==0) a++;
        cnt^=a;
    }
    if(cnt) printf("First player wins.\n");
    else printf("Second player wins.\n");
}
 
int main() {
    int T;
    read(T);
    while(T--) solve();
    return 0;
}

1004. Magic Number

1005. Master Zhu

1006. Stabilization

1007. This world need more Zhu

给定n个点的带权树，第i个点权值为a_i。

给定m个询问，形如

1 \; u \; v \; a \; b：询问点u子树中出现过a次的权值之和与出现过b次的权值之和的最大公约数，保证u = v。

2 \; u \; v \; a \; b：询问路径(u,v)上出现过a次的权值之和与出现过b次的权值之和的最大公约数。

1 \le T \le 10, 1 \le n,m \le 10 ^ 5, 1 \le a_i \le 10 ^ 9

数据范围和仅有询问操作说明肯定是莫队。

我们发现子树操作可以转化为区间操作。于是我们发现两种操作分别对应树上莫队和序列莫队，分开来做就好了。

于是就找板子拼成了一份200+行的代码。出题人您有意思吗？

时间复杂度O(Tn \sqrt {n})。

1007
C++
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
      
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
 
struct edge {
    int next,to;
};
 
const int maxn=(int)(2e5)+5;
int fr[maxn];
int be[maxn];
int mp[maxn];
int dfn[maxn];
int edv[maxn];
int dep[maxn];
int vis[maxn];
LL res[maxn];
int fa[maxn][22];
int stk[maxn],top;
edge e[maxn<<1];
LL sum[maxn];
int apr[maxn];
int val[maxn],tb[maxn];
int n,tote,cnt,siz,idx,hs_cnt=0;
 
inline void addone(int u,int v) {
    ++tote;
    e[tote].next=fr[u];fr[u]=tote;e[tote].to=v;
}
inline void addedge(int u,int v) {
    addone(u,v);addone(v,u);
}
 
struct EventI {
    int id,l,r,pos,a,b;
} A[maxn];
int posa;
 
struct EventII {
    int id,u,v,a,b;
} B[maxn];
int posb;
 
bool operator < (EventI a,EventI b) {
    if(a.pos!=b.pos) return a.pos<b.pos;
    return a.r<b.r;
}
 
bool operator < (EventII a,EventII b) {
    if(be[a.u]!=be[b.u]) return be[a.u]<be[b.u];
    return dfn[a.v]<dfn[b.v];
}
 
inline int LCA(int u,int v) {
    if(dep[u]>dep[v]) swap(u,v);
    PER(i,20,0) if(dep[u]<=dep[fa[v][i]]) v=fa[v][i];
    if(u==v) return u;
    PER(i,20,0) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
 
inline void verxor(int x) {
    sum[apr[val[x]]]-=tb[val[x]];
    if(!vis[x]) apr[val[x]]++;
    else apr[val[x]]--;
    vis[x]^=1;
    sum[apr[val[x]]]+=tb[val[x]];
}
 
inline void path(int u,int v) {
    if(dep[u]>dep[v]) swap(u,v);
    while(dep[u]<dep[v]) verxor(v),v=fa[v][0];
    while(u!=v) verxor(u),verxor(v),u=fa[u][0],v=fa[v][0];
}
 
LL gcd(LL a,LL b) {
    return b==0?a:gcd(b,a%b);
}
 
inline void EventISolve() {
    int l=1,r=0;
    REP(i,1,n) sum[i]=apr[i]=vis[i]=0;
    REP(i,1,n) sum[apr[val[i]]]+=tb[val[i]];
    REP(i,1,posa) {
        while(r<A[i].r) verxor(mp[++r]);
        while(l>A[i].l) verxor(mp[--l]);
        while(r>A[i].r) verxor(mp[r--]);
        while(l<A[i].l) verxor(mp[l++]);
        res[A[i].id]=gcd(sum[A[i].a],sum[A[i].b]);
    }
}
 
void EventIISolve() {
    int l=1,r=1;
    REP(i,1,n) sum[i]=apr[i]=vis[i]=0;
    REP(i,1,n) sum[apr[val[i]]]+=tb[val[i]];
    REP(i,1,posb) {
        path(l,B[i].u);l=B[i].u;
        path(r,B[i].v);r=B[i].v;
        int lca=LCA(B[i].u,B[i].v);
        verxor(lca);
        res[B[i].id]=gcd(sum[B[i].a],sum[B[i].b]);
        verxor(lca);
    }
}
 
void block(int x,int f,int d) {
    int bot=top;
    dfn[x]=++idx;mp[idx]=x;
    dep[x]=d+1;fa[x][0]=f;
    REP(i,1,20) fa[x][i]=fa[fa[x][i-1]][i-1];
    RAL(i,x) if(e[i].to!=f) {
        block(e[i].to,x,d+1);
        if(top-bot>=siz) {
            ++cnt;
            while(top>bot) be[stk[top--]]=cnt;
        }
    }
    stk[++top]=x;edv[x]=idx;
}
 
inline int hash_v(int x) {
    return lower_bound(tb+1,tb+hs_cnt+1,x)-tb;
}
 
void init() {
    tote=cnt=idx=top=hs_cnt=0;
    posa=posb=0;
    siz=(int)pow(n,0.5);
    REP(i,1,n) fr[i]=-1;
}
 
int kase=0;
void solve() {
    printf("Case #%d:\n",++kase);
    int q;
    read(n);read(q);
    init();
    REP(i,1,n) read(val[i]),tb[++hs_cnt]=val[i];
    sort(tb+1,tb+hs_cnt+1);
    hs_cnt=unique(tb+1,tb+hs_cnt+1)-tb-1;
    REP(i,1,n) val[i]=hash_v(val[i]);
    REP(i,1,n-1) {
        int u,v;
        read(u);read(v);
        addedge(u,v);
    }
    block(1,0,1);
    if(cnt==0) ++cnt;
    while(top) be[stk[top--]]=cnt;
    REP(i,1,q) {
        int opt,u,v,a,b;
        read(opt);read(u);read(v);read(a);read(b);
        if(dfn[u]>dfn[v]) swap(u,v);
        if(opt==1) {
            ++posa;
            A[posa].id=i;A[posa].l=dfn[u];A[posa].r=edv[u];
            A[posa].pos=(dfn[u]-1)/siz+1;A[posa].a=a;A[posa].b=b;
        }
        if(opt==2) {
            ++posb;
            B[posb].id=i;B[posb].u=u;B[posb].v=v;
            B[posb].a=a;B[posb].b=b;
        }
    }
    sort(A+1,A+posa+1);EventISolve();
    sort(B+1,B+posb+1);EventIISolve();
    REP(i,1,q) printf("%lld\n",res[i]);
}
 
int main() {
    int T;
    read(T);
    while(T--) solve();
    return 0;
}

1008. To My Girlfriend

1009. Up Sky,Mr.Zhu

1010. Windows 10

1011. Zhu’s Math Problem

快速访问

    分类目录：

    文章归档：

随便看看

标签

Copyright © 2016 AC. 梦想 版权所有 | Powered By WordPress | Theme By YeLook