数学

· · 个人记录

组合计数类

P8557 炼金术（Alchemy）

题意简述

有 k 个铁炉，每个铁炉会给出若干种金属，求有多少种方案，使得所有铁炉给出的金属合起来共有 n 种。

思路分析

从每块金属的角度出发，对于 k 个炉子，它都有出现或不出现两种选择，所以一共有 2^k 种方案，因为不能不出现，所以是 2^k-1 种，因为有 n 种金属，所以乘起来就是 (2^k-1)^n 种。用快速幂计算即可。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
#define Mod 998244353
using namespace std;
ll n,k;
ll pow(ll a,ll b){
    ll ans=1;
    for(;b;b>>=1){
        if(b&1) ans*=a,ans=ans%Mod;
        a=(a*a)%Mod;
    }
    return ans;
}
int main(){
    scanf("%lld%lld",&n,&k);
    ll num=pow((long long)2,k);
    num-=1;
    cout<<pow(num,n)<<endl;
    return 0;
}

不要老想着从整体出发，抓住特定的角度来计数。

这里就是从金属的角度考虑，比从炉子的角度考虑更优。

P5303 [GXOI/GZOI2019] 逼死强迫症

题意简述

有一个 2*n 的矩形，要用 n 个 1*2 的矩形将它填满，其中有一个矩形的断成了两个 1 *1 的正方形。求将整块矩形铺满有多少种方案。

思路总结

首先考虑不存在 1*1 矩形时的情况，由于题目 2 * n 矩形的特殊性，所以可以从列的角度来考虑，对于每一列，它要么被一个长方形竖着填满，要么由两个横着的长方形填满。因此有 F_i=F_{i-1}+F_{i-2}。发现是斐波那契数列。

再考虑有 1*1 小方块的情况。发现此时两个方块之间能够放置的方案是唯一的。所以对于第 i 列，当不存在小方块时，方案数为 f_{i-1}+f_{i-2}，当存在小方块时，因为有两个方块不能相邻的条件，所以他们组成的矩形最小也是 2*3 的，枚举左侧另一个矩形出现的位置，相加即可。（注意不要枚举右边的，因为之后遍历到右边时统计的状态是一样的，所以统计一个方向的状态就够了。）公式为:

f_i=f_{i-1}+f_{i-2}+2\times\sum_{j=0}^{i-3} F_j

因为中间的矩阵可以上下颠倒，所以有两种方案，有小方块的情况的方案前面的系数要乘个 2。

由于数据范围的原因，所以要用矩阵乘法优化递推式的计算。定义状态为 \begin{bmatrix}f_i&f_{i-1}&F_{i-2} & F_{i-3} & S_{i-3}\end{bmatrix}，递推的下一个式子为 \begin{bmatrix}f_{i+1}&f_i&F_{i-1}&F_{i-2}&S_{i-2} \end{bmatrix} 。

状态转移矩阵为:

\begin{bmatrix}1&1&0&0&0\\1&0&0&0&0\\2&0&1&1&1\\0&0&1&0&0\\2&0&0&0&1\end{bmatrix}

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define ll long long
#define Mod 1000000007
using namespace std;
ll T,n;
ll zt[5][5]=
{
    {1,1,0,0,0},
    {1,0,0,0,0},
    {2,0,1,1,1},
    {0,0,1,0,0},
    {2,0,0,0,1}
};
ll cs[5]={2,0,1,1,1};
ll a[5],b[5][5];
void mul(){
    //a*b
    ll c[5];
    memset(c,0,sizeof(c));
    for(int i=0;i<5;i++){
        for(int k=0;k<5;k++){
            c[i]=(c[i]+a[k]*b[k][i])%Mod;
        }
    }
    memcpy(a,c,sizeof(c));
    return;
}
void selfmul(){
    ll c[5][5];
    memset(c,0,sizeof(c));
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            for(int k=0;k<5;k++){
                c[i][j]=(c[i][j]+b[i][k]*b[k][j])%Mod;
            }
        }
    }
    memcpy(b,c,sizeof(c));
    return;
}
void ksm(ll x){
    for(;x;x>>=1){
        if(x&1) mul();
        selfmul();
    }
}
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        if(n<3) cout<<"0"<<endl;
        else{
            memcpy(a,cs,sizeof(cs));
            memcpy(b,zt,sizeof(zt));
            ksm(n-3);
            cout<<a[0]<<endl;
        }
    }   
    return 0;
}

