学大伟业Day解题报告
预计分数:30+30+0=60
实际分数:30+20+0=50
题解部分全部来自http://www.cnblogs.com/TheRoadToTheGold/p/7723564.html
T1https://www.luogu.org/problem/show?pid=T14734
不会。。打30分暴力走人
对于60%的分数
通过观察可知设当前坐标为x，则通过坐标为a的圆环可移动到2a-x处。连续通过两个圆环(a,b)可以移动到x+(2b-2a)处。
先以移动步数为偶数情况考虑简化版问题：设圆环坐标为a[1]~a[n]，对于任意两个圆环，可由坐标x变为x+2(a[j]-a[i])，题目转化为对于N^2个数其中b[i,j]=2(a[j]-a[i])，通过有限次加减运算能否由x=0变化至目标。
根据广义裴蜀定理以及扩展欧几里得相关原理可知，当且仅当目标为gcd的倍数时有解。故预处理出全部可能的2(a[j]-a[i])，求出其最大公约数，在判断目标是否为gcd的倍数即可。
对于奇数的情况，可以通过枚举第一步的方案转化为偶数的情况，即维护一个set表示0步或1步可达点集(mod gcd意义下)，再查询目标点在mod gcd下是否属于这个集合即可。复杂度瓶颈在于N^2个数求gcd。
对于100%的分数
通过欧几里得算法的性质与更相减损术可知gcd(a,b)=gcd(a-b,b)。设p1={2*(a[i]-a[1])|i>1}的最大公约数，设p2={2*(a[i]-a[j])}的最大公约数，易知p1>=p2（因为p1比p2约束宽松）。而对于任意i,j由于p1同时是2*(a[i]-a[1])、2*(a[j]-a[1])的约束，那么p1也一定是任意2*(a[i]-a[1])-2*(a[j]-a[1])=2*(a[i]-a[j])的约数，故p1<=p2。综上所述p1=p2，这样就不需要N^2个数同时求gcd了，只求p1即可，可获得满分。
1 #include<set>
2 #include<cstdio>
3 #include<iostream>
4 #include<algorithm>
5
6 using namespace std;
7
8 typedef long long LL;
9
10 #define N 100001
11
12 LL a[N];
13
14 set<LL>S;
15
16 void read(LL &x)
17 {
18 x=0; int f=1; char c=getchar();
19 while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
20 while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
21 x*=f;
22 }
23
24 LL getgcd(LL i,LL j) { return !j ? i : getgcd(j,i%j); }
25
26 int main()
27 {
28 freopen("ninja.in","r",stdin);
29 freopen("ninja.out","w",stdout);
30 int n,m;
31 scanf("%d%d",&n,&m);
32 for(int i=1;i<=n;i++) read(a[i]);
33 LL gcd=0;
34 for(int i=2;i<=n;i++) gcd=getgcd(abs(a[i]-a[1]<<1),gcd);
35 LL x;
36 if(gcd)
37 {
38 S.insert(0);
39 for(int i=1;i<=n;i++) S.insert((2*a[i]%gcd+gcd)%gcd);
40 while(m--)
41 {
42 read(x);
43 puts(S.find((x%gcd+gcd)%gcd)!=S.end() ? "Yes" : "No");
44 }
45 }
46 else
47 {
48 while(m--)
49 {
50 read(x);
51 puts(x==a[1]*2 ? "Yes" : "No");
52 }
53 }
54 }T2https://www.luogu.org/problem/show?pid=T14735
有20分裸地暴力
还有10分裸的线段树
其他的不会做，，后来线段树写炸了QWQ、、、
线段树
先下放取反标记，在下方加标记
下放取反标记时，若存在加标记，加标记也取反
关键是如何处理加标记的影响
设当前线段树区间有4个数x1，x2，x3，x4
sum[i] 表示 选出i个数的乘积 的和
sum[1]=x1+x2+x3+x4
sum[2]=x1x2+x1x3+x1x4+x2x3+x2x4+x3x4
sum[3]=x1x2x3+x1x2x4+x1x3x4+x2x3x4
sum[4]=x1x2x3x4
操作：区间加a
以sum[3]为例
新的sum[3]=
(x1+a)(x2+a)(x3+a) +
(x1+a)(x2+a)(x4+a) +
(x1+a)(x3+a)(x4+a) +
(x2+a)(x3+a)(x4+a)
=x1x2x3+a(x1x2+x1x3+x2x3)+a^2(x1+x2+x3)+a^3 +
x1x2x4+a(x1x2+x1x4+x2x4)+a^2(x1+x2+x4)+a^3 +
x1x3x4+a(x1x3+x1x4+x3x4)+a^2(x1+x3+x4)+a^3 +
x2x3x4+a(x2x3+x2x4+x3x4)+a^2(x2+x3+x4)+a^3
=sum[3] + a*sum[2]*2 + a^2*sum[1]*3 + a^4
所以 对有siz个元素的区间执行区间加a操作
那么sum[]的更新：
for i： 10 ——> 1
for j：i-1——>1
sum[i]+=a^(i-j)*sum[j]*C(siz-j,i-j)
解释：
有i个（xi+a）相乘
从里面选出j个xi，那就只能选i-j个a
后面那个组合数？
一共有siz个（xi+a） ，已经确定了有j个（xi+a）选择xi
一共要选i个（xi+a），那就要从剩下的siz-j个（xi+a）里选出 i-j个（xi+a）来用他们的a
所以是C（siz-j，i-j）
区间的合并
枚举左边选j个，那右边就选i-j个，乘起来就行了
例：
假设当前要选3个数
左边有2个数x1，x2 选1个，
右边有3个数x3，x4，x5 选2个
那就是 x1*x3*x4+x1*x3*x5+x1*x4*x5+x2*x3*x4+x2*x3*x5+x2*x4*x5
=x1*右边的sum[2]+x2*右边的sum[2]
=左边的sum[1] * 右边的sum[2]
1 #include<cstdio>
2 #include<iostream>
3 #include<algorithm>
4
5 using namespace std;
6
7 #define N 50001
8
9 const int mod=1e9+7;
10
11 typedef long long LL;
12
13 int n;
14
15 int C[N][11];
16
17 int f[N<<2];
18 int siz[N<<2],mid[N<<2];
19 bool rev[N<<2];
20
21 struct node { int sum[11]; }ans[N<<2];
22
23 void read(int &x)
24 {
25 x=0; int ff=1; char c=getchar();
26 while(!isdigit(c)) { if(c=='-') ff=-1; c=getchar(); }
27 while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
28 x*=ff;
29 }
30
31 int tot=0;
32
33 void MOD(int &a,int b)
34 {
35 a+=b;
36 a-= a>=mod ? mod : 0;
37 }
38
39 void pre(int n)
40 {
41 C[0][0]=1;
42 for(int i=1;i<=n;i++)
43 {
44 C[i][0]=1;
45 for(int j=1;j<=min(i,10);j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
46 }
47 }
48
49 void update(int k)
50 {
51 for(int i=1;i<=10;i++)
52 {
53 ans[k].sum[i]=0;
54 for(int j=1;j<i;j++) MOD(ans[k].sum[i],1ll*ans[k<<1].sum[j]*ans[k<<1|1].sum[i-j]%mod);
55 MOD(ans[k].sum[i],ans[k<<1].sum[i]); MOD(ans[k].sum[i],ans[k<<1|1].sum[i]);
56 }
57 }
58
59 void build(int k,int l,int r)
60 {
61 siz[k]=r-l+1;
62 if(l==r) { read(ans[k].sum[1]); MOD(ans[k].sum[1],0); return; }
63 mid[k]=l+r>>1;
64 build(k<<1,l,mid[k]); build(k<<1|1,mid[k]+1,r);
65 update(k);
66 }
67
68 void insert(int k,int w)
69 {
70 MOD(f[k],w);
71 for(int i=10;i;i--)
72 {
73 int x=w;
74 for(int j=i-1;j;j--,x=1ll*x*w%mod)
75 MOD(ans[k].sum[i],1ll*x*ans[k].sum[j]%mod*C[siz[k]-j][i-j]%mod);
76 MOD(ans[k].sum[i],1ll*x*C[siz[k]][i]%mod);
77 }
78 }
79
80 void turn(int k)
81 {
82 rev[k]^=1;
83 if(f[k]) f[k]=mod-f[k];
84 for(int i=9;i>0;i-=2)
85 if(ans[k].sum[i]) ans[k].sum[i]=mod-ans[k].sum[i];
86 }
87
88 void down(int k)
89 {
90 if(rev[k]) turn(k<<1),turn(k<<1|1),rev[k]=0;
91 if(f[k]) insert(k<<1,f[k]),insert(k<<1|1,f[k]),f[k]=0;
92 }
93
94 void add(int k,int l,int r,int opl,int opr,int w)
95 {
96 if(l>=opl && r<=opr) { insert(k,w); return; }
97 down(k);
98 if(opl<=mid[k]) add(k<<1,l,mid[k],opl,opr,w);
99 if(opr>mid[k]) add(k<<1|1,mid[k]+1,r,opl,opr,w);
100 update(k);
101 }
102
103 void reverse(int k,int l,int r,int opl,int opr)
104 {
105 if(l>=opl && r<=opr) { turn(k); return; }
106 down(k);
107 if(opl<=mid[k]) reverse(k<<1,l,mid[k],opl,opr);
108 if(opr>mid[k]) reverse(k<<1|1,mid[k]+1,r,opl,opr);
109 update(k);
110 }
111
112 node query(int k,int l,int r,int opl,int opr,int w)
113 {
114 if(l>=opl && r<=opr) return ans[k];
115 down(k);
116 if(opr<=mid[k]) return query(k<<1,l,mid[k],opl,opr,w);
117 else if(opl>mid[k]) return query(k<<1|1,mid[k]+1,r,opl,opr,w);
118 else
119 {
120 node L=query(k<<1,l,mid[k],opl,opr,w),R=query(k<<1|1,mid[k]+1,r,opl,opr,w);
121 node tmp;
122 for(int i=1;i<=w;i++)
123 {
124 tmp.sum[i]=(L.sum[i]+R.sum[i])%mod;
125 for(int j=1;j<i;j++) MOD(tmp.sum[i],1ll*L.sum[j]*R.sum[i-j]%mod);
126 }
127 return tmp;
128 }
129 }
130
131 int main()
132 {
133 freopen("game.in","r",stdin);
134 freopen("game.out","w",stdout);
135 int n,m;
136 read(n); read(m);
137 pre(n);
138 build(1,1,n);
139 int ty,l,r,w;
140 while(m--)
141 {
142 read(ty); read(l); read(r);
143 if(ty==1)
144 {
145 read(w); w%=mod;
146 w+= w<0 ? mod : 0;
147 add(1,1,n,l,r,w);
148 }
149 else if(ty==2) reverse(1,1,n,l,r);
150 else
151 {
152 read(w);
153 node p=query(1,1,n,l,r,w);
154 printf("%d\n",query(1,1,n,l,r,w).sum[w]);
155 }
156 }
157 }T3https://www.luogu.org/problem/show?pid=T14737
没看懂题目。。。。
总结
、。、、今天的考试确实没有昨天那么水了，，，，
不过，，我好菜啊。。。。。。