夏令营501-511NOIP训练18—

传送门：QAQQAQ

题意：给你一个数$n$，把它拆分成至多$k$个正整数，使得这些数的和等于$n$且每一个正整数的个数不能超过$4$

拆分的顺序是无序的，但取出每一个数方案是不同的（例如我要拆$1$，就有$4$种方案，因为$4$个“1”是不同的）

思路：依旧神仙题。。满分好像是什么BM算法，但这道题可以用矩阵快速幂卡过去

40分：暴力，我们把$n$种数拆分成$4*n$个数，然后跑01背包就可以了，防止MLE，可以开滚动，但注意转移时要反着来

#include<bits/stdc++.h>

using namespace std;

const int MOD=;

int dp[][],n,k,a[];

int main()

{

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        if(k>n) k=n;

        if(n==) break;

        memset(dp,,sizeof(dp));

        dp[][]=;

        for(int i=;i<=*n;i++) a[i]=(i+)/;

        for(int i=;i<=*n;i++)

        {

            for(int j=min(i,k);j>=;j--)

            {

                for(int t=n;t>=a[i];t--)

                {

                    dp[t][j]=(dp[t][j]+dp[t-a[i]][j-])%MOD;

                }

            }

        }

        int ans=;

        for(int i=;i<=k;i++) ans=(ans+dp[n][i])%MOD;

        printf("%d\n",ans);

    }

    return ;

}

60分：我们考虑转移时优化一维——即把枚举数的ID这一维优化掉

我们对于转移进行分类讨论：

1.若转移前数列中没有1，那么我们就可以一次性往现数列中加1，并对新加上的1进行“不同化”——即对加进的t个1乘上C(4,t)（这样可以保证2,3,4……都已进行“不同化”）

2.若转移中有1，那么我们就把数列中所有数都加一，使其没有1

我们可以设$dp[i][j][bl]$为和为$i$，取了$j$个数，数列中是否含有1（这种设状态较好理解）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD=;

ll dp[][][],n,k;

void add(ll &x,ll y)

{

    x+=y;

    if(x>=MOD) x-=MOD;

}

ll c4[]={,,,,};

int main()

{

    while(scanf("%lld%lld",&n,&k)!=EOF)

    {

        if(k>n) k=n;

        if(n==&&k==) break;

        memset(dp,,sizeof(dp));

        dp[][][]=;

        for(ll i=;i<=n;i++)

        {

            for(ll j=;j<=min(i,k);j++)

            {

                if(i>j)

                {

                    add(dp[i][j][],dp[i-j][j][]);

                    add(dp[i][j][],dp[i-j][j][]);

                }

                for(ll t=;t<=min(j,4LL);t++)

                    add(dp[i][j][],dp[i-t][j-t][]*c4[t]%MOD);

            }

        }

        ll ans=;

        for(ll i=;i<=k;i++)

        {

            add(ans,dp[n][i][]);

            add(ans,dp[n][i][]);

        }

        printf("%lld\n",ans);

    }

    return ;

}

当然，为了后面的满分代码更方便，我们考虑对状态进行降维，我们把最后bl去掉，把“所有数加1”和“往数组里加1”两个操作一起进行

考虑到满分是矩阵快速幂，我们把剩下的两位压进一维（k比较小，所以可以压）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD=;

ll dp[],n,k;

void add(ll &x,ll y)

{

    x+=y;

    if(x>=MOD) x-=MOD;

}

ll c4[]={,,,,};

ll id(ll x,ll y)

{

    return x*+y;

}

int main()

{

    while(scanf("%lld%lld",&n,&k)!=EOF)

    {

        if(k>n) k=n;

        if(n==&&k==) break;

        memset(dp,,sizeof(dp));

        dp[]=;

        for(ll i=;i<=n;i++)

        {

            for(ll j=;j<=min(i,k);j++)

            {

                for(ll t=;t<=min(j,4LL);t++)

                    add(dp[id(i,j)],dp[id(i-j,j-t)]*c4[t]%MOD);

                    //先让原数组j-t个数都加1，再加入t个1

            }

        }

        ll ans=;

        for(ll i=;i<=k;i++)

        {

            add(ans,dp[id(n,i)]);

        }

        printf("%lld\n",ans);

    }

    return ;

}

