「ABC 196A」Difference Max

Link.

略。

#include<cstdio>
long long a,b,c,d;
int main(){
    scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
    printf("%lld\n",b-c);
    return 0;
}

「ABC 196B」Round Down

Link.

略。

#include<cstdio>
#include<cstring>
char s[10000];
int main(){
    scanf("%s",s);int len=strlen(s);
    for(int i=0;i<len;++i)if(s[i]^'.')putchar(s[i]);else break;
    return 0;
}

「ABC 196C」Doubled

Link.

分类讨论即可，可能会有点点细节需要注意。

#include<cstdio>
#include<algorithm>
using namespace std;
long long n;
int dig[20],cnt;
long long qpow(long long bas,long long fur){long long res=0;for(long long i=1;i<=fur;++i)res=res*10+9;return res;}
long long getnum(int l,int r){long long res=0;for(int i=r;i>=l;--i)res=res*10+dig[i];return res;}
int main(){
    scanf("%lld",&n);long long bk=n;do dig[++cnt]=bk%10,bk/=10; while(bk);
    if(cnt==1)return puts("0"),0;int lm=(cnt>>1);
    long long pre=getnum(cnt-lm+1,cnt),suf=getnum(1,lm);
    if(cnt&1)printf("%lld\n",qpow(9,lm));
    else{
        if(pre<=suf)printf("%lld\n",pre);
        else printf("%lld\n",pre-1);
    }
    return 0;
}
/*
23333

3 3 3 3 2

232
*/

「ABC 196D」Hanjo

Link.

暴搜。

#include<iostream>
using namespace std;
int h,w,a,b,ans;
void dfs(int solvedNumber,int stateBoard,int leftLongerBlock,int leftCenterBlock)
{
    if(solvedNumber==h*w)    ++ans;
    else
    {
        if(stateBoard&(1<<solvedNumber))    return dfs(solvedNumber+1,stateBoard,leftLongerBlock,leftCenterBlock);
        if(leftLongerBlock)
        {
            if((solvedNumber%w!=w-1)&&(!(stateBoard&(1<<(solvedNumber+1)))))    dfs(solvedNumber+1,stateBoard|(1<<solvedNumber)|(1<<(solvedNumber+1)),leftLongerBlock-1,leftCenterBlock);
            if(solvedNumber+w<h*w)    dfs(solvedNumber+1,stateBoard|(1<<solvedNumber)|(1<<(solvedNumber+w)),leftLongerBlock-1,leftCenterBlock);
        }
        if(leftCenterBlock)    dfs(solvedNumber+1,stateBoard|(1<<solvedNumber),leftLongerBlock,leftCenterBlock-1);
    }
}
int main()
{
    cin >> h >> w >> a >> b;
    dfs(0,0,a,b); cout << ans << "\n";
    return 0;
}

「ABC 196E」Filters

Link.

这是个 Segment Tree Beats 的板子，不打了。

// Oops, something went wrong.

「ABC 196F」Substring 2

Link.

你 ABC 考 FFT 字符串匹配。

定义匹配函数 $f(x)=\sum_{i=0}^{|T|-1}(S_{x+i}-T_{i})^{2}=\sum_{i=0}^{|T|-1}S^{2}_{x+i}-2\sum_{i=0}^{|T|-1}S_{x+i}T_{i}+\sum_{i=0}^{|T|-1}T_{i}^{2}$。

然后反转 $T$ 卷积即可。

