STEINS;GATE 0

El Psy Congroo.

原谅我不知道这套题的名字,所以我直接用“STEINS;GATE 0”了。

没有做出任何一道题,全是看的题解。

相互再归的鹅妈妈

题目大意

给定 01 字符串 $S$,重复 $k$ 次后形成的字符串表示的二进制数为 $R$。

求在 $[0,R-1]$ 中选 $n$ 个互不相同的整数,并使他们异或和为 $0$ 的方案数。

其中 $1\le n\le 7,|R|\le 5\times 10^6$。

题解

首先 $n=1$ 或 $2$ 时是很简单的。

但是之后该怎么办呢?

这个应该能看出来只能用容斥了吧。

所以我们设 $f(x)$ 表示有 $x$ 个不同数异或起来是 $R$,$g(x)$ 表示最多 $x$ 个不同的数异或起来是 $R$。

那么由 $f$ 得到 $g$ 就是一个无序集合划分,每个集合里的数相同。这个我不会。所以我们考虑把他变成有序的,最后再除 $n!$

那么元素是有序之后,就有
$$
g(n)=\sum_{i=1}^{n}{\left\{
\begin{matrix}
n\\
i\\
\end{matrix}
\right\}f(i)}
$$
,然后呢根据斯特林反演,有
$$
f(n)=\sum_{i=1}^{n}{(-1)^{n-i}\left[
\begin{matrix}
n\\
i\\
\end{matrix}
\right]g(i)}
$$

所以题解是写复杂了吧。

然后我就 wa 了。

为啥呢?

因为大小为偶数的集合最后答案是 $0$,而不是像奇数那样可以随便搞。

那怎么搞?

那我们对于每个序列都要专门算一下咯?

设 $f(\{a_n\})$ 表示 $\{1,2,…,n\}$ 的集合划分为 $\{a_n\}$,同一集合相同,不同集合不同,$g(\{a_n\})$ 表示同一集合相同,不同集合可相同可不相同,就有
$$
g\left(\left\{a_n\right\}\right)=\sum_{\{b_n\}}f\left(\left\{\cup_{i\in b_n}a_i\right\}\right)
$$
其中 $\{b_n\}$ 是 $\{1,2,…,|\{a_n\}|\}$ 的一个集合划分。

很显然,对于 $g$ 而言,相同的数个集合合并后就是 $f$,所以枚举哪些集合是相同的。

现在考虑如何求 $f(\{1,2,…,n\})$。考虑使用类似反演的方式,设每个 $g(\{a_n\})$ 的系数为 $h(\{a_n\})$,有
$$
\begin{align*}
f(\{1,2,…,n\})&=\sum_{\{a_n\}}h(\{a_n\})g(\{a_n\})\\
&=\sum_{\{a_n\}}h(\{a_n\})\sum_{\{b_n\}}f\left(\left\{\cup_{i\in b_n}a_i\right\}\right)\\
\end{align*}
$$
其中 $\{b_n\}$ 是 $\{1,2,…,|\{a_n\}|\}$ 的集合划分。按照套路枚举 $f$ 的“下标”,也就是集合划分,
$$
\begin{align*}
f(\{1,2,…,n\})&=\sum_{\{a_n\}}f(\{a_n\})\sum_{\{b_1\},\{b_2\},…,\{b_{|\{a_n\}|}\}}h(\{b_{1,1},…,b_{|\{a_n\}|,|b_{|\{a_n\}|}|}\})\\
\end{align*}
$$

如果我们定义集合的集合划分为把其中的每个集合进行集合划分在丢到一个集合里,那么 $f(\{a_n\})$ 的系数是 $\sum\limits_{\{b_n\}是 \{a_n\}的集合划分}h(\{b_n\})$。现在我们希望的是 $f(\{1,2,…,n\})$ 的系数是 $1$,其他的 $f$ 的系数都是 $0$,即
$
h(\{1,2,…,n\})=1\\
h(\{\{1,2\},3,…,n\})=-(h(\{1,2,…,n\}))=-1\\
h(\{\{1,3\},2,4,…,n\})=-(h(\{1,2,…,n\}))=-1\\
h(\{\{1,2,3\},4,…,n\})=-(h(\{1,2,…,n\})+h(\{\{1,2\},3,…,n\})+h(\{\{1,3\},2,…,n\})+h(\{\{2,3\},1,4,…,n\}))=-(1-1-1-1)=2\\
h(\{\{1,2,4\},3,5,…,n\})=-(h(\{1,2,…,n\})+h(\{\{1,2\},3,…,n\})+h(\{\{1,4\},2,3,5,…,n\})+h(\{\{2,4\},1,3,5,…,n\}))=-(1-1-1-1)=2\\
\cdots
$
发现只要两个划分中每个集合的大小对应相等,由于对称性,它们的系数也是相等的。所以我们简化一下 $h$ 的输入,把一个集合划分改为一个集合划分中每个集合大小的集合,对于一个这样的集合,它的集合划分就是把它每个元素进行正整数拆分。
$
h(\{1,…,1\})=1\\
h(\{2,1,…,1\})=-1\\
h(\{3,1,…,1\})=2\\
h(\{3,2,1,…,1\})=…=-2\\
h(\{3,3,1,…,1\})=…=4
$

