摘要:周测总结

09052020机房赛

因为是校内的题所以就不描述题意了.

看到这套题顿时流下了没有数理基础的眼泪…

t1

题目分析

其实题意提示得很明显了,对于任意一个高斯整数都可以分解成$p^{k1}+p^{k2}+\cdots+p^{kn}~(p=-1-i)$的形式.

那这不就是把$p$作为进制吗,我竟然这都没看出来,尝试写dp失败后写状压暴力合并拿了50…

于是我们将给出的数进行$p$进制分解,考虑到$p^0=1$,所以实部和虚部的和为奇数时就说明产生了$p_0$,统计答案.

需要用到虚数的除法:

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef long long lxl;
const lxl big=210;
lxl x,y,cnt,i;
lxl ans[big];
int main(void)
{
x=read(),y=read();
while(x||y)
{
if((x+y)&1)ans[++cnt]=i,--x;
lxl nx=(-x-y)/2,ny=(x-y)/2;
x=nx,y=ny;
++i;
}
printf("%lld\n",cnt);
for(R int i(1);i<=cnt;++i)printf("%lld\n",ans[i]);
return 0;
}

t2

题目分析

第一眼:这个式子组合数带取模,卢卡斯定理分解一下没跑了.

但我不会卢卡斯导致这题变得很不可做于是交了个随机数跑路…

先写下卢卡斯定理:

回到题目上,会发现当$a_i\leq2333$时这个取模本质上没啥用.

也就是说只要组合数的答案不为$0$就可以产生贡献了,也就是$a_{k1}\geq a_{k2}$.

所以说当$a_i$很小时,写个树状数组统计一下不升子序列即可.

但是满分数据是保证$0 \leq a_i \leq 2333333$,所以说要在卢卡斯定理中进行考虑.

发现$n \mod p$和$\lfloor n/p\rfloor$在$n \leq p^2$时相当于是把$n$化成了$p$进制下的两位数,这在本题中恰好合适.

于是将数列中的每一项分解为$p$进制后再用二维树状数组维护第一位和第二位即可.

另外吐槽教练在把题面从pdf搬到校内oj时疑似不会打latex组合数所以把组合数写成了括号内的分数…

代码

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
typedef long long lxl;
const lxl p=2333,mod=1000000007;
lxl n,x,y,ans,del;
lxl t[p+10][p+10];
#define lowbit(x) (x&-x)
inline lxl query(lxl x,lxl y)
{
lxl ret(0);
for(R int i(x);i;i-=lowbit(i))
for(R int j(y);j;j-=lowbit(j))
ret=(ret+t[i][j])%mod;
return ret;
}
inline void add(lxl x,lxl y,lxl val)
{
for(R int i(x);i<=p;i+=lowbit(i))
for(R int j(y);j<=p;j+=lowbit(j))
t[i][j]=(t[i][j]+val)%mod;
}
int main(void)
{
n=read();
for(R int i(1);i<=n;++i)
{
x=read();
lxl ki63=x;
x=x/p,y=ki63%p;
del=query(p-x,p-y);
ans=(ans+del)%mod;
debug(del);
add(p-x,p-y,del+1);
}
printf("%lld\n",ans);
return 0;
}

t3

题目分析

算是个比较套路的dp题,但是打了个$O(2^m)$狂暴跑路.

设$f_{i,j}$为将点集$j$拆分为$i$个连通块的方案数,那么$f_{1,j}$就为点集$j$联通的方案数.

先通过输入的边统计一下点集内有多少边,然后考虑$i=1$的转移.

对于集合$i$的子集$i_0$,由先前的dp已经求得了集合$i-i_0$联通的方案数,那么对于集合$i_0$内的边,因为我们仅统计了集合$i_0$内部的边,仅考虑这些边选任意多条都无法与集合$i-i_0$联通,设集合$i_0$内的连边数量为$p$,那么这些边使得集合$i$不连通的方案数为:

用总的方案减去不连通方案即得答案.

然后考虑$i \geq 2$的转移,考虑集合$j$的子集$j_0$,我们已经求得$f_{i-1,j_0}$,乘上$f_{1,j-j_0}$,也就是让$j_0$的补集联通,单独形成一个连通块,即可.

代码

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
typedef long long lxl;
const lxl large=1<<16|1,big=15,mod=1000000007;
lxl n,m,k;
lxl f[big][large],c[large],base[1010];
int main(void)
{
n=read(),m=read(),k=read();
lxl all=(1<<n)-1;
for(R int i(1);i<=m;++i)
{
lxl x=read()-1,y=read()-1;
++c[(1<<x)|(1<<y)];
}
base[0]=1;
for(R int i(1);i<1010;++i)base[i]=base[i-1]*2%mod;
for(R int i(0);i<n;++i)
for(R int j(0);j<=all;++j)
if(j&(1<<i))c[j]+=c[j^(1<<i)];
for(R int i(1);i<=all;++i)
{
lxl i0=i&(i-1),del(0);
for(R int j(i0);j;j=(j-1)&i0)
del=(del+f[1][i^j]*base[c[j]]%mod)%mod;
f[1][i]=(base[c[i]]-del+mod)%mod;
}
for(R int i(2);i<=k;++i)
for(R int j(1);j<=all;++j)
{
lxl j0=j&(j-1);
for(R int k(j&(j-1));k;k=(k-1)&j0)
f[i][j]=(f[i][j]+f[i-1][k]*f[1][j^k]%mod)%mod;
}
printf("%lld\n",f[k][all]);
return 0;
}