#include<cstdio>
#include<numeric>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MOD=998244353,INF=numeric_limits<int>::max();
void exGCD(int one,int ano,int &x,int &y)
{
    if(ano==0)    x=1,y=0;
    else    exGCD(ano,one%ano,y,x),y-=(one/ano)*x;
}
int getInv(int val){int res,w; exGCD(val,MOD,res,w); return (res+MOD)%MOD;}
int qpow(int bas,int fur)
{
    int res=1;
    while(fur)
    {
        if(fur&1)    res=LL(res)*bas%MOD;
        bas=LL(bas)*bas%MOD;
        fur>>=1;
    }
    return res%MOD;
}
namespace Poly
{
    typedef vector<int> poly;
    #define len(x) (int((x).size()))
    int lim,rev[4000010];
    void ntt(poly &f,int op)
    {
        for(int i=0;i<lim;++i)    if(i<rev[i])    swap(f[i],f[rev[i]]);
        for(int len=2;len<=lim;len<<=1)
        {
            int bas=qpow(op==1?3:332748118,(MOD-1)/len);
            for(int fr=0;fr<lim;fr+=len)
            {
                int now=1;
                for(int ba=fr;ba<fr+(len>>1);++ba,now=LL(now)*bas%MOD)
                {
                    int tmp=LL(now)*f[ba+(len>>1)]%MOD;
                    f[ba+(len>>1)]=(f[ba]-tmp+MOD)%MOD;
                    f[ba]=(f[ba]+tmp)%MOD;
                }
            }
        }
        if(op==-1)
        {
            int tmp=getInv(lim);
            for(int i=0;i<lim;++i)    f[i]=LL(f[i])*tmp%MOD;
        }
    }
    poly operator*(poly f,poly g)
    {
        int n=len(f)+len(g)-1; lim=1;
        while(lim<n)    lim<<=1;
        f.resize(lim),g.resize(lim);
        for(int i=0;i<lim;++i)    rev[i]=(rev[i>>1]>>1)|((i&1)?(lim>>1):0);
        ntt(f,1),ntt(g,1);
        for(int i=0;i<lim;++i)    f[i]=LL(f[i])*g[i]%MOD;
        ntt(f,-1),f.resize(n);
        return f;
    }
    poly operator*(int x,poly f){for(int i=0;i<len(f);++i)    f[i]=LL(f[i])*x%MOD; return f;}
    poly operator-(poly f,poly g)
    {
        int n=max(len(f),len(g));
        f.resize(n),g.resize(n);
        for(int i=0;i<len(f);++i)    f[i]=(f[i]-g[i]+MOD)%MOD;
        return f;
    }
    poly operator+(poly f,poly g)
    {
        int n=max(len(f),len(g));
        f.resize(n),g.resize(n);
        for(int i=0;i<len(f);++i)    f[i]=(f[i]+g[i])%MOD;
        return f;
    }
}using namespace Poly;
int main()
{
    string S,T;
    cin >> S >> T; reverse(T.begin(),T.end());
    poly onesi,anosi,onexsi,anoxsi;
    #define Sqr(x) ((LL)(x)*(x)%MOD)
    onesi.push_back(Sqr((*S.begin())-'0'));
    anosi.push_back(Sqr((*T.begin())-'0'));
    for(int i=1;i<len(S);++i)    onesi.push_back(onesi.back()+Sqr(S[i]-'0'));
    for(int i=1;i<len(T);++i)    anosi.push_back(anosi.back()+Sqr(T[i]-'0'));
    for(char c : S)    onexsi.push_back(c-'0'); for(char c : T)    anoxsi.push_back(c-'0');
    poly tmp=2*onexsi*anoxsi; int ans=INF;
    #define getValue(i) (((i)<(len(T)))?0:onesi[(i)-len(T)])
    for(unsigned int i=T.size()-1;i<S.size();++i)    ans=min(ans,onesi[i]-getValue(i)+anosi[len(T)-1]-tmp[i]);
    printf("%d\n",ans);
    return 0;
}

Description

Link.

包里有无穷多个巧克力，巧克力有 $c$ 种颜色，每次从包里拿出不同颜色巧克力的概率都是相等的，桌面的巧克力不允许颜色相同，若某次拿出的巧克力与桌上的巧克力颜色相同了，则将两颗巧克力都吃掉。计算进行 $n$ 次拿巧克力的操作后，桌上有 $m$ 颗巧克力的概率。

Solution

本质是给在 $c$ 种颜色选 $m$ 种颜色每种选奇数次，剩下 $c-m$ 中每种选偶数次。

构造那 $c-m$ 种和 $m$ 种的 egf：

$$ \begin{aligned} G_{1}(x)&=\sum_{i=0}^{\infty}\frac{x^{2i}}{(2i)!} \\ G_{2}(x)&=\sum_{i=0}^{\infty}\frac{x^{2i+1}}{(2i+1)!} \end{aligned} $$

换成 $e$ 的形式:

$$ \begin{aligned} G_{1}(x)&=\frac{e^{x}-e^{-x}}{2} \\ G_{2}(x)&=\frac{e^{x}+e^{-x}}{2} \end{aligned} $$

那么方案数的 ogf 为：

$$ G(x)=\left(\frac{e^{x}-e^{-x}}{2}\right)^{m}\times\left(\frac{e^{x}+e^{-x}}{2}\right)^{c-m} $$

那么答案即为：

$$ \frac{[G_{n}]\times n!\times\binom{c}{m}}{c^{n}} $$

考虑怎么求出 $[G_{n}]$。我们把 $G$ 看成关于 $e^{x}$，然后二项式展开后卷积：