P7738 [NOI2021] 量子通信

从 k \le 15 入手，想到将 256 位二进制数转化为 16 位 65536 进制数，因为这样子一来，如果一个单词没被改，那么它至少有 1 位是与词典中的单词的 1 位是相同的。

所以我们可以把词典中的单词都处理为 16 位的，并将每一位数对应到其单词。这样在处理询问的单词时，只需要比较有相同位数的单词是否满足条件即可。

统计 k 的个数我们可以利用改变的是二进制状态下的单词这一性质，采取异或运算，将不同的留下来，然后预处理出 1 \sim 65536 二进制数下 1 的个数，即可 O(1) 的进行计算。

最后拿了 76 分，卡不过去了。

#include <bits/stdc++.h>
using namespace std;

#define gc getchar()
#define mem(x,v) memset(x,v,sizeof(x))

typedef unsigned long long ull;
typedef unsigned short us;

namespace IO{
    char buf[1<<23],*p1=buf,*p2=buf;
    #ifdef __WIN32
        #define gc getchar()
    #else
        #define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
    #endif
    inline int read(){
        int x=0;char s=gc;
        while(!isdigit(s))s=gc;
        while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=gc;
        return x;
    }
} using namespace IO;

const int N=400000+5;
const int W=65536;
bool s[N][256],q[256];

ull myRand(ull &k1,ull &k2){
    ull k3=k1,k4=k2;
    k1=k4,k3^=(k3<<23),k2=k3^k4^(k3>>17)^(k4>>26);
    return k2+k4;
}
void gen(int n,ull a1,ull a2){
    for(int i=0;i<n;i++)
        for(int j=0;j<256;j++)
            s[i][j]=(myRand(a1,a2)&(1ull<<32))?1:0;
}

struct EDGE{
    int cnt,hd[W],nxt[N],to[N];
    void add(int x,int y){nxt[++cnt]=hd[x],hd[x]=cnt,to[cnt]=y;}
}buc[16];

ull n,m,a1,a2;
us val[N][16],mp[W],qq[16];
int main(){
    cin>>n>>m>>a1>>a2,gen(n,a1,a2);
    for(int i=0;i<n;i++)
        for(int j=0;j<16;j++){
            //j 表示一个单词的第几位 
            //将 256 位二进制数 16 位 16 位的划分；
            //因为每 16 位二进制转化为 10 进制表示后为一位 65536 进制下的数  
            for(int k=0;k<16;k++)
                val[i][j]+=s[i][j*16+k]<<k;
            //k 表示将这 16 位二进制数转化为 10 进制数 
            buc[j].add(val[i][j],i);
            //用 链式向前星 将每一位数与其单词建立联系，方便之后查找 
        }
    for(int i=1;i<W;i++)mp[i]=mp[i>>1]+(i&1);
    //处理从 1 ~ 65536 每一个数的二进制表示下有几个 1 
    for(int i=0,las=0,k;i<m;i++,mem(qq,0)){
        for(int j=0,vv=0;j<64;j++,vv=0){
            char s=gc;
            if(isdigit(s))vv=s-'0';
            else if(s>='A'&&s<='F')vv=10+s-'A';
            else {j--; continue;}
            for(int l=0;l<4;l++)q[j*4+l]=(vv>>3-l)&1;
            //从高位到低位拆解二进制数 
            //- 号的优先级在 >> 前面 
        }
        bool ok=0; k=read();
        for(int j=0;j<16;j++)
            for(int l=0;l<16;l++)
                qq[j]+=(q[j*16+l]^las)<<l;
        //将新输入的数转成 65536 进制的数并将它异或上上一个答案使得得到正确输入 
        for(int j=0;j<16;j++){
            for(int p=buc[j].hd[qq[j]];p;p=buc[j].nxt[p]){
                int it=buc[j].to[p],cnt=0;
                us *pval=val[it],*pq=qq;
                //找包含这个数位的所有数，与 y 计算，验证是否小于等于 k 
                for(int l=0;l<16;l++,pval++,pq++){
                    cnt+=mp[(*pval)^(*pq)];
                    if(cnt>k)break;
                } if(cnt<=k){ok=1; break;}
            } if(ok)break;
        } cout<<(las=ok)<<'\n';
    }
    return 0;
}

