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]. （当然记得取模）

代码：

 #include<bits/stdc++.h>

 #define ll long long

 #define pi pair<int,int>

 #define mp(x,y) make_pair(x,y)

 using namespace std;

 const int N=;

 bool vis[N][][][];int t,mod,ml;

 ll n,m,nn,mm,k,kk;pi f[N][][][];

 void add(int &x,int y){

     x+=y;if(x>=mod) x-=mod;

 } pi dp(int len,bool n1,bool m1,bool k1){

     if(len>ml) return mp(,);

     if(vis[len][n1][m1][k1])

     return f[len][n1][m1][k1];

     vis[len][n1][m1][k1]=;

     int np=(n>>ml-len)&,mp=(m>>ml-len)&,

     kp=(k>>ml-len)&;

     for(int i=;i<=(n1?np:);i++)

     for(int j=;j<=(m1?mp:);j++){

         if(k1&&(i^j)<kp) continue;

         pi nw=dp(len+,n1&&(i==np),

         m1&&(j==mp),k1&&((i^j)==kp));

         add(f[len][n1][m1][k1].first,nw.first);

         add(f[len][n1][m1][k1].second,

         ((1ll<<ml-len)*(i^j)%mod*

         nw.first+nw.second)%mod);

     } return f[len][n1][m1][k1];

 } int main(){

     scanf("%d",&t);while(t--){

         memset(vis,,sizeof(vis));

         memset(f,,sizeof(f));

         scanf("%lld%lld%lld%d",&n,&m,&k,&mod);

         n--;m--;int nw=;nn=n,mm=m,kk=k;

         while(nn) nw++,nn/=;

         ml=max(nw,ml);nw=;

         while(mm) nw++,mm/=;

         ml=max(nw,ml);nw=;

         while(kk) nw++,kk/=;

         ml=max(nw,ml);pi ans=dp(,,,);

         printf("%d\n",(1ll*ans.second-1ll*k%mod*

         ans.first%mod+mod)%mod);

     } return ;

 }

数位dp

巴特西

BZOJ4513 SDOI2016 储能表记忆化搜索（动态规划）

题意：

分析：

最新文章

热门文章

巴特西

BZOJ4513 SDOI2016 储能表 记忆化搜索（动态规划）

题意：

分析：

最新文章

热门文章

BZOJ4513 SDOI2016 储能表记忆化搜索（动态规划）