100分：第二天补的。。。其实dp并不需要压入一维，而且dp压维因为转移的时候会涉及到dp[0][0]，所以dp压维有点不方便，我们只需要在把dp数组弄进矩阵的时候压一压就可以了

我们考虑转移需要的最早的dp和转移的周期，本来想一个一个递推的，但这种要分类j是否大于4，所以每次矩阵都会改变，无法使用矩阵快速幂。

所以我们加大周期：每十个一次转移，$dp[i][j]$由$dp[i-j][j-t]$转移而来，所以我们对于要更新出的dp[m+1][j]，枚举所有合法的t（此时t=j不合法，我们已经枚举了$dp[k][k]$前的所有状态，所以转移前状态$i$一定都大于0，所以此时$j=0$不合法）

所以总结一下，矩阵快速幂由这些要点：转移需要的最早的值，转移周期，和初始矩阵边界条件

我们把前$k*(k-1)$列都设为把ANS矩阵往前推10位，后k列根据$dp[m+1][j]$的转移前缀和系数在适当的位置填上$C(4,t)$，为了方便理解，下面打印一个k=5时的初始转移矩阵

（ANS矩阵时横着的，转移时ANS=ANS*B）

$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 $
$1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 $
$0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 $
$0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 $
$0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 $
$0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 $
$0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 $
$0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 $
$0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 $
$0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 $
$0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 $
$0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 4 0 0 0 $
$0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 $
$0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 $
$0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 $

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD=;

ll dp[][];

int n,k;

void add(ll &x,ll y)

{

    x+=y;

    if(x>=MOD) x-=MOD;

}

ll c4[]={,,,,};

int id(int x,int y)

{

    return (x-)*k+y;

}

struct matrix{

    ll a[][];

    int n,m;

    matrix(){}

    matrix(int n,int m):n(n),m(m)

    {

        memset(a,,sizeof(a));

    }

    void print()

    {

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=m;j++) printf("%lld ",a[i][j]);

            puts("");

        }

    }

};

matrix operator * (matrix A,matrix B)

{

    matrix C(A.n,B.m);

    int t=min(A.m,B.n);

    for(int i=;i<=C.n;i++)

    {

        for(int j=;j<=C.m;j++)

        {

            for(int p=;p<=t;p++)

                add(C.a[i][j],A.a[i][p]*B.a[p][j]%MOD);

        }

    }

    return C;

}

matrix qpow(matrix B,matrix A,int y)

{

    matrix Z=A;

    while(y)

    {

        if(y&) Z=Z*B;

        B=B*B;

        y>>=;

    }

    return Z;

}

void ready()

{

    memset(dp,,sizeof(dp));

    dp[][]=;

    for(int i=;i<=;i++)

    {

        for(int j=;j<=min(k,i);j++)

        {

            for(int t=;t<=min(j,);t++)

                add(dp[i][j],dp[i-j][j-t]*c4[t]%MOD);

                //先让原数组j-t个数都加1，再加入t个1

        }

    }

}

void make_matrix()

{

    matrix A(k*k,k*k);

    matrix B(k*k,k*k);

    for(int i=;i<=A.m;i++) A.a[i][i]=;

    for(int i=;i<=k*k-k;i++) B.a[i+k][i]=;

    for(int j=;j<=k;j++)

    {

        for(int t=;t<=min(,j-);t++) //和已经大于k，不可能再从取数为0的情况下一次转移而来

        //dp[2][1]就从dp[1][1]转移而来

        {

            B.a[id(k+-j,j-t)][k*k-k+j]=c4[t];

        }

    }

    matrix C(,k*k);

    for(int i=;i<=k;i++)

    {

        for(int j=;j<=k;j++)

        {

            C.a[][id(i,j)]=dp[i][j];

        }

    }

    B=qpow(B,A,n-k);

    C=C*B;

    ll ans=;

    for(int i=;i<=k;i++)

    {

        add(ans,C.a[][id(k,i)]);

    }

    printf("%lld\n",ans%MOD);

}

int main()

{

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        if(k>n) k=n;

        if(n==&&k==) break;

        ready();

        if(n<=k)

        {

            ll ans=;

            for(int i=;i<=k;i++) add(ans,dp[n][i]);

            printf("%lld\n",ans);

        }

        else make_matrix();

    }

    return ;

}

巴特西

夏令营501-511NOIP训练18——高二学堂

最新文章

热门文章