P2822 [NOIP2016 提高组] 组合数问题

这道题主要利用了组合数的这个性质造出了一个递推式：

C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}

可以运用选物品的思想来理解这个例子，对于第 n 个物品，它可以选，就从 C_{n-1}^{m-1} 转移过来，也可以不选，它就从 C_{n-1}^m 转移过来。两个相加就是 C_n^m。

因为 C_0^0=C_1^0=C_1^1=1，所以反映到数组上，这个规律其实是杨辉三角。

之后再利用二维前缀和统计是 k 的倍数的数的个数即可 O(1) 回答询问。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,k,t;
int sum[2005][2005],ans[2005][2005];
int main(){
    scanf("%d%d",&t,&k);
    sum[0][0]=sum[1][0]=sum[1][1]=1;
    for(int i=2;i<=2000;i++){
        sum[i][0]=1;
        for(int j=1;j<=i;j++){
            sum[i][j]=(sum[i-1][j-1]+sum[i-1][j])%k;
        }
    }
    for(int i=1;i<=2000;i++){
        for(int j=1;j<=2000;j++){
            if(j>i) ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
            else ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+(sum[i][j]==0?1:0);
        }
    }
    while(t--){
        scanf("%d%d",&n,&m);
        cout<<ans[n][m]<<endl;
    }
    return 0;
}

和这一题一样的，需要注意的一点是由于前缀和运算中有减的操作，所以要 + k 再取 mod，否则会由于有负数的存在导致模运算错误。

P8576 「DTOI-2」星之界

关于数学公式推导

\prod\limits_{i=1}^{n}C_{\sum\limits_{j=1}^{i}a_j}^{a_i}=\dfrac{sum_1!\times sum_2! \times sum_3!\times ...\times sum_n!}{a_1! \times a_2! \times a_3! \times... \times a_n! \times sum_0! \times sum1! \times sum_2! \times ... \times sum_{n-1}!}= \dfrac{(\sum_{i=1}^na_i)!}{\prod_{i=1}^n (a_i!)}

关于阶乘和逆元的处理

对于 (\sum\limits_{i=1}^n a_i)! 因为题目保证和最大不超过 10^7，所以把 10^7 以内的数的阶乘都预处理出来，之后直接用即可。

对于 \dfrac{1}{\prod\limits_{i=1}^n (a_i!)} 因为我们已经算出了 10^7 以内的阶乘，求得是倒数，所以我们算出最大的数的逆元，往回推，就能得到所有数的阶乘的逆元。

这里是把逆元当成分数的形式来看，已知 \dfrac{1}{a_{i+1}!} 求 \dfrac{1}{a_i!}，显然是将 \dfrac{1}{a_{i+1!}} \times (i+1) 得到答案。 于是就可以线性求逆元。

之后整块答案更新的维护也是运用这个原理，这里就不赘述了。

通过并查集来维护块内相同的数

因为我们通过分块将序列分成了若干个长度相同的块状，对于同一块内整体修改同一元素的操作，可以用并查集优化修改操作来维护。

