洛谷 P2481 [SDOI2010]代码拍卖会

洛谷

这大概是我真正意义上的第一道黑题吧！

自己想出了一个大概，状态转移方程打错了一点点，最后还是得看题解。

一句话题意：求出有多少个\(n\)位的数，满足各个位置上的数字从左到右不下降，且被\(p\)整除。

刚开始没有看到数位不下降这个条件，于是自信满满的喊了一句：“这是假黑题吧！”

后来发现了，想了好久好久才找到一条规律。。。

对于任意一个\(n\)位的数，因为要求满足数位不下降，所以一定可以拆分成\(0,1,11,111,1111,11111……\)的和。

又因为数字最大是\(9\)，所以就是从上述数字中任选\(9\)个的和。

于是，我敏锐的觉察到，这是一个dp题，嘿嘿～

分析了一下，由于\(n\)实在太大\((n\leq10^{18})\)所以时间复杂度肯定要去掉这个\(n\)。

然后，我们又会发现\(p\)的范围很小很小，只有\(500\)，于是我们很快想到模数的循环之类的。

因为这里的所有数都是由\(0,1,11,111,1111,11111……\)组成的，又因为这些\(1\)们模上\(p\)会出现循环。

所以我们记\(cnt[i]\)，表示模\(p\)为\(i\)的这些11111……

显然我们需要预处理一波\(cnt[]\)数组，直接从\(1\)枚举到\(p\)即可。

有了上面这些性质，就很好能想出如何定义状态了。

设\(f[i][j][k]\)，表示枚举到了\(cnt[i]\)，模\(p\)为\(j\)，选了\(k\)个形如1111……的数。

那么状态转移方程就很好出来了：

\[f[i+1][(j+l*i)~\texttt{mod}~p][k+l]=(f[i][j][k]*T(l,cnt[i])+f[i+1][(j+l*i)~\texttt{mod}~p][k+l])
\]

这里的\(T(A,B)=C_{A+B-1}^{A}\)根据组合知识很容易求出。

那么差不多这题也完结了。

我本来以为会爆空间的，毕竟\(f[501][501][11]\)我开的是\(\texttt{long~long}\)。结果洛谷只有\(21\texttt{M}\)多一点点。

要注意三个问题：

开长整型\(\texttt{long long}\)。
为了防止前导\(0\)问题，刚开始要填满111111……
最好弄个滚动数组，滚掉第一维。

代码有点丑：

#include <bits/stdc++.h>

using namespace std;

typedef int _int;

#define int long long

const int mo=999911659;

int ans;

int n,p,cnt[501],beg,len,pos[501];

int A[10],c[501][11];

int f[501][501][11],a,sum;

_int main()

{

    cin>>n>>p;

    if (n<=p) {

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

            sum=sum*10+1;

            sum%=p;

            ++cnt[sum];

        }

        a=sum;

    }

    else {

        for (int i=1;i<=p+1;++i) {

            sum=sum*10+1;

            sum%=p;

            if (cnt[sum]) {

                beg=pos[sum];

                len=i-pos[sum];

                break;

            }

            ++cnt[sum];

            pos[sum]=i;

        }

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

            if (cnt[i]&&pos[i]>=beg) {

                cnt[i]=(n-beg+1)/len;

                if (pos[i]-beg+1<=(n-beg+1)%len)

                    ++cnt[i];

                if ((pos[i]-beg+1)%len==(n-beg+1)%len)

                    a=i;

            }

    }

    A[1]=1;

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

        A[i]=(mo-mo/i)*A[mo%i]%mo;

    for (int i=0;i<p;++i) {

        c[i][0]=1;

        if (cnt[i])

            for (int j=1;j<=8;++j) {

                c[i][j]=(cnt[i]*c[i][j-1]%mo)*A[j]%mo;

                ++cnt[i];

                cnt[i]%=mo;

            }

    }

    f[0][a][0]=1;

    for (int i=0;i<p;++i) {

        for (int j=0;j<p;++j) {

            for (int k=0;k<9;++k) {

                for (int l=0;l<=k;++l) {

                    f[i+1][j][k]+=f[i][(j-(l*i%p)+p)%p][k-l]*c[i][l]%mo;

                    f[i+1][j][k]%=mo;

                }

            }

        }

    }

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

        ans+=f[p][0][i],ans%=mo;

    cout<<ans;

    return 0;

}

巴特西

洛谷 P2481 [SDOI2010]代码拍卖会

最新文章

热门文章