$$ \begin{aligned} G(x)&=\left(\frac{e^{x}-e^{-x}}{2}\right)^{m}\times\left(\frac{e^{x}+e^{-x}}{2}\right)^{c-m} \\ &=2^{-c}\times\left(\sum_{i=0}^{m}\binom{m}{i}(-1)^{i}e^{x(m-2i)}\right)\times\left(\sum_{i=0}^{c-m}\binom{c-m}{i}e^{(2i+m-c)x}\right) \\ &=2^{-c}\times\left(\sum_{i=0}^{m}\sum_{j=0}^{c-m}(-1)^{i}\binom{m}{i}\binom{c-m}{j}e^{x(2m-2i+2j-c)}\right) \\ &=2^{-c}\times\left(\sum_{i=0}^{m}\sum_{j=0}^{c-m}(-1)^{i}\binom{m}{i}\binom{c-m}{j}\left(\sum_{k=0}^{\infty}\frac{(x(2m-2i+2j-c))^{k}}{k!}\right)\right) \end{aligned} $$

这份代码是在 POJ 上过的，至于 UVa 这边不想管了。

#include<bits/stdc++.h>
using namespace std;
int comb[210][210],c,n,m;
double ans;
double qpow(double bas,int fur)
{
    double res=1;
    while(fur)
    {
        if(fur&1)    res*=bas;
        bas*=bas;
        fur>>=1;
    }
    return res;
}
int main()
{
    for(int i=0;i<=100;++i)    comb[i][0]=comb[i][i]=1;
    for(int i=2;i<=100;++i)    for(int j=1;j<i;++j)    comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
    while(~scanf("%d",&c)&&c)
    {
        ans=0;
        scanf("%d %d",&n,&m);
        if(m>c||m>n||(n-m)%2)    puts("0.000");
        else
        {
            for(int i=0,now=1;i<=m;++i,now*=-1)    for(int j=0;j<=c-m;++j)    ans+=now*comb[m][i]*comb[c-m][j]*qpow(double(2*m-2*i+2*j-c)/c,n);
            ans*=comb[c][m]; ans/=qpow(2,c);
            printf("%.3f\n",ans);
        }
    }
    return 0;
}

Description

Link.

给定一个数列 $\sf a_1,a_2,....a_n$，请求出下面这个结果在模 $\sf 998244353$ 下的答案。

$$ \sum_{i=1}^{n}\sum_{j=1}^{n}2^{a_i a_j} $$

Solution

这题涉及一个 trick：$\sf ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}$，是 UQ 里面 EI 给我讲的，说明一下。

首先我们令 $\sf c_{a_{i}}=the~number~of~the~occurrences~of~a_{i},mx=\max\{a_{i}\}$。

然后来推式子：

$$ \begin{aligned} \sf\sum_{i=1}^{n}\sum_{j=1}^{n}2^{a_{i}a_{j}}&=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}2^{ij} \\ &=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}2^{\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}} \\ &=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}2^{\binom{i+j}{2}}2^{-\binom{i}{2}}2^{-\binom{j}{2}} \\ &=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}2^{\binom{i+j}{2}}2^{-\binom{i}{2}}2^{-\binom{j}{2}} \\ \end{aligned}\\ $$

现在我们令 $\sf t_{i}=2^{\binom{i}{2}},it_{i}=2^{-\binom{i}{2}}$。

那么 $\sf i+j$ 那项你就直接拿出来最后单独算即可。

$$ \begin{aligned} \sf\sum_{i=1}^{n}\sum_{j=1}^{n}2^{a_{i}a_{j}} &=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}2^{\binom{i+j}{2}}2^{-\binom{i}{2}}2^{-\binom{j}{2}} \\ &=\sf\sum_{i=1}^{mx}\sum_{j=1}^{mx}c_{i}c_{j}t_{i+j}it_{i}it_{j} \\ \end{aligned}\\ $$

最后直接算：

$$ \sf \sum_{i=1}^{mx}\sum_{j=0}^{mx-1}c_{i}it_{i}c_{i-j}it_{i-j} $$

卷积 完了。

