BZOJ4513 SDOI2016 储能表 记忆化搜索(动态规划)

题意:

  题面中文,不予翻译:SDOI2016储能表

 

分析:

  据说有大爷用一些奇怪的方法切掉了这道题%%%%%

  这里用的是大众方法——动态规划。

  其实这是一道类似于二进制数位dp的动态规划题,(但是实际上还不是特别典型的数位dp)这里就要我们对问题的深入理解。

  如果我们按照思路进程来发展的话,首先,我们会想到把求和式和k拆开,先求出所有大于k的(i^j)的和,然后减去若干个k。

  我们怎样去数这个数呢?

  逐位分析,用数位dp的手段,要判断i是否卡n的上界,j是否卡m的上界,以及i^j是否卡k这个下界,我们需要统计两个东西。

  1. 合法的,对答案有贡献的方案数

  2. 合法的,对答案有贡献的方案的总贡献。

  所以我们需要dp两个数组,f[len][1/0][1/0][1/0]表示考虑的第len位是否卡n的第len位(上界),是否卡m的第len位(上界),是否卡k的第len位(下界)时的方案数,和g[len][1/0][1/0][1/0]表示的是相应状态的总贡献。

  那么我们按照数位dp的思路去做记忆化搜索,最后的答案就是

  ans = g[1][1][1][1] - k* f[1][1][1][1]. (当然记得取模)

代码:

 

BZOJ4513 SDOI2016 储能表 记忆化搜索(动态规划)
 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define pi pair<int,int>
 4 #define mp(x,y) make_pair(x,y)
 5 using namespace std;
 6 const int N=70;
 7 bool vis[N][2][2][2];int t,mod,ml;
 8 ll n,m,nn,mm,k,kk;pi f[N][2][2][2];
 9 void add(int &x,int y){
10     x+=y;if(x>=mod) x-=mod;
11 } pi dp(int len,bool n1,bool m1,bool k1){
12     if(len>ml) return mp(1,0);
13     if(vis[len][n1][m1][k1])
14     return f[len][n1][m1][k1];
15     vis[len][n1][m1][k1]=1;
16     int np=(n>>ml-len)&1,mp=(m>>ml-len)&1,
17     kp=(k>>ml-len)&1;
18     for(int i=0;i<=(n1?np:1);i++)
19     for(int j=0;j<=(m1?mp:1);j++){
20         if(k1&&(i^j)<kp) continue;
21         pi nw=dp(len+1,n1&&(i==np),
22         m1&&(j==mp),k1&&((i^j)==kp));
23         add(f[len][n1][m1][k1].first,nw.first);
24         add(f[len][n1][m1][k1].second,
25         ((1ll<<ml-len)*(i^j)%mod*
26         nw.first+nw.second)%mod);
27     } return f[len][n1][m1][k1];
28 } int main(){
29     scanf("%d",&t);while(t--){
30         memset(vis,0,sizeof(vis));
31         memset(f,0,sizeof(f));
32         scanf("%lld%lld%lld%d",&n,&m,&k,&mod);
33         n--;m--;int nw=0;nn=n,mm=m,kk=k;
34         while(nn) nw++,nn/=2;
35         ml=max(nw,ml);nw=0;
36         while(mm) nw++,mm/=2;
37         ml=max(nw,ml);nw=0;
38         while(kk) nw++,kk/=2;
39         ml=max(nw,ml);pi ans=dp(1,1,1,1);
40         printf("%d\n",(1ll*ans.second-1ll*k%mod*
41         ans.first%mod+mod)%mod);
42     } return 0;
43 }
数位dp

 

上一篇:洛谷P4069 [SDOI2016]游戏(李超线段树)


下一篇:mysql全局唯一ID生成方案(二)