Nescafé 41

其实我对混合咖啡还蛮有自信的

异化多肽

题目大意

有 $m$ 种氨基酸,每种氨基酸的相对分子质量为 $c_i$,这些氨基酸中的一些形成一条肽肽链。不计脱去水分子的质量,求最终形成肽链相对分子质量为 $n$ 的方案数。($\text{A-B}$ 与 $\text{B-A}$ 两条肽链视为不同)。

其中 $1\le n,m,c_i\le 10^5$

题解

不会诶。

背包?但是要记顺序。。。

就是把一个数拆分成多个数的和嘛,除开有顺序以外。

哎呀顺序真的好烦啊。

还是先考虑 DP 吧。这种背包每次都要把每样东西放一件进去。

$$dp_i=\sum_{j=1}^{n}{dp_{i-c_j}}$$

但是 $\mathcal O(n^2)$,无法接受。如何优化呢?

可以考虑把体积相同的物品合并:


$$
\begin{align*}
dp_0 & =1\\
dp_i & =\sum_{j=1}^{i}{dp_{i-j}\times cnt_j}
\end{align*}
$$

其中 $cnt_i$ 表示体积为 $i$ 的物品的数量。

这样还是过不了。试着展开一下:


\begin{align*}
dp_0 & =1\\
dp_1 & =dp_0\times cnt_1=cnt_1\\
dp_2 & =dp_0\times cnt_2+dp_1\times cnt_1=cnt_2+cnt_1^2\\
dp_3 & =dp_0\times cnt_3+dp_1\times cnt_2+dp_2\times cnt_1=cnt_3+2cnt1\times cnt_2+cnt_1^3\\
… & \\
dp_n & =\sum{\prod{cnt_i^{p_i}}|\sum{i\times p_i}=n}
\end{align*}

emmm.

看到这里,应该可以想到生成函数了。

如果你还不会生成函数,可以参考这篇博客:母函数 入门 + 模板

好了,现在你一定会母函数了。我们只需要知道最基础的,就是用指数表示目标,系数表示答案。

那么可以构造出:

$$F(x)=\sum{cnt_i\times x^i}$$

这是只选一个的方案数。选两个呢?平方一下就行。可以发现这样搞顺序上是没有漏算的。

所以有:

$$G(x)=\sum_{i=0}^{\infty}{F(x)^i}$$

$G(x)$ 中 $x^n$ 的系数即为答案。那么显然 $F(x)^{n+1}$ 及其之后的项对答案没有贡献,考虑前 $n+1$ 项即可。

好的那么现在就是一个等比多项式求值了,可以考虑使用分治 + FFT 在 $\mathcal O(n\times \log^2{n})$ 的时间复杂度解决。

然而要题目要求取模,所以其实要用 NTT。

那么这个模数的原根是多少呢?有两种办法搞:

  1. 随机生成一个数,看人品咯。
  2. 写个暴力跑一跑,发现 $5$ 是一个原根。

emmm.

【手动滑稽。

【【向使用 FFT 被卡精度的李爷致敬。

当然分治太难写了,而且不预处理的话其实是 $\mathcal O(n\times \log^3{n})$,真的超麻烦。

所以我们选择另一种搞法。

我们来看一看 $G(x)$ 到底是个啥。

如果你学习母函数是用一本名叫《信息学奥赛之数学一本通》的书的话,你一定对下面这个式子不陌生:

$$\cfrac{1}{1-x}=1+x+x^2+x^3+…$$

对吧?

这里就不证了,反正很简单。

那么显然的,适当的推证一下,可以发现:

$$G(x)=\cfrac{1}{1-F(x)}$$

所以这道题又变成了多项式求逆元。

推荐博客:多项式求逆元

这位巨巨写的超好,如果需要可以阅读他写的 FFT 等等的教程。

代码

