day0
下午到了宾馆,晚上醒来好几次。
day1
到了考场感觉非常渴,然而又没有带杯子。
然而t1开场开始打表,然而考场上的我意识模糊导致打表时ans没清零,又因为是取max导致看了半个小时没看出来。
然后开始推exgcd,过了样列然而一拍就错,感觉自己要爆蛋了。
10点多才拍上,不断优化程序之后竟然发现只有1行,看了一眼时间发现10点半了,感觉自己要回家了。
然而还是在11点前写完了t3,边权等于0的情况会出事,然后一直到12点没过大样列。
出来发现一群人ak了。

晚上又醒来好几次。
day2
看完3题发现都是水题,t2是3^n*n^3,然而卡常卡到0.7s。
t3动态开点线段树。
写完还有1个小时,然后作死卡t3常数把一个数组改成int考完发现爆了。
t2在民间数据奇怪的会wa一个点,而且还是树的情况。

然后测完民间数据估分525,药丸。

出成绩day1 260,day2 250。
day2 t2 for循环应该从0开始枚举,然而我从1开始枚举然后只剩80分
day2 t3 没开longlong,炸成70分。
day2挂成暴力分。
afo快乐。

Lucas定理:C(n,m)=C(n/p,m/p)*C(n%p,m%p)(以下p均为素数,/为下取整),a=n%p,b=m%p。
证明:有C(p,n)%p=0(n>0&&n<p)。
因为C(p,n)=p!/n!/(n-p)!,p为素数,不可能被消去。
然后有(1+x)^p=1+x^p(%p)。
因为展开后每一项的系数为C(p,i),由C(p,n)%p=0得在%p下均为0。
然后有(1+x)^n=(1+x)^(n/p*p)*(1+x)^(n%p)
=(1+x^p)^(n/p)*(1+x)^(n%p)(%p下)
=[x^p*sum(C(n/p,i))x^i]*sum(C(n%p,j))*x^j
而(1+x)^n=sum(C(n,i)*(x^i))(i=1..n)
上式左右两边x的某项x^m的系数对p同余,其中左边x^m的系数是C(n,m),因为a,b都小于p,
因此右边的x^m肯定是由x^(m/p*p)和x^b和(i=m/p,j=b)相乘得到。
如何说明每一项一一对应?考虑到x的值可以任意取,在无数种不同的取值下x^i的值也会改变,而式子始终成立,因此一定一一对应。

可以将欧拉序转化为括号序列。
访问一个点时加一个左括号,再把这个点放这,离开时放一个右括号。
显然任意两点间的距离即为括号序列中将它们之间可匹配的括号全部去掉后剩下的括号的数量。
可以使用线段树来维护。
以下为将可以匹配括号删除的情况:
c1,c2代表多余的左括号和右括号
l2所有黑点到左端点左括号与右括号的数量的差值的最大值
r2所有黑点到右端点右括号与左括号的数量的差值的最大值
l1所有黑点到左端点的括号数量的最大值
r1所有黑点到右端点的括号数量的最大值
dis代表最大答案。

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
#include<algorithm>
#include<cstdio>
#define ll int
#define inf 1000000000
#define maxn 100010
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
char s[10];
ll n,q,cnt,tot,sum;
ll head[maxn],v[maxn*3],next[maxn*2],vet[maxn*2],pos[maxn],c[maxn];
struct data{
ll l1,r1,l2,r2,dis,c1,c2;
void New(ll x){
dis=-inf; c1=c2=0;
if (v[x]==-6) c2=1;
if (v[x]==-9) c1=1;
if (v[x]>0&&c[v[x]]) l1=r1=l2=r2=0;
else l1=r1=l2=r2=-inf;
};
}tr[maxn*12];
data merge(data x,data y){
data s;
ll a=x.c1,b=x.c2,c=y.c1,d=y.c2;
s.dis=max(max(x.dis,y.dis),max(x.r1+y.l2,x.r2+y.l1));
s.r1=max(y.r1,max(x.r1-c+d,x.r2+c+d));
s.l1=max(x.l1,max(y.l1-b+a,y.l2+b+a));
s.r2=max(y.r2,x.r2+c-d);
s.l2=max(x.l2,y.l2+b-a);
if (b<c) s.c1=a-b+c,s.c2=d;
else s.c1=a,s.c2=b-c+d;
return s;
}
void insert(ll x,ll y){
next[++cnt]=head[x]; head[x]=cnt; vet[cnt]=y;
}
void dfs(ll x,ll pre){
v[++tot]=-6; v[++tot]=x; pos[x]=tot;
for(ll i=head[x];i;i=next[i])
if (vet[i]!=pre) dfs(vet[i],x);
v[++tot]=-9;
}
void build(ll p,ll l,ll r){
if (l==r){ tr[p].New(l); return; }
ll mid=(l+r)>>1;
build(p<<1,l,mid); build(p<<1|1,mid+1,r);
tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}
void modify(ll p,ll l,ll r,ll x){
if (l==r){ tr[p].New(l); return; }
ll mid=(l+r)>>1;
if (x<=mid) modify(p<<1,l,mid,x);
else modify(p<<1|1,mid+1,r,x);
tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}
int main(){
sum=n=read();
For(i,1,n) c[i]=1;
For(i,1,n-1){
ll x=read(),y=read();
insert(x,y); insert(y,x);
}
dfs(1,-1); build(1,1,tot);
q=read();
while(q--){
scanf("%s",s);
if (s[0]=='C'){
ll x=read();
sum-=c[x]?1:-1;
c[x]^=1;
modify(1,1,tot,pos[x]);
}else{
if (!sum) puts("-1");
else if (sum==1) puts("0");
else writeln(tr[1].dis);
}
}
}