诶?$h(\{a,b\})$ 好像等于 $h(\{a\})\cdot h(\{b\})$?

如何考虑?使用数学归纳法。

首先在集合中加入 $1$ 对答案没有影响,因为 $1$ 无法进行拆分,所以 $h(\{a_1,a_2,…,a_n,1\})=h(\{a_1,a_2,…,a_n\})\cdot h(\{1\})$。

然后对于 $h(\{a_1,a_2\,…,a_n\}),\exists a_i\gt 1$,有
$$\sum_{\{b_1\},…,\{b_n\}}h(\{b_{1,1},…,b_{n,k}\})\prod_{i=1}^{n}u(a_i,\{b_i\})=0$$
其中 $u(a,\{b\})$ 表示把大小为 $a$ 的集合拆分成大小为 $\{b\}$ 的集合的方案数,所以进行归纳
$$
\begin{align*}
\sum_{\{b_1\},…,\{b_n\}}h(\{b_{1,1},…,b_{n,k}\})\prod_{i=1}^{n}u(a_i,\{b_i\})&=0\\
\prod_{i=1}^{n}\sum h(\{b_{i,1},…,b_{i,k}\})u(a_i,\{b_i\})-\prod_{i=1}^{n}h(\{a_i\})+h(\{a_1,…,a_n\})&=0\\
h(\{a_1,…,a_n\})&=\prod_{i=1}^{n}h(\{a_i\})
\end{align*}
$$

我们设 $v(\{a_n\})$ 表示在反演式中 $f(\{a_n\})$ 的系数,显然有
$$
\begin{align*}
v(\{a_n\})&=\prod_{i=1}^{n}[a_i=1]\\
v(\{a_n\})&=\sum_{\{b_1\},…,\{b_n\}}h(\{b_{1,1},…,b_{n,k}\})\prod_{i=1}^{n}u(a_i,\{b_i\})\\
&=\sum_{\{b_1\}}\left(h(\{b_1\})u(a_1,\{b_1\})\sum_{\{b_2\}}\left(h(\{b_2\})u(a_2,\{b_2\})\sum…\right)\right)\\
&=\prod_{i=1}^{n}\sum_{\{b_i\}}h(\{b_i\})u(a_i,\{b_i\})
\end{align*}
$$
要是我们使用最开始的 $h$ 的定义,那么就是要找到一个 $h$ 满足
$$
[S=\{1\}]=\sum_{\{a_n\}}h(\{a_n\})
$$
其中 $\{a_n\}$ 是 $S$ 的一个集合划分,并且 $h$ 只和每个 $a_i$ 的大小有关。

正好有这么个东西,当 $h(\{a_n\})=\prod_{i=1}^{n}(a_i-1)!(-1)^{a_i-1}$,有
$$
\begin{align*}
\sum_{\{a_n\}}h(\{a_n\})&=\sum_{\{a_n\}}\prod_{i=1}^{k}(a_i-1)!(-1)^{a_i-1}\\
&=\sum_{i=1}^{n}\sum_{|\{a_n\}|=i}\prod_{j=1}^{i}(a_j-1)!(-1)^{a_j-1}
\end{align*}
$$
可以发现这就是在枚举把一个序列分成 $i$ 个环排列的方案数,即
$$
\sum_{i=1}^{n}(-1)^{n-i}\left[\begin{matrix}n\\i\end{matrix}\right]
$$
然后根据斯特林数和递降阶乘的关系有
$$
(x)_n=\sum_{i=0}^{n}(-1)^{n-i}\left[\begin{matrix}n\\i\end{matrix}\right]x^i
$$
当 $x=1$ 时,
$$
\sum_{i=1}^{n}(-1)^{n-i}\left[\begin{matrix}n\\i\end{matrix}\right]=(1)_n-(-1)^n\left[\begin{matrix}n\\0\end{matrix}\right]
$$
这里我们只考虑 $n$ 为正整数,所以 $(1)_n=[n=1],\left[\begin{matrix}n\\0\end{matrix}\right]=0$,那么
$$
[n=1]=\sum_{\{a_n\}}\prod_{i=1}^{k}(a_i-1)!(-1)^{a_i-1}
$$
系数就可以很简单地求到了。

接下来我们考虑如何求 $g$。

首先我们肯定是要枚举集合划分得到 $h$,然后由于要求集合中元素相等,集合大小为偶数的最后异或和一定是零,所以可以随便填;大小为奇数的最后异或只剩一个数,所以当成一个数。其实我们现在要求的是我们最开始的那个 $g$。

考虑某一位 $1$ 之前所有数都和 $R$ 一样,这一位有 $2k$ 个数填 $1$,这些数要保证在 $R$ 内。剩下的数已经小于 $R$ 了,我们留一个数出来把异或和调成 $0$,其余随便填。