将块中第一个出现的元素当做父亲，其它元素指向它，每次更改的时候，如果是更改整块的元素，就将 x 对应的值改为 y 即可，如果不是，就重构整个块，暴力更新。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define Mod 998244353
#define ll long long
using namespace std;
int n,q,B=317;
int a[100005];
int inv[100005],fac[10000005],powinv[100005][320],powfac[100005][320];
int pos[100005],bl[320],br[320];
struct node{
    int head,num;
}e[320][100005];
int fa[100005],v[100005];
int sum[320],mul[320];
int ksm(int x,int y){
    ll ans=1;
    for(;y;y>>=1){
        if(y&1) ans=(ll)(ans)*x%Mod;
        x=(ll)x*x%Mod;
    }
    return ans;
}
int find(int x){
    if(fa[x]==x) return fa[x];
    return  fa[x]=find(fa[x]);
}
void init(int x){
    for(int i=bl[x];i<=br[x];i++){
        if(!e[x][a[i]].head){
            e[x][a[i]].head=i;
            e[x][a[i]].num=1;
            fa[i]=i;
            v[i]=a[i];
        }
        else{
            fa[i]=e[x][a[i]].head;
            e[x][a[i]].num++;
        }
    }
    sum[x]=0,mul[x]=1;
    for(int i=bl[x];i<=br[x];i++){
        sum[x]+=a[i];
        mul[x]=(ll)mul[x]*inv[a[i]]%Mod;
    }
    return;
}
void clac1(int now,int l,int r,int x,int y){
    for(int i=bl[now];i<=br[now];i++){
        a[i]=v[find(i)];
        e[now][a[i]].head=e[now][a[i]].num=0;
        //不要直接memset会超时 
    }
    for(int i=bl[now];i<=br[now];i++) fa[i]=i;
    //父节点要单独更新，因为并查集还在查找相同的数 
    for(int i=l;i<=r;i++) if(a[i]==x) a[i]=y;
    init(now);
}
void clac2(int now,int x,int y){
    sum[now]+=(y-x)*e[now][x].num;
    mul[now]=(ll)mul[now]*(ll)powfac[x][e[now][x].num]%Mod*(ll)powinv[y][e[now][x].num]%Mod;
    e[now][y].num+=e[now][x].num;
    if(!e[now][y].head){
        e[now][y].head=e[now][x].head;
        v[e[now][y].head]=y;
    }
    else fa[e[now][x].head]=e[now][y].head;
    e[now][x].head=e[now][x].num=0;
    return;
}
void change(int l,int r,int x,int y){
    if(pos[l]==pos[r]){
        clac1(pos[l],l,r,x,y);
    }
    else{
        int L,R;
        if(l!=bl[pos[l]]){
            clac1(pos[l],l,br[pos[l]],x,y);
            L=pos[l]+1;
        }
        else L=pos[l];
        if(r!=br[pos[r]]){
            clac1(pos[r],bl[pos[r]],r,x,y);
            R=pos[r]-1;
        }
        else R=pos[r];
        for(int i=L;i<=R;i++){
            clac2(i,x,y);
        }
    }
    return;
}
int ask(int l,int r){
    ll y=1,sum_ans=0;
    if(pos[l]==pos[r]){
        for(int i=l;i<=r;i++){
            int z=v[find(i)];
            //暴力枚举的要用最新的数 
            sum_ans+=z;
            y=(ll)y*inv[z]%Mod;
        }
    }
    else{
        int L,R;
        if(bl[pos[l]]!=l){
            for(int i=l;i<=br[pos[l]];i++){
                int z=v[find(i)];
                sum_ans+=z;
                y=(ll)y*inv[z]%Mod;
            }
            L=pos[l]+1;
        }
        else L=pos[l];
        if(br[pos[r]]!=r){
            for(int i=bl[pos[r]];i<=r;i++){
                int z=v[find(i)];
                sum_ans+=z;
                y=(ll)y*inv[z]%Mod;
            }
            R=pos[r]-1;
        }
        else R=pos[r];
        for(int i=L;i<=R;i++){
            sum_ans+=sum[i];
            y=(ll)y*mul[i]%Mod;
        }
    }
    return (ll)fac[sum_ans]*y%Mod;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),fa[i]=i;
    fac[0]=inv[0]=1;
    for(int i=1;i<=10000001;i++) fac[i]=(ll)fac[i-1]*i%Mod;
    inv[100000]=ksm(fac[100000],Mod-2);
    for(int i=100000-1;i>=1;i--) inv[i]=(ll)inv[i+1]*(i+1)%Mod;
    for(int i=1;i<=100000;i++){
        powfac[i][0]=powinv[i][0]=1;
        for(int j=1;j<=B;j++){
            powfac[i][j]=(ll)powfac[i][j-1]*fac[i]%Mod;
            powinv[i][j]=(ll)powinv[i][j-1]*inv[i]%Mod;
        }
    }
    for(int i=1;i<=n;i++){
        pos[i]=(i/B)+1;
        if(pos[i]!=pos[i-1]){
            bl[pos[i]]=i,br[pos[i-1]]=i-1;
        }
    }
    br[pos[n]]=n;
    for(int i=1;i<=(n/B)+1;i++){
        init(i);
    }
    while(q--){
        int type,l,r,x,y;
        scanf("%d",&type);
        if(type==1){
            scanf("%d%d%d%d",&l,&r,&x,&y);
            if(x==y) continue;
            change(l,r,x,y);
        }
        else {
            scanf("%d%d",&l,&r);
            printf("%d\n",ask(l,r));
        }
    }
    return 0;
}

遇到的几个坑点