/*"-Aria on the Planets-"*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int,int> Pii;
#define mp(a,b) make_pair(a,b)
#define fir first
#define sec second
inline int min(int _a,int _b){return _a<_b?_a:_b;}
inline int max(int _a,int _b){return _a>_b?_a:_b;}
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<<1)+(_a<<3)+_ch-'0',_ch=getchar();if(_f)_a=-_a;}
const int inf=0x3f3f3f3f;
const D eps=1e-8;
const int mod=1005060097,N=6e5+5;
LL a[N],b[N],tmp[N];
LL fp(LL a,LL b){LL r=1;for(;b;b>>=1,(a*=a)%=mod)if(b&1)(r*=a)%=mod;return r;}
void ntt(LL *a,int l,int f){
    for(int i=0,j=0;i<l;i++){if(j<i)swap(a[i],a[j]);for(int k=l>>1;(j^=k)<k;k>>=1);}
    for(int i=1;i<l;i<<=1){
        LL wn=fp(5,(mod-1)/(i<<1));
        for(int j=0;j<l;j+=i<<1){
            LL w=1;
            for(int k=0;k<i;k++,(w*=wn)%=mod){
                LL x=a[j+k],y=a[i+j+k]*w%mod;
                (a[j+k]=x+y)%=mod;
                (a[i+j+k]=x-y)%=mod;
            }
        }
    }
    if(f==-1){
        for(int i=1;i<l>>1;i++)swap(a[i],a[l-i]);
        LL inv=fp(l,mod-2);
        for(int i=0;i<l;i++)(a[i]*=inv)%=mod;
    }
}
void inv(int l){
    if(l==1){b[0]=fp(a[0],mod-2);return;}
    inv(l>>1);memcpy(tmp,a,sizeof(LL)*(l>>1));ntt(tmp,l,1);ntt(b,l,1);
    for(int i=0;i<l;i++)b[i]=(2-tmp[i]*b[i])%mod*b[i]%mod;
    ntt(b,l,-1);memset(b+(l>>1),0,sizeof(LL)*(l>>1));
}
int main(){
    //clock_t start=clock();
    //freopen("polypeptide.in","r",stdin);
    //freopen("polypeptide.out","w",stdout);
    int n,m,l=1;rd(n);rd(m);for(int i=1,x;i<=m;i++)rd(x),a[x]--;a[0]++;
    for(;l<n<<1;l<<=1);inv(l<<1);printf("%lld",(b[n]+mod)%mod);
    //printf("\n%dms",(int)((D)(clock()-start)/CLOCKS_PER_SEC*1000));
    return 0;
}

你们看我 ntt 连行都没压。


编码病毒

题目大意

给定两个 $n$ 位的二进制数 $a,b$,以及一个初始为零的 $m+2$ 位二进制数 $c$,其中 $c$ 的第 $1,2$ 位分别为 $x_1,x_2$,剩下的构成数 $C$。

现在你可以修改任何一个数的任何一位,并且修改的数位尽可能少,使得:

$a[i]=b[(i+(x_2\times 2-1)\times C)\ \mathrm{mod}\ n]\ \mathrm{xor}\ x_1\ (1\le i\le n)$

其中 $a[i],b[i]$ 表示二进制的第 $i$ 位。

其中 $1\le n\le 10^5,1\le m\le 22$。

题解

真的不会啊。

这体面啥啊。

太长了不想看啊。

于是就去看 t3 最后还是决定回来做 t2。

我们先来一点一点的化简这个式子。

可以发现对于同样的 $c$,这个式子就是在循环移动 $b$ 后使得 $b$ 的每一位与 $a$ 都相等或相反。

那么可以考虑把问题分成两部分:改 $c$ 和改 $a$ 或 $b$,很明显对于给定的 $c$ 改 $a$ 和 $b$ 是等效的。

那么 $(x_2\times 2-1)\times C$ 是在干嘛呢?

自己代 $x_2$ 的取值选一选,显然这就是个换方向。

那么我们想枚举一下移动多少位,然后统计 $a$ 和 $b$ 有多少位不同,再看需不需要取反或换移动的方向,同时看怎么改 $C$ 是最优的。

对于每一次枚举需要 $\mathcal O(n)$ 统计和 $\mathcal O(\cfrac{2^m}{n})$ 计算最优的 $C$,总时间复杂度 $\mathcal O(n^2+2^m)$,稳定爆炸。

那怎么搞呢?

显然,每一位只能为 $0$ 或 $1$。【废话。

所以上 bitset 咯。

自己去推一推 bitset 的循环位移怎么搞吧。

来细节地计算一波复杂度:

$$\cfrac{n^2}{32}+2^m\approx\frac{10^{10}}{32}+4\times 10^6=3.165\times 10^8\lt 4\times 10^8$$

诶嘿嘿~ 过了!

emmm.

【手动滑稽。

其实呢,这并不是正解。

有一道一个字符串匹配另一个字符串的子串的题,不知道你做没做过:BZOJ4503

【似乎还是个权限题。。。

是的这道题又是 FFT。。。

我日。

那么 FFT 是要把 $i+j=k$ 的 $i,j$ 推到 $k$ 上,这里的是 $i=j$,所以要翻转一个串。

然后我们考虑如果 $a[i]\times b[j]=1$ 加到 $c[k]$ 上,那么只有当 $a[i],b[j]$ 同为 $1$ 时才能给 $c[k]$ 加 $1$。

所以先翻转一个,然后卷一卷,然后把两个串取反,先翻转一个,然后卷一卷,分别统计相同的 $1$ 和 $0$ 的数量。注意第 $n+i$ 位实际就是第 $i$ 位,记得向右移动后移回来。

另外这道题虽然要求取模,不过稍有常识的人都知道,这个最大值。。。所以并不用 NTT,FFT 即可。【手动滑稽。

代码

bitset

/*"-Aria on the Planets-"*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int,int> Pii;
#define mp(a,b) make_pair(a,b)
#define fir first
#define sec second
inline int min(int _a,int _b){return _a<_b?_a:_b;}
inline int max(int _a,int _b){return _a>_b?_a:_b;}
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<<1)+(_a<<3)+_ch-'0',_ch=getchar();if(_f)_a=-_a;}
const int inf=0x3f3f3f3f;
const D eps=1e-8;
const int N=1e5+5;
int c[1<<23];bitset<N>s1,s2,t;
int main(){
    //clock_t start=clock();
    //freopen("virus.in","r",stdin);
    //freopen("virus.out","w",stdout);
    int m,n,ans=inf;rd(m);rd(n);
    for(int i=0,x;i<n;i++)scanf("%1d",&x),s1[i]=x;
    for(int i=0,x;i<n;i++)scanf("%1d",&x),s2[i]=x;
    for(int i=1;i<1<<m;i++)c[i]=c[i-(i&-i)]+1;
    for(int i=0;i<n;i++){
        int t1=0,t2=inf;
        t1=(s1^s2).count();
        for(int j=i;j<1<<m;j+=n)t2=min(t2,c[j]);
        for(int j=n-i;j<1<<m;j+=n)t2=min(t2,c[j]+1);
        ans=min(ans,t2+min(t1,n-t1+1));
        t=s2>>1;t[n-1]=s2[0];s2=t;
    }
    printf("%d",ans);
    //printf("\n%dms",(int)((D)(clock()-start)/CLOCKS_PER_SEC*1000));
    return 0;
}

FNT

贴的标程,自己没写

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int modi=1005060097,prime_root=5;
const int N=1<<18;
char data[N],test[N];
int n,m,a[N],b[N],c[N],d[N],s[N],f[1<<22],ans=0x7fffffff;
int w[N],ls1[N],ls2[N];
int power(int a,int b)
{
    int r=1;
    while(b)
    {
        if(b&1)r=(long long)r*a%modi;
        a=(long long)a*a%modi;
        b>>=1;
    }
    return r;  
}
int ni(int x){return power(x,modi-2);}
int Rev(int x,int y)
{
    int r=0;
    for(int i=0;i<y;i++){r=(r<<1)^(x&1);x>>=1;}
    return r;
}
void FFT(int *F,int bit,int offset)
{
    int i,j,k,W;
    for(i=0;i<(1<<bit);i++)
    if(Rev(i,bit)>i)swap(F[i],F[Rev(i,bit)]);
    for(i=1;i<=bit;i++)
    {
        for(j=0;j<(1<<bit);j+=(1<<i))
        {
            W=0;
            for(k=j;k<j+(1<<i-1);k++)
            {
                F[k]=(F[k]+(long long)F[k+(1<<i-1)]*w[W])%modi;
                F[k+(1<<i-1)]=((F[k]-((long long)F[k+(1<<i-1)]*w[W]<<1))%modi+modi)%modi;
                W+=offset*(1<<bit-i);
                if(W<0)W+=(1<<bit);
            }
        }
    }
}
void multi(int *a,int *b,int *c,int n)//卷积长度为N的离散序列a,b存于c(下标从0开始存储)
{
    int i,k,log_=0,NI,save=n;
    for(;k=n&(-n),(n^k)!=0;n+=k);
    n<<=1;
    while((1<<log_)<n)log_++;
    NI=ni(n);
    w[0]=1;w[1]=power(prime_root,(modi-1)/n);
    for(k=2;k<n;k++)w[k]=(long long)w[k-1]*w[1]%modi;
    for(k=0;k<save;k++)ls1[k]=a[k];
    for(k=0;k<save;k++)ls2[k]=b[k];
    for(k=save;k<n;k++)ls1[k]=ls2[k]=0;
    FFT(ls1,log_,1);
    FFT(ls2,log_,1);
    for(k=0;k<n;k++)c[k]=(long long)ls1[k]*ls2[k]%modi;
    FFT(c,log_,-1);
    for(k=0;k<n;k++)c[k]=(long long)c[k]*NI%modi;
}
int solve()
{
    int i,j,r=0x7fffffff;
    reverse(b,b+n);
    for(i=0;i<2*n;i++)c[i]=d[i]=0;
    multi(a,b,c,n);
    for(i=0;i<n;i++)a[i]^=1,b[i]^=1;
    multi(a,b,d,n);
    for(i=0;i<n;i++)c[i]+=c[i+n],d[i]+=d[i+n];
    for(i=0;i<n;i++)s[i]=n-(c[n-i-1]+d[n-i-1]);
    for(i=0;i<(1<<m);i++)r=min(r,f[i]+s[i%n]);
    return r;
}
int main()
{
    //freopen("virus.in","r",stdin);
    //freopen("virus.out","w",stdout);
    int i;
    for(i=1;i<(1<<22);i++)f[i]=f[i^(i&(-i))]+1;
    scanf("%d%d",&m,&n);
    scanf("%s",data);
    scanf("%s",test);
    for(int ord1=0;ord1<=1;ord1++)
    for(int ord2=0;ord2<=1;ord2++)
    {
        for(i=0;i<n;i++)a[i]=(data[i]-'0')^ord1;
        for(i=0;i<n;i++)b[i]=test[i]-'0';
        if(ord2){reverse(a,a+n);reverse(b,b+n);}
        ans=min(ans,solve()+ord1+ord2);
    }
    cout<<ans<<endl;
    return 0;
}

数论函数簇

题目大意

定义 $F_{n,a,b}(x)=(a\times x+b)\ \mathrm{mod}\ n\ (0\lt a\lt n,0\le b\lt n)$,$R(n)$ 为 $n$ 为定值时,对于 $\forall x$,$F_{n,a,b}(F_{n,a,b}(x))=F_{n,a,b}\ (x)$ 的不同的 $(a,b)$ 个数。

求 $\sum_{1\le i\le n}R(i)$

其中 $n\le 10^{11}$。

首先,非常显然的,可以得到这样的一个方程组:


$$
\begin{cases}
a^2\equiv a \pmod{n}\\
(a+1)\times b\equiv b \pmod{n}
\end{cases}
$$

可以得到 $$n\mid (a-1)\times a$$ 且 $$n\mid a\times b$$

那么可以枚举 $n,a$,对于合法的 $a$,$b$ 有 $\gcd(a,n)$ 种,时间复杂度 $\mathcal O(n^2)$,T 成傻逼。

然后我们再来考虑,显然,$\gcd(a,a-1)=1$,那么 $a,a-1$ 包含的质数一定是 $n$ 分解后的两部分不一样的质数。

设 $p,q$,有 $\gcd(p,q)=1,p\times q=n$,设 $a=k_1p,a-1=k_2q$,显然有 $k_1p\equiv 1\pmod{q}$,由 $k_1p\lt n$ 得出 $k_1\lt q$,所以方程一定有唯一解,对答案的贡献为 $\gcd(a,n)=\gcd(k_1p,n)=\gcd(p,n)=p$。

所以可以得到:


$$
R(n)=\sum_{\begin{align*}d \mid& n\\ d \lt & n\\ \gcd(d,&\frac{n}{d})=1\end{align*}}{d}
$$

设 $n=\prod{p_i^{e_i}}$,那么 $p=\prod{(p_i^{e_i})^{q_i}}$,其中 $$q_i\in{0,1},\prod{q_i}=0$$。

联想到因数和的计算,我们可以得到:

$$
R(n)=\prod{(p_i^{e_i}+1)}-n
$$

显然 $R(n)+n$ 为积性函数,可以使用线性筛得到,时间复杂度 $\mathcal O(n)$,照样 T。

可以自己推一推怎么筛,推荐一篇 ppt:线性筛法与积性函数

它第 $10$ 页的内容很有帮助。

回到本题,可以发现那个 $\text{-}n$ 是很好算的,那么剩下的部分该怎么搞呢?


$$
\begin{align*}
&\sum_{i\le n}{R(i)+i}\\
=&\sum_{i\le n}{\sum_{d\mid i}{[gcd(d,\frac{i}{d})=1]\times d}}\\
=&\sum_{i\le n}{\sum_{d\mid i}{\sum_{k\mid i,\frac{i}{d}}{\mu(k)}\times d}}\\
&设\ i=h\times d\\
=&\sum_{hd\le n\\k\mid h,d}{\mu(k)\times d}\\
&设\ d=i\times k,h=j\times k\\
=&\sum_{k^2ij\le n}{\mu(k)\times i\times k}\\
=&\sum_{k^2i\le n}{\mu(k)\times k\times i\times\lfloor \cfrac{n}{k^2\times i}\rfloor}
\end{align*}
$$

显然 $k$ 的取值只有 $\mathcal O(\sqrt{n})$ 种,所以考虑枚举 $k$。对于给定的 $k$,直接根号分块计算 $\sum_{i=1}^{\frac{n}{k^2}}{i\times \lfloor\cfrac{n}{k^2\times i}\rfloor}$ 即可。

来细节一波时间复杂度:

$$\sum_{i=1}^{\sqrt{n}}{\sqrt{\cfrac{n}{i^2}}}=\sum_{i=1}^{\sqrt{n}}{\cfrac{\sqrt{n}}{i}}\approx \sqrt{n}\log{\sqrt{n}}$$

所以其实是 $\mathcal O(\sqrt{n}\log{\sqrt{n}})$ 的。

代码

/*"-Aria on the Planets-"*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int,int> Pii;
#define mp(a,b) make_pair(a,b)
#define fir first
#define sec second
inline int min(int _a,int _b){return _a<_b?_a:_b;}
inline int max(int _a,int _b){return _a>_b?_a:_b;}
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<<1)+(_a<<3)+_ch-'0',_ch=getchar();if(_f)_a=-_a;}
const int inf=0x3f3f3f3f;
const D eps=1e-8;
const int mod=1005060097,N=1e6+5,inv2=502530049;
int isp[N],p[N/10],mu[N];
LL sl(LL n){LL r=0;for(LL i=1,j;i<=n;i=j+1){j=n/(n/i);LL x=(i+j)%mod,y=(j-i+1)%mod;(r+=x*y%mod*inv2%mod*(n/i))%=mod;}return r;}
int main(){
    //clock_t start=clock();
    //freopen("function.in","r",stdin);
    //freopen("function.out","w",stdout);
    int cnt=0;mu[1]=1;for(int i=2;i<N;i++){if(!isp[i]){p[cnt++]=i;mu[i]=-1;}for(int j=0,k;j<cnt&&(k=i*p[j])<N;j++){isp[k]=1;mu[k]=-mu[i];if(i%p[j]==0){mu[k]=0;break;}}}
    LL n,ans=0;rd(n);
    for(LL i=1;i*i<=n;i++)(ans+=mu[i]*i*sl(n/i/i))%=mod;
    n%=mod;printf("%lld",((ans-(n+1)*n/2)%mod+mod)%mod);
    //printf("\n%dms",(int)((D)(clock()-start)/CLOCKS_PER_SEC*1000));
    return 0;
}