Tenka1 Programmer Contest 2019

Tenka1 Programmer Contest 2019
好题:F

D Three Colors

请先思考后再展开

$(a>b>c)合法当且仅当 a<\lceil \frac{sum}{2} \rceil$ ,考虑容斥掉非法情况

先考虑一个 $n^4$ 的做法,$dp(i,a)=选了i个数,和为a的方案数$

那么 $ans=\sum_{S \geq \lceil \frac{sum}{2} \rceil} \sum_i 3f(i,S)2^{n-i}$

但当S为偶数,a=b=num/2的情况会被减两次,加回来即可

然后仔细观察一下上面的式子,发现只要一开始存在$2^n$的系数,在增加数的时候/2即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int f[MAX_N*MAX_N],g[MAX_N*MAX_N];
void main()
{
int n=qread(),sum=0;f[0]=qpower(2,n);g[0]=1;
for(int i=1;i<=n;i++)
{
int aa=qread();
for(int s=sum;s>=0;s--) add(f[s+aa],(ll)f[s]*inv2%MOD),add(g[s+aa],g[s]);
sum+=aa;
}
int ans=qpower(3,n);
for(int a=ceil(sum/2.0);a<=sum;a++) add(ans,-(ll)f[a]%MOD*3%MOD);
if(sum%2==0) add(ans,(ll)g[sum/2]*3%MOD);
write((ans+MOD)%MOD);
}

还有一种做法,也是考虑容斥,容斥掉 $a-b-c \geq 0$ 的部分,然后这个部分很好求,因为a一定是最大值,不会被替代

和上面一样要考虑a=b=num/2的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int f[MAX_N][MAX_N*MAX_N*2],g[MAX_N][MAX_N*MAX_N];
#define F(i,j) f[i][MAX_N*MAX_N+j]
#define G(i,j) g[i][MAX_N*MAX_N+j]
void main()
{
int n=qread(),sum=0;F(0,0)=1;G(0,0)=1;
for(int i=1;i<=n;i++)
{
int aa=qread();
for(int s=-sum;s<=sum;s++)
{
add(F(i,s+aa),F(i-1,s));
add(F(i,s-aa),1ll*F(i-1,s)*2%MOD);
add(G(i,s+aa),G(i-1,s));
add(G(i,s-aa),G(i-1,s));
}
sum+=aa;
}
int ans=qpower(3,n);
for(int s=0;s<=sum;s++) add(ans,-(ll)F(n,s)*3%MOD);
if(sum%2==0) add(ans,(ll)G(n,0)*3%MOD);
write((ans+MOD)%MOD);
}

E Polynomial Divisors

题意:给出一个$n \le 1e4$次多项式f,问有多少个$p \in Prime$满足$\forall f(i)=0(\%p)$

请先思考后再展开

首先$p|gcd(a_i)$肯定是可以的,除此之外,根据因式定理,多项式一定有因式$\prod_{t=0}^{p-1} (x-t)$,分析这个因式的根、最高项,根据费马小定理知等价于$(x^{p-1}-1)x$。故枚举n以内的p并做多项式取模即可,$O(n^2/ln)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ll n,a[N],b[N];vc<int> ans;
bool isp(int num){if(num==1)return 0;fo(i,2,sqrt(num))if(num%i==0)return 0;return 1;}
bool check(int p)
{
fo(i,0,n-1) b[i]=a[i+1];
fd(i,n-1,p-1) (b[i-(p-1)]-=1ll*(p-1)*b[i])%=p,b[i]=0;
fo(i,0,p-2) if(b[i]) return 0;return 1;
}
void main()
{
n=qread();int d=0;fd(i,n,0) a[i]=qread(),d=gcd(d,a[i]);d=abs(d);
fo(p,1,sqrt(d)) if(d%p==0) {if(isp(p)) ans.PB(p);if(isp(d/p)) ans.PB(d/p);}
fo(p,1,n) if(isp(p) and a[0]%p==0 and check(p)) ans.PB(p);
sort(all(ans));ans.resize(unique(all(ans))-ans.begin());for(auto t:ans) write2(t);
}

F Banned X

请先思考后再展开

需要考虑12串的贡献,最后枚举长度塞0即可

  1. $sum<X$
  2. $sum>X,不能产生一个连续区间的和为某个 \geq sum 的偶数$

如果存在这样的区间,那么不断删除2、删除两边的1就能产生0

那么枚举ln和sum

对于第一种,$C_{ln}^{sum-ln}$

对于第二种,$[(sum-X)\&1]$,左右两侧都必须放足够多的2($\lceil \frac{sum-ln}{2} \rceil$),然后中间就可以随便放了,即 $C_{ln-2\lceil \frac{sum-ln}{2} \rceil}^{2ln-sum}$

$ans=\sum C_n^{ln} f(ln)$ 时间复杂度 $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int C[MAX_N][MAX_N];
void main()
{
C[0][0]=1;for(int i=1;i<MAX_N;i++){C[i][0]=1;for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;}

int n=qread(),X=qread();int ans=1;
for(int ln=1;ln<=n;ln++)
{
int now=(X&1 or X>2*ln);
for(int sum=ln;sum<=2*ln-1;sum++)
{
if(sum<X) add(now,C[ln][sum-ln]);
else if((sum-X)&1)
{
int cnt=(sum-X+1)/2;if(cnt*2>=ln) continue;
add(now,C[ln-2*cnt][2*ln-sum]);
}
}
add(ans,(ll)now*C[n][ln]%MOD);
}
write(ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/23f2.html
转载请注明出处,谢谢!