atcTenka1-2019

atcTenka1-2019

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

$\forall f(i)=0(\%p)$

在 $p|gcd(ai)$ 时显然成立,考虑如何验证一个p

多项式必定含有因式 $\prod_{t=0}^{p-1} (x-t)$ ,使用【威尔逊定理】、【任意模数下存在逆元的数,其逆元互不相同】这两个结论,可化为 $x^p-x$

【任意模数下存在逆元的数,其逆元互不相同】的证明: $ax=1(\%p),那么把其一作为未知数,根据裴蜀定理另一个与p互质​$

实现的时候,化一下柿子,发现只需要判断【%下系数剩余系=0】即可;根据上面的推导,只要判断 $p \leq n$ 即可(upd:需要判断a[0]%p=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
int n,a[MAX_N];
bool check(int p)
{
for(int t=0;t<p-1;t++)
{
int sum=0;for(int i=t;i<=n;i+=p-1) sum=(sum+a[i])%p;
if(sum) return 0;
}
return 1;
}
bool isp(int n)
{
for(int i=2;i*i<=n;i++) if(n%i==0) return 0;
return 1;
}
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
vc<int> ans;
void main()
{
n=qread();int d=0;for(int i=n;i>=0;i--) a[i]=qread(),d=gcd(d,abs(a[i]));
for(int i=2;(ll)i*i<=d;i++) if(d%i==0)//debug 爆int
{
ans.PB(i);
while(d%i==0) d/=i;
}
if(d>1) ans.PB(d);
for(int i=2;i<=n;i++) if(a[0]%i==0 and isp(i) and check(i)) ans.PB(i);
sort(ans.begin(),ans.end());
for(int t=0;t<(int)ans.size();t++) if(t==0 or ans[t-1]!=ans[t]) write2(ans[t]);//debug
}

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
转载请注明出处,谢谢!