Week 3 计数

CF1770F Koxia and Sequence

考虑每个 \(a_i\) 是等价的，所以我们计算 \(a_1=t\) 的方案数 \(\bmod 2\)，\(n\) 是偶数答案是 0。
拆位得到计算 \(a_1[i]=1\) 的方案数 \(\bmod 2\)。可以将 \(a_1\leftarrow a_1-2^i\)。
对于 \(y\) 的限制不好做，考虑容斥去掉这个限制。
即 \(\sum_{y'\subseteq y} (-1)^{|y|-|y'|}f(y')\)，容斥系数 \(\bmod 2=1\)。
其中 \(f(y')=\sum_{\Sigma a=x-2^i}[a_1\subseteq y'-2^i]\prod_{j>1} [a_j\subseteq y']\)，转组合数，范德蒙德卷积得到 \([x-2^i\subseteq ny'-2^i]\)。

qoj7974 染色

考虑 \(n+m\) 元 GF，有 \([z^k\prod x_i^{2k_i+1}]\prod_{i,j}(1+x_iy_jz)\)。
单位根反演，带入 \(b\) 个 \(-1\) 系数就是 \((-1)^b\)。
分 2 类，即 \((1-z)^c(1+z)^{nm-c}\)。
设带入了 \(a\times [x=1],b\times [y=1]\)，贡献是 \((-1)^{n+m-a-b}\binom{n}{a}\binom{m}{b}(1+z)^{ab+(n-a)(m-b)}(1-z)^{a(m-b)+b(n-a)}\)。

最后是 \(\sum_c A_c(1+z)^c(1-z)^{nm-c}\)，可以卷积处理。

TopCoder11351 TheCowDivOne

考虑 GF 有 \(\sum_{q=0}^{\infty} [x^{qn}y^k]\prod_{i=0}^{n-1}(1+x^iy)\)。
设 \(w=\omega_n\)，单位根反演有 \(\frac{1}{n}\sum_{q=0}^{n-1} [y^k]\prod_{i=0}^{n-1}(1+w^{qi}y)\)。
首先把这个 \(\sum_q\) 改掉：\(\frac{1}{n}\sum_{g|n}\varphi(\frac{n}{g})[y^k](\prod_{i=0}^{n/g-1}(1+w^{gi}y))^g\)。

\(\prod_{i=0}^{n/g-1}(1+w^{gi}y)^g=\prod_{i=0}^{n/g-1}(1+\omega_{n/g}^iy)^g\)。不妨设 \(m=\frac{n}{g}\)。
对于单位根有分解 \(z^m-1=\prod_{i=0}^{m-1}(z-\omega_{m}^i)\)。
带入 \(z=-\frac{1}{x}\) 得到：

\[\begin{aligned} (-\frac{1}{x})^m-1&=\prod_{i=0}^{m-1}(-\frac{1}{x}-\omega_w^i)\\ (-\frac{1}{x})^m-1&=(-\frac{1}{x})^m\prod_{i=0}^{m-1}(1+x\omega_m^i)\\ 1-(-x)^m&=\prod_{i=0}^{m-1}(1+x\omega_m^i) \end{aligned} \]

故 \(\frac{1}{n}\sum_{g|n}\varphi(\frac{n}{g})[y^k](1-(-y)^{n/g})^g\)。
二项式展开计算，\(O(d(n)k)\)。

由于无法提交，把代码粘在这里吧。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL P=1e9+7;
LL n,k,ans;
LL ksm(LL a,LL b) { LL res=1; for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P; return res; }
LL phi(LL n)
{
	LL res=n;
	for(LL i=2;i*i<=n;i++)
	{
		if(n%i) continue;
		res=res/i*(i-1);
		while(n%i==0) n/=i;
	}
	if(n>1) res=res/n*(n-1);
	return res;
}
LL C(LL a,LL b)
{
	LL res=1;
	for(int i=1;i<=b;i++) res=res*(a-i+1)%P*ksm(i,P-2)%P;
	return res;
}
void solve(LL g)
{
	if(k%(n/g)) return;
	LL i=k/(n/g);
	ans=(ans+phi(n/g)*(k+i&1?P-1:1)%P*C(g,i)%P)%P;
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(LL d=1;d*d<=n;d++)
	{
		if(n%d) continue;
		solve(d);
		if(d*d!=n) solve(n/d);
	}
	printf("%lld",ans*ksm(n,P-2)%P);
	return 0;
}

CF1810G The Maximum Prefix

芝麻糊。

P8290 [省选联考 2022] 填树

先考虑链全局情况。查询 \(\sum_i f_{[i,i+k]}-f_{[i+1,i+k]}\)。
将值域划分成 \(O(n)\) 个段。
\(f_{[a,b]}\) 是若干个 \(S_{\Box}(a,r_i),S_{\Box}(a,b),S_{\Box}(l_i,b)\) 的乘积，\(\Box\) 是 0 或 1，分别表示求 0/1 次方和。
我们考虑 1 次方和的情况，0 次方和是这个的弱化。\(g(x)=x\) 是一次多项式，做前缀和是二次多项式，和另外 \(n\) 个方案数的乘积则是 \(n+1\) 次多项式。对 \(f\) 做一次前缀和得到 \(S_f\) 是 \(n+2\) 次多项式。
使用树形 dp 求出每条路径的 \(f_{[a,b]}\) 之和，可以换根 dp \(O(n)\) 求出。
插值求出多项式，可以做到 \(O(n^2)\)。
总复杂度 \(O(n^3)\)。