记住模数非质的时候不一定有逆元啊啊啊啊！！！！

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD=998244353;
void exGCD(LL one,LL ano,LL &x,LL &y)
{
    if(ano==0)    x=1,y=0;
    else    exGCD(ano,one%ano,y,x),y-=(one/ano)*x;
}
LL getInv(LL val,LL _MOD){LL res,w; exGCD(val,_MOD,res,w); return (res%_MOD+_MOD)%_MOD;}
LL fspow(LL bas,LL fur)
{
    LL res=1;
    while(fur)
    {
        if(fur&1)    res=LL(res)*bas%MOD;
        bas=LL(bas)*bas%MOD;
        fur>>=1;
    }
    return (res+MOD)%MOD;
}
LL fac[200010],ifac[200010];
//LL binom(LL n,LL k){return n>=k?LL(fac[n])*ifac[k]%(MOD-1)*ifac[n-k]%(MOD-1):0;}
LL binom(LL n,LL k){return n>=k?LL(n)*(n-1)/2%(MOD-1):0;}
namespace Poly
{
    typedef vector<LL> poly;
    #define len(x) (LL((x).size()))
    LL lim,rev[800010];
    void ntt(poly &f,LL op)
    {
        for(LL i=0;i<lim;++i)    if(i<rev[i])    swap(f[i],f[rev[i]]);
        for(LL len=2;len<=lim;len<<=1)
        {
            LL bas=fspow(op==1?3:332748118,(MOD-1)/len);
            for(LL fr=0;fr<lim;fr+=len)
            {
                LL now=1;
                for(LL ba=fr;ba<fr+(len>>1);++ba,now=LL(now)*bas%MOD)
                {
                    LL tmp=LL(now)*f[ba+(len>>1)]%MOD;
                    f[ba+(len>>1)]=(f[ba]-tmp+MOD)%MOD;
                    f[ba]=(f[ba]+tmp)%MOD;
                }
            }
        }
        if(op==-1)
        {
            LL tmp=getInv(lim,MOD);
            for(LL i=0;i<lim;++i)    f[i]=LL(f[i])*tmp%MOD;
        }
    }
    poly operator*(poly f,poly g)
    {
        LL n=len(f)+len(g)-1; lim=1;
        while(lim<n)    lim<<=1;
        f.resize(lim),g.resize(lim);
        for(LL i=0;i<lim;++i)    rev[i]=(rev[i>>1]>>1)|((i&1)?(lim>>1):0);
        ntt(f,1),ntt(g,1);
        for(LL i=0;i<lim;++i)    f[i]=LL(f[i])*g[i]%MOD;
        ntt(f,-1),f.resize(n);
        return f;
    }
}using namespace Poly;
LL n,mx,c[100010],t[100010],it[100010],ans,ex[200010];
int main()
{
    poly f;
    scanf("%lld",&n);
    for(LL i=1,x;i<=n;++i)    scanf("%lld",&x),mx=max(mx,x),++c[x];
    f.resize(mx+1);
    fac[0]=1;
    for(LL i=1;i<=(mx<<1);++i)    fac[i]=LL(fac[i-1])*i%(MOD-1);
//    for(LL i=0;i<=(mx<<1);++i)    ifac[i]=getInv(fac[i],MOD-1);
//    printf("%lld\n",getInv(fac[2],MOD));
//    printf("(%lld %lld %lld %lld)\n",fac[2],ifac[2],ifac[0],binom(2,2));
    for(LL i=0;i<=mx;++i)    t[i]=fspow(2,binom(i,2));
    for(LL i=0;i<=mx;++i)    it[i]=getInv(t[i],MOD);
//    for(LL i=1;i<=mx;++i)    printf("%lld ",fac[i]); puts("");
//    for(LL i=1;i<=mx;++i)    printf("%lld ",binom(i,2)); puts("");
//    for(LL i=1;i<=mx;++i)    printf("%lld ",LL(i)*(i-1)/2%MOD); puts("");
    for(LL i=0;i<=mx;++i)    f[i]=LL(c[i])*it[i]%MOD;
    for(LL i=1;i<=(mx<<1);++i)    ex[i]=fspow(2,binom(i,2));
    f=f*f;
    for(LL i=0;i<len(f);++i)    ans=(ans+LL(f[i])*ex[i]%MOD)%MOD;
    printf("%lld\n",ans);
    return 0;
}

Part. 1 FFT

Part. 1-1 Main

对于一个 $n$ 次多项式 $F(x)=\sum_{i=0}^{n}a_{i}x^{i}$，在平面直角坐标系中可以由 $n+1$ 个点唯一确定。

考虑带什么样的 $x$ 进去，能够快速计算 $x^{n}$ 并且有一定的性质，DFT 采用的是复单位根。

那么 DFT 就是把 $F(x)$ 转为点值表示。我们来推式子：

先令 $L(x)=\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor-1}a_{2i}x^{2i},R(x)=\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor-1}a_{2i+1}x^{2i}$。

$$ \begin{aligned} F(\omega_{n}^{k})&=L((\omega_{n}^{k})^{2})+\omega_{n}^{k}R((\omega_{n}^{k})^{2}) \\ &=L(\omega_{n}^{2k})+\omega_{n}^{k}R(\omega_{n}^{2k}) \\ &=L(\omega_{\lfloor\frac{n}{2}\rfloor}^{k})+\omega_{n}^{k}R(\omega_{\lfloor\frac{n}{2}\rfloor}^{2k}) \\ \end{aligned} $$

