In mathematics you don't understand things, you just get used to them.

动态 书籍 杂项 关于 友链

分类 笔记 下的文章

Description

Link.

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

Solution

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

构造那 c−mc-m 种和 mm 种的 egf：

G1(x)=∑i=0∞x2i(2i)!G2(x)=∑i=0∞x2i+1(2i+1)! \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}

换成 ee 的形式:

G1(x)=ex−e−x2G2(x)=ex+e−x2 \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)=(ex−e−x2)m×(ex+e−x2)c−m G(x)=\left(\frac{e^{x}-e^{-x}}{2}\right)^{m}\times\left(\frac{e^{x}+e^{-x}}{2}\right)^{c-m}

那么答案即为：

[Gn]×n!×(cm)cn \frac{[G_{n}]\times n!\times\binom{c}{m}}{c^{n}}

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

G(x)=(ex−e−x2)m×(ex+e−x2)c−m=2−c×(∑i=0m(mi)(−1)iex(m−2i))×(∑i=0c−m(c−mi)e(2i+m−c)x)=2−c×(∑i=0m∑j=0c−m(−1)i(mi)(c−mj)ex(2m−2i+2j−c))=2−c×(∑i=0m∑j=0c−m(−1)i(mi)(c−mj)(∑k=0∞(x(2m−2i+2j−c))kk!)) \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.

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

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

Solution

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

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

然后来推式子：

∑i=1n∑j=1n2aiaj=∑i=1mx∑j=1mxcicj2ij=∑i=1mx∑j=1mxcicj2(i+j2)−(i2)−(j2)=∑i=1mx∑j=1mxcicj2(i+j2)2−(i2)2−(j2)=∑i=1mx∑j=1mxcicj2(i+j2)2−(i2)2−(j2) \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}\\

现在我们令 ti=2(i2),iti=2−(i2)\sf t_{i}=2^{\binom{i}{2}},it_{i}=2^{-\binom{i}{2}}。

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

∑i=1n∑j=1n2aiaj=∑i=1mx∑j=1mxcicj2(i+j2)2−(i2)2−(j2)=∑i=1mx∑j=1mxcicjti+jitiitj \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}\\

最后直接算：

∑i=1mx∑j=0mx−1ciitici−jiti−j \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;
}

所以 Chinese Round 出 DS 是传统了对吧。

Description

Link.

Given is a rooted tree with the 1\sf1-th node as the root.

The tree will be given in this way: it will tell you that the parent of the i\sf i-th node is aia_{i}.

Supporting the following operations:

  • 1 l r x: let ∀i∈[l,r],ai=max{ai−x,1}\sf \forall i\in[l,r],a_{i}=max\{a_{i}-x,1\}.
  • 2 u v: find the LCA (Lowest Common Ancestor) of u\sf u and v\sf v.

Solution

经典永流传。

考虑到修改操作是对结点进行的操作，然后这个东西不太能直接 LCT 或树剖，考虑照序列来分块，那么我们来对结点编号分块。

  1. 修改；

\quad维护一个属性 topu\sf top_{u} 表示在原树上结点 u\sf u 的祖先中不和 u\sf u 在同一个块里面的编号最大的一个结点的编号，如果不存在的话就令 topu=1\sf top_{u}=1。这样的话你从结点 u\sf u 跳到 root 的复杂度为 O(n)\sf O(\sqrt{n})。接下来考虑怎么维护这个东西。

\quad散块我们直接暴力扫着改；对于整块，可以发现如果一个块的被修改次数超过了块的大小，那么就一定会有 topu=fau\sf top_{u}=fa_{u}。

  1. 询问。

\quad分三个类讨论，这个比较好做（差不多和树剖找 LCA 一个样子）。

#include<bits/stdc++.h>
using namespace std;
int n,m,top[100010],deln[320],tag[320],belong[100010],bl[320],br[320],fa[100010],bs;
#define gtlf(x) ((x-1)*bs+1)
#define gtrg(x) (min(x*bs,n))
void updtop(int x)
{
    if(belong[x]^belong[fa[x]])    top[x]=fa[x];
    else    top[x]=top[fa[x]];
}
void turndown(int x)
{
    if(tag[x])
    {
        for(int i=gtlf(x);i<=gtrg(x);++i)    fa[i]=max(fa[i]-tag[x],1);
        tag[x]=0;
    }
}
int main()
{
    scanf("%d %d",&n,&m),bs=sqrt(double(n))+1,fa[1]=belong[1]=1;
    for(int i=2;i<=n;++i)    scanf("%d",&fa[i]);
    for(int i=2;i<=n;++i)    belong[i]=(i-1)/bs+1,updtop(i);
    while(m--)
    {
        int opt; scanf("%d",&opt);
        if(opt==1)
        {
            int opl,opr,opx;
            scanf("%d %d %d",&opl,&opr,&opx);
            turndown(belong[opl]);
            if(belong[opl]==belong[opr])
            {
                turndown(belong[opl]);
                for(int i=opl;i<=opr;++i)    fa[i]=max(fa[i]-opx,1),updtop(i);
                for(int i=opr+1;i<=gtrg(belong[opl]);++i)    updtop(i);
            }
            else
            {
                turndown(belong[opl]);
                for(int i=opl;i<=gtrg(belong[opl]);++i)    fa[i]=max(fa[i]-opx,1),updtop(i);
                for(int i=gtlf(belong[opl]);i<opl;++i)    updtop(i);
                turndown(belong[opr]);
                for(int i=gtlf(belong[opr]);i<=opr;++i)    fa[i]=max(fa[i]-opx,1),updtop(i);
                for(int i=opr+1;i<=gtrg(belong[opr]);++i)    updtop(i);
                for(int i=belong[opl]+1;i<belong[opr];++i)
                {
                    if(deln[i]>=bs)    tag[i]+=opx;
                    else
                    {
                        ++deln[i];
                        for(int j=gtlf(i);j<=gtrg(i);++j)    fa[j]=max(fa[j]-opx,1),updtop(j);
                    }
                }
            }
        }
        else
        {
            int opx,opy; scanf("%d %d",&opx,&opy);
            while(opx^opy)
            {
                int fopx,fopy;
                if(deln[belong[opx]]>=bs)    turndown(belong[opx]),fopx=fa[opx];
                else    fopx=top[opx];
                if(deln[belong[opy]]>=bs)    turndown(belong[opy]),fopy=fa[opy];
                else    fopy=top[opy];
                if(belong[opx]^belong[opy])
                {
                    if(belong[opx]>belong[opy])    opx=fopx;
                    else    opy=fopy;
                }
                else if(fopx^fopy)    opx=fopx,opy=fopy;
                else
                {
                    if(opx>opy)    turndown(belong[opx]),opx=fa[opx];
                    else    turndown(belong[opy]),opy=fa[opy];
                }
            }
            printf("%d\n",opx);
        }
    }
    return 0;
}

