Luogu5307 [COCI2019] Mobitel 【数论分块】【递推】

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目分析：

对于向上取整我们总有，$\lceil \frac{\lceil \frac{n}{a} \rceil}{b} \rceil = \lceil \frac{n}{a*b} \rceil$这个不难想到。

然后朴素的dp很容易想到，用上面的式子优化一下就行了。

代码：

 // luogu-judger-enable-o2

 #include<bits/stdc++.h>

 using namespace std;

 const int mod = 1e9+;

 int f[][];

 int a[][];

 int rem[],pep[];

 int n,m,k,num;

 int main(){

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

     for(int i=;i<=n;i++) for(int j=;j<=m;j++) scanf("%d",&a[i][j]);

     int lst = ;

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

     int now = k/i + (k%i != );

     if(now != lst) rem[++num] = i,pep[now] = num;

     lst = now;

     }

     f[][] = ;

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

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

         for(int ku=num;ku>=;ku--){

         if(!f[j][ku] && !f[j-][ku]) continue;

         int dem = f[j][ku];

         f[j][ku] = ;

         int ham = rem[ku];

         if(1ll*ham*a[i][j] >= k) ham = k;

         else ham = a[i][j]*ham;

         ham = pep[k/ham+(k%ham!=)];

         f[j][ham] += dem; if(f[j][ham] >= mod) f[j][ham] -= mod;

         f[j][ham] += f[j-][ku]; if(f[j][ham] >= mod) f[j][ham]-=mod;

         }

     }

     }

     printf("%d\n",f[m][num]);

     return ;

 }