同时：

$$ \begin{aligned} F(\omega_{n}^{k+\lfloor\frac{n}{2}\rfloor})&=L(\omega_{n}^{2k})+\omega_{n}^{k+\lfloor\frac{n}{2}\rfloor}R(\omega_{n}^{2k}) \\ &=L(\omega_{\lfloor\frac{n}{2}\rfloor}^{k})-\omega_{n}^{k}R(\omega_{\lfloor\frac{n}{2}\rfloor}^{k}) \end{aligned} $$

于是你直接分治，这是 DFT，注意要把多项式长度调整为 $2$ 的幂。

递归常数大，考虑迭代。你会发现分治后的序列与原序列的关系是下标的二进制反转，然后就完了。

void fft(Poly &f,int op)
{
    for(int i=0;i<lim;++i)    if(i<rev[i])    swap(f[i],f[rev[i]]);
    for(int len=2;len<=lim;len<<=1)
    {
        comp bas(cos(2*bh_pi/len),op*sin(2*bh_pi/len));
        for(int fr=0;fr<lim;fr+=len)
        {
            comp now(1,0);
            for(int ba=fr;ba<fr+(len>>1);++ba,now*=bas)
            {
                comp tmp=now*f[ba+(len>>1)];
                f[ba+(len>>1)]=f[ba]-tmp;
                f[ba]+=tmp;
            }
        }
    }
    if(op==-1)    for(int i=0;i<lim;++i)    f[i]/=lim;
}

Description

Link.

给出一个长度为 $n$ 的序列 $a$，问有序三元组 $(a_{i},a_{j},a_{k})$ 使得 $i\neq j\neq k$ 且 $a_{i}+a_{j}=a_{k}$ 的数量。

Solution

发现这个值域有说头，于是设 $F(x)=\sum_{i=1}^{n}x^{a_{i}}$。

然后求出 $F^{2}(x)$，判断一通就好了。

主要是记录一下这种多项式题的常用 trick，把值域小的整成多项式或者生成函数一类的。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace Poly
{
    typedef complex<double> comp;
    typedef vector<complex<double> > poly;
    #define len(x) (LL((x).size()))
    const double bh_pi=acos(-1);
    LL lim,rev[400010];
    void fft(poly &f,LL op)
    {
        for(LL i=0;i<lim;++i)    if(i<rev[i])    swap(f[i],f[rev[i]]);
        for(LL len=2;len<=lim;len<<=1)
        {
            comp bas(cos(2*bh_pi/len),op*sin(2*bh_pi/len));
            for(LL fr=0;fr<lim;fr+=len)
            {
                comp now(1,0);
                for(LL ba=fr;ba<fr+(len>>1);++ba,now*=bas)
                {
                    comp tmp=now*f[ba+(len>>1)];
                    f[ba+(len>>1)]=f[ba]-tmp;
                    f[ba]+=tmp;
                }
            }
        }
        if(op==-1)    for(LL i=0;i<lim;++i)    f[i]/=lim;
    }
    poly mulself(poly f)
    {
        LL n=(len(f)<<1)-1; lim=1;
        while(lim<n)    lim<<=1;
        for(LL i=0;i<lim;++i)    rev[i]=(rev[i>>1]>>1)|((i&1)?(lim>>1):0);
        f.resize(lim),fft(f,1);
        for(LL i=0;i<lim;++i)    f[i]*=f[i];
        fft(f,-1),f.resize(n);
        return f;
    }
}using namespace Poly;
LL n,mx,nzr,tmp[400010],a[400010],ans;
const LL lay=50000;
int main()
{
    scanf("%lld",&n);
    poly f(100001);
    for(LL i=1,x;i<=n;++i)
    {
        scanf("%lld",&x);
        mx=max(mx,lay+x);
        f[lay+x]=comp(f[lay+x].real()+1,0);
        nzr+=(x==0),a[i]=x;
    }
    ++mx;
    f.resize(mx);
    f=mulself(f);
    for(LL i=0;i<len(f);++i)    tmp[i]=LL(f[i].real()+0.49);
    for(LL i=1;i<=n;++i)    --tmp[(lay+a[i])<<1];
    for(LL i=1;i<=n;++i)
    {
        ans+=tmp[a[i]+(lay<<1)];
        if(a[i])    ans-=(nzr<<1);
        else    ans-=((nzr-1)<<1);
    }
    printf("%lld\n",ans);
    return 0;
}