注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1974][Sdoi2010]auction 代码拍卖会  

2015-06-14 14:26:46|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1974: [Sdoi2010]auction 代码拍卖会

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 225  Solved: 83
[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整除的有多少个。由于答案过大,他只想要知道答案mod 999911659就行了。

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

Solution

题意:给定N,P,有一个数A是N位数,并且A的每一位不减(如11234)并且不超过9,求能被P整除的数有多少个。
分析:首先我们注意到N非常大,O(N)绝对不能接受,但是P只有500,而且A这个数有非常奇妙的性质:由于A的每一位不减,所以可以将A拆成0,1,11,111,1111,11111……中取九个的和(如11234=11111+111+11+1+0+0+0+0+0),这样一来,由于11…111 mod P会出现循环,就可以将N从复杂度中消去,记Cnt[i]表示0,1,11……中mod P 为i的个数(0 <= I < P),题目就变成了从Cnt[i]中取九个使下标之和被P整除;
于是可以容易的想到动态规划,F[i][j][k]表示做到Cnt[i],当前取了k个,k个的和mod P为j,转移方程就是
F[i + 1][(j + l * i) % P][k + l] = (F[i][j][k] * Calc(l, Cnt[i]) + F[i + 1][(j + l * i) % P][k + l]) % mod;(枚举l)
其中Calc(l, Cnt[i])表示Cnt[i]中无差别的取出l个(可以重复)的方案数,根据排列组合的定理可知Calc(A, B) = C(A+B-1,A) 
复杂度:O(P*P*9*9)
记得最后的数还要加上111...11(n个1).因为在DP的时候这个数是可以有前导0的。

Code

/**************************************************************
    Problem: 1974
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1048 ms
    Memory:876 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define rint register int
typedef long long ll;
#define mod 999911659
int p,f[2][510][10],vis[510],s[510][10],len,x,inv[20],ans,add,now;ll cnt[510],n;
int getC(ll n,rint k){
    rint ans=inv[k];
    for(n%=mod;k--;ans=1LL*ans*n%mod,n--);
    return ans;
}
int main(){
    scanf("%lld%d",&n,&p);rint i,j,k,l;
    if(n<=p){
        for(i=j=1;j<n;j++,i=(i*10+1)%p)cnt[i]++;cnt[add=i]++;
    }else{
        for(vis[i=1%p]=len=1;!vis[i=(i*10+1)%p];vis[i]=++len);
        x=len,len-=vis[i]-1;
        for(i=1%p,j=1;j<=x;j++,i=(i*10+1)%p)cnt[i]=1;
        for(;j<=x+len&&j<=n;j++,i=(i*10+1)%p)cnt[i]+=(n-j+1)/len+((n-j+1)%len!=0),(n-j)%len==0?add=i:1;
    }
    add=(p-add)%p;
    for(inv[0]=inv[1]=1,i=2;i<=15;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
    for(i=2;i<=15;i++)inv[i]=1LL*inv[i]*inv[i-1]%mod;
    for(i=0;i<p;i++)if(cnt[i])
    for(j=0;j<9;j++)s[i][j]=getC(cnt[i]+j-1,j);
    f[0][0][0]=1;
    if(cnt[0])for(j=1;j<9;j++)f[0][0][j]=s[0][j];
    for(i=1;i<p;i++)
    if(cnt[i]){
        now^=1;memset(f[now],0,sizeof(f[now]));
        for(j=0;j<p;j++)
        for(k=0;k<9;k++)
        if(f[now^1][j][k]){
            for(l=0;l+k<9;l++)
            f[now][(j+i*l)%p][k+l]=(f[now][(j+i*l)%p][k+l]+1LL*f[now^1][j][k]*s[i][l])%mod;
        }
    }
    for(i=0;i<9;i++)ans=(ans+f[now][add][i])%mod;
    printf("%d\n",ans);
}
  评论这张
 
阅读(456)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018