这题可以用prufer定理证明。
考虑最后剩下的2个点,一定有连边,那么一定是在不同集合里。
对于其他点,有n种点,总共出现(m-1)次;有m种点,总共出现(n-1)次。
答案为n^(m-1)*m^(n-1)。

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
#include<algorithm>
#include<memory.h>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll n,m,mod;
ll cheng(ll x,ll k){
ll ans=0;
while(k){
if (k&1) (ans+=x)%=mod; (x<<=1)%=mod;
k>>=1;
}
return ans;
}
ll ppow(ll x,ll k){
ll ans=1;
while(k){
if (k&1) ans=cheng(ans,x); x=cheng(x,x);
k>>=1;
}
return ans;
}
int main(){
n=read(); m=read(); mod=read();
writeln(cheng(ppow(n,m-1),ppow(m,n-1)));
}

首先发现可以直接无视0的位置,答案只与有几个1有关,于是优化到了64个状态。
考虑到如果一个状态有偶数个,那么后手可以仿照先手,于是只需要考虑是奇数个的状态。
然后就转化为谁先把所有奇数个全部转化为偶数个,就能胜利。
考虑一个人一次最多减少8个奇数个,最少减少1个,因此转化为另一个,因此只要考虑%9余数就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll mark[70],n,ans;
int main(){
n=read();
For(i,1,n){
unsigned ll x=read(),tot=0;
for(;x;x-=x&-x) tot++;
mark[tot]++;
}
For(i,0,65) ans+=mark[i]&1;
if (ans%9) puts("B"); else puts("L");
}

打表后可以发现答案每3个一次循环,因此只需要计算%3的余数就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
char s[1010];
ll sum,n;
int main(){
ll T=read();
while(T--){
scanf("%s",s+1);
n=strlen(s+1); sum=0;
For(i,1,n) sum=(sum*10+s[i]-'0')%3;
if (sum) puts("A"); else puts("B");
}
}

nim游戏的sg值为本身,因此只要全部异或就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll n,ans;
int main(){
n=read();
For(i,1,n) ans^=read();
if (ans) puts("A"); else puts("B");
}

先手和后手每一个来回都可以强制使得取k+1个,因此只需要把总石子数%(k+1),若为0则B必胜,否则A必胜,因为A可以取掉这么多石子使得A和B先取与后取顺序转化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll n,ans;
int main(){
ll T=read();
while(T--){
ll n=read(),k=read();
if (n%(k+1)) puts("A");
else puts("B");
}
}

可以对sg值打表找规律,可以发现若%7余2或0则B必胜否则A必胜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<algorithm>
#include<memory.h>
#include<cstdio>
#include<cmath>
#define ll long long
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; }
inline void write(ll x){ if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
int main(){
ll T=read();
while(T--){
ll t=read()%7;
if (t==2||!t) puts("B"); else puts("A");
}
}

首先每个人肯定每次会选择剩下的数中最大的一些数。
因此可以先排序。
考虑到从小到大dp,类似回溯的过程,f[i]代表剩下i个最小的数先手-后手的最大差值。
有dp方程f[i]=max(a[j+1]-f[j])。
然后可以发现求max(a[j+1]-f[j])只需要每次跟新f值后维护一个最大值就可以了。

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
#include<algorithm>
#include<memory.h>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
#define maxn 1000010
#define For(i,x,y) for(ll i=x;i<=y;++i)
#define FOr(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }
inline void write(ll x){ if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0'); }
void writeln(ll x){ write(x); puts(""); }
ll a[maxn],f[maxn],n,cho;
int main(){
n=read();
For(i,1,n) a[i]=read();
sort(a+1,a+n+1);
f[1]=a[1]; cho=a[1];
For(i,1,n){
f[i]=cho;
cho=max(cho,a[i+1]-f[i]);
}
cho=0;
For(i,1,n) cho=max(cho,f[i]);
writeln(cho);
}