需要注意的是如果这一位之前出现了 $1$ 那么就只能是偶数个数。

时间复杂度 $\mathcal O(n|R|+B_n)$

呼,终于写完了。

代码

常数暴大,写得巨丑。

/*-Aria on the Planetes-*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int,int> Pii;
template<class _T>inline void rd(_T&_a){int _f=0,_ch=getchar();_a=0;while(_ch<'0'||_ch>'9'){if(_ch=='-')_f=1;_ch=getchar();}while(_ch>='0'&&_ch<='9')_a=_a*10+_ch-'0',_ch=getchar();if(_f)_a=-_a;}
template<class _T>inline _T dmin(const _T _a,const _T _b){return _a<_b?_a:_b;}
template<class _T>inline _T dmax(const _T _a,const _T _b){return _a>_b?_a:_b;}
template<class _T>inline bool cmin(_T &_a,const _T _b){return _a>_b?_a=_b,1:0;}
template<class _T>inline bool cmax(_T &_a,const _T _b){return _a<_b?_a=_b,1:0;}
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define eb emplace_back
#define fir first
#define sec second
const int inf=0x3f3f3f3f;
const D eps=1e-8;
const int N=8,M=5e6+5,mod=1e9+7;
int n,a[M],f[N];LL g[N],c[N][N],w[M],p2[M][N],pw[M][N],s[N][N],ans,fac[N];
char str[M];
LL fp(LL x,LL y){LL r=1;for(;y;y>>=1,(x*=x)%=mod)if(y&1)(r*=x)%=mod;return r;}
void dfs(int ct,int u){
    if(u==n){
        LL h=1;int cnt=0;
        for(int i=1;i<=ct;i++)(h*=fac[f[i]-1]*(f[i]&1?1:-w[1])%mod)%=mod,cnt+=f[i]&1;
        (ans+=h*g[cnt])%=mod;
        return;
    }
    for(int i=1;i<=ct+1;i++)f[i]++,dfs(max(i,ct),u+1),f[i]--;
}
int main(){
    //freopen("mothergoose.in","r",stdin);
    //freopen("mothergoose.out","w",stdout);
    int x,m;rd(n);rd(x);scanf("%s",str+1);m=strlen(str+1);
    for(int i=0;i<x;i++)for(int j=1;j<=m;j++)a[i*m+j]=str[j]-'0';
    m*=x;
    for(int i=fac[0]=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    for(int i=m,p=1;i;i--,(p<<=1)%=mod)w[i]=(w[i+1]+p*a[i])%mod;
    for(int i=0;i<=n;i++)for(int j=0;j<=i;j++)c[i][j]=j?(c[i-1][j-1]+c[i-1][j])%mod:1;
    for(int i=0,p=1;i<=m+1;i++,(p<<=1)%=mod)
        for(int j=0;j<=n;j++)p2[i][j]=j?p*p2[i][j-1]%mod:1,pw[i][j]=j?w[i]*pw[i][j-1]%mod:1;
    for(int i=g[0]=1,fl=0;i<=m;fl|=a[i],i++)if(a[i])for(int j=1;j<=n;j++)
        if(!fl||!(j&1))for(int k=0;k<=(j-1>>1);k++)(g[j]+=c[j][k<<1]*pw[i+1][k<<1]%mod*p2[m-i][j-(k<<1)-1])%=mod;
    dfs(0,0);
    printf("%lld",(ans*fp(fac[n],mod-2)%mod+mod)%mod);
    return 0;
}

盟誓的文艺复兴

题目大意

求区间 $[l,r]$ 中,有多少数能表示成 $ab^c$ 的形式,满足 $a\ge 1,b,c\gt 1,a\lt b$。

其中 $1\le l\le r\le 8\times 10^{16}$。

题解

稍有常识的人都知道肯定算 $[1,n]$ 的嘛。

可以发现当 $c$ 是偶数时,都可以转换成 $c=2$ 的情况。当 $c$ 是奇数时呢?还是可以。只是要注意 $c=3$ 时由于 $b\le ab$,所以不行。所以所有合法的数一定可以用 $c=2,3$ 来表示。

当 $c=2$ 时,这个比较简单,直接算每个不含有平方因子的 $a$ 有多少满足的 $b$ 就行了,是
$$
\sum_{a=1}^{n^\frac{1}{3}}{\mu^2(a)\left(\left\lfloor\sqrt{\cfrac{n}{a}}\right\rfloor-a\right)}
$$

注意到这里巧妙地使用了 $\mu$ 函数的平方来判断平方因子,并且由于 $b\gt a$,所以只用枚举到 $n^{\frac{1}{3}}$。

那么当 $c=3$ 时呢?首先我们要保证它不能表示成 $c=2$ 的形式。我们假设 $k$ 是最大的满足 $k^2\mid ab$ 的整数,那么有 $ab^3=(ab)b^2=\cfrac{ab}{k^2}(bk)^2$,所以要满足 $\cfrac{ab}{k^2}\ge bk$,即 $a\ge k^3$。