【BZOJ-1974】auction代码拍卖会 DP + 排列组合

1974: [Sdoi2010]auction 代码拍卖会

Time Limit: 10 Sec Memory Limit: 64 MB
Submit:
305 Solved: 122
[Submit][Status][Discuss]

Description

随着iPig在P++语言上的造诣日益提升，他形成了自己一套完整的代码库。猪王国想参加POI的童鞋们都争先恐后问iPig索要代码库。iPig不想把代码库给所有想要的小猪，只想给其中的一部分既关系好又肯出钱的小猪，于是他决定举行了一个超大型拍卖会。
在拍卖会上，所有的N头小猪将会按照和iPig的好感度从低到高，从左到右地在iPig面前站成一排。每个小猪身上都有9猪币（与人民币汇率不明），从最左边开始，每个小猪依次举起一块牌子，上面写上想付出的买代码库的猪币数量（1到9之间的一个整数）。大家都知道，如果自己付的钱比左边的猪少，肯定得不到梦寐以求的代码库，因此从第二只起，每只猪出的钱都大于等于左边猪出的价钱。最终出的钱最多的小猪（们）会得到iPig的代码库真传，向着保送PKU（Pig
Kingdom University）的梦想前进。
iPig对自己想到的这个点子感到十分满意，在去现场的路上，iPig就在想象拍卖会上会出现的场景，例如一共会出现多少种出价情况之类的问题，但这些问题都太简单了，iPig早已不敢兴趣了，他想要去研究更加困难的问题。iPig发现如果他从台上往下看，所有小猪举的牌子从左到右将会正好构成一个N位的整数，他现在想要挑战的问题是所有可能构成的整数中能正好被P整除的有多少个。由于答案过大，他只想要知道答案mod999911659就行了。

Input

一行：两个数N（1≤N≤10^18）、P(1≤P≤500)，用一个空格分开。

Output

一行：一个数，表示答案除以999911659的余数。

Sample Input

2 3

Sample Output

15
样例解释
方案可以是：12 15 18 24 27 33
36 39 45 48 57 66 69 78 99，共15种。
数据规模
测试点 N P 测试点 N P
1 ≤1000 ≤500 6
≤10^6 ≤500
2 ≤10^18 5 7 ≤10^18 ≤120
3 ≤10^18 ≤10 8 ≤10^18 ≤500
4 ≤10^18
≤10 9 ≤10^18 ≤500
5 ≤10^18 25 10 ≤10^18 ≤500

HINT

Source

Sdoi2010 Contest2 Day2

Solution

数据范围和题目描述，一开始以为是数位DP，发现其实不是折越

发现从左到右每一位不减，那么有个不错的性质，可以组成的数，拆成${1，11，111，1111....}$中取$<=8$个数组合出来

而这些数%p，最多有p种可能，那么找循环，DP，用组合数计算一下答案即可

那么方程就是$dp[i][j][k]$表示前i种可能选了j个，组合出来的数%p结果为k的方案数

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define mod 999911659

long long n;int p,a,ans;

long long dp[][][],inv[],c[][],data[],cnt[];

long long C(long long x,int y)

{

    if (y>x) return ;

    long long re=;

    for (long long i=x-y+; i<=x; i++)

        (re*=(i%mod))%=mod;

    return re*inv[y]%mod;

}

void GetInv()

{

    inv[]=,inv[]=;

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

        inv[i]=(mod-mod/i)*inv[mod%i]%mod;

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

        inv[i]=inv[i]*inv[i-]%mod;

}

int main()

{

    scanf("%lld%d",&n,&p);

    GetInv();

    int x=%p,sz=;

    while (!cnt[x]) {cnt[x]=++sz; data[sz]=x; if (sz>=n) break; x=(x*+)%p;}

    if (sz!=n)

        {

            long long N=n-cnt[x]+; int SZ=sz-cnt[x]+;

            if (SZ>) a=(p-data[cnt[x]+(N%SZ?N%SZ:SZ)-])%p;

                else a=(p-data[cnt[x]])%p;

            for (int i=,t=cnt[x]; i<p; i++)

                if (cnt[i])

                    if (cnt[i]<t) cnt[i]=;

                        else

                            if (SZ> && (N%SZ)>cnt[i]-t)

                                cnt[i]=N/SZ+; else cnt[i]=N/SZ;

        }

    else

        {

            a=(p-x)%p;

            for (int i=; i<p; i++) if (cnt[i]) cnt[i]=;

        }

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

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

            if (cnt[i]) c[i][j]=C(cnt[i]+j-,j);

    dp[][][]=;

    int now=;

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

        if (cnt[i])

            {

                now^=;

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

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

                        dp[now][j][k]=dp[now^][j][k];

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

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

                        if (dp[now^][j][k])

                            for (int l=; l<-j; l++)

                                (dp[now][j+l][(k+l*i)%p]+=dp[now^][j][k]*c[i][l]%mod)%=mod;

            }

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

        ans=(ans+dp[now][i][a])%mod;

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

    return ;

}

这道题吼啊！

秒客网