Part. 1 FFT

Part. 1-1 Main

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

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

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

先令 L(x)=∑i=0⌊n2⌋−1a2ix2i,R(x)=∑i=0⌊n2⌋−1a2i+1x2iL(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}。

F(ωnk)=L((ωnk)2)+ωnkR((ωnk)2)=L(ωn2k)+ωnkR(ωn2k)=L(ω⌊n2⌋k)+ωnkR(ω⌊n2⌋2k) \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}

同时：

F(ωnk+⌊n2⌋)=L(ωn2k)+ωnk+⌊n2⌋R(ωn2k)=L(ω⌊n2⌋k)−ωnkR(ω⌊n2⌋k) \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，注意要把多项式长度调整为 22 的幂。

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

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×NN \times N 的矩阵，她希望求出：

  1. 该矩阵的所有子矩阵的 AND\texttt{AND} 值之和（所有子矩阵 AND\texttt{AND} 值相加的结果）。
  2. 该矩阵的所有子矩阵的 OR\texttt{OR} 值之和（所有子矩阵 OR\texttt{OR} 值相加的结果）。

Solution

对于每一个数的每一位，我们单独拉出来构成 log⁡\log 个矩阵。

对于 AND\texttt{AND}，显然只有全为 11 的子矩阵能产生贡献。

对于 OR\texttt{OR}，只有存在 11 的子矩阵才能产生贡献。

那么枚举右下角，单调栈统计。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD=1e9+7;
int n,pre[1010][1010],stk[1010],top,a[1010][1010],b[1010][1010],ans,exans,mx;
void work(int k,int t)
{
    for(int i=1;i<=n;++i)    for(int j=1;j<=n;++j)    b[i][j]=((a[i][j]>>k)&1);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(b[i][j]==t)    pre[i][j]=pre[i-1][j]+1;
            else    pre[i][j]=0;
        }
    }
    int siz=0;
    for(int i=1;i<=n;++i)
    {
        siz=top=0,stk[1]=stk[0]=0;
        for(int j=1;j<=n;++j)
        {
            while(top&&pre[i][stk[top]]>=pre[i][j])    siz=(siz-LL(pre[i][stk[top]])*(stk[top]-stk[top-1])%MOD+MOD)%MOD,--top;
//            siz=(siz+LL(pre[i][j])*(j-stk[top])%MOD)%MOD,stk[++top]=j;
            siz+=LL(pre[i][j])*(j-stk[top]),stk[++top]=j;
            if(t)    ans=(ans+LL(siz)*(1<<k)%MOD)%MOD;
            else    exans=(exans+(LL(i)*j%MOD-LL(siz))*(1<<k)%MOD+MOD)%MOD;
        }
    }
}
inline char fgc()
{
    static char buf[1<<17],*p=buf,*q=buf;
    return p==q&&(q=buf+fread(p=buf,1,1<<17,stdin),p==q)?EOF:*p++;
}
void read(int &hhh)
{
    int x=0;
    char c=fgc();
    while(!isdigit(c))    c=fgc();
    while(isdigit(c))    x=(x<<3)+(x<<1)+(c^'0'),c=fgc();
    hhh=x;
}
void write(int x,char las='\n')
{
    static int stk[100],top=0;
    do stk[++top]=x%10,x/=10; while(x);
    while(top)    putchar(stk[top--]^'0');
    putchar(las);
}
int main()
{
    read(n);
    for(int i=1;i<=n;++i)    for(int j=1;j<=n;++j)    read(a[i][j]),mx=max(mx,a[i][j]);
    for(int k=0;(1ll<<k)<=mx;++k)    work(k,0),work(k,1);
    write(ans,' '),write(exans);
    return 0;
}
  1. 1
  2. ...
  3. 32
  4. 33
  5. 34
  6. 35
  7. 36
  8. 37
  9. 38
  10. ...
  11. 49