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

电玩女神 2021-11-01 22:50 277阅读 0赞

题目分析：

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

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

代码：

1 // luogu-judger-enable-o2
     2 #include<bits/stdc++.h>
     3 using namespace std;
     4 
     5 const int mod = 1e9+7;
     6 
     7 int f[350][5020];
     8 int a[350][350];
     9 int rem[5020],pep[1020000];
    10 int n,m,k,num;
    11 
    12 int main(){
    13     scanf("%d%d%d",&n,&m,&k);
    14     for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
    15     int lst = 0;
    16     for(int i=1;i<=k;i++){
    17     int now = k/i + (k%i != 0);
    18     if(now != lst) rem[++num] = i,pep[now] = num;
    19     lst = now;
    20     }
    21     f[1][1] = 1;
    22     for(int i=1;i<=n;i++){
    23     for(int j=1;j<=m;j++){
    24         for(int ku=num;ku>=1;ku--){
    25         if(!f[j][ku] && !f[j-1][ku]) continue;
    26         int dem = f[j][ku];
    27         f[j][ku] = 0; 
    28         int ham = rem[ku];
    29         if(1ll*ham*a[i][j] >= k) ham = k;
    30         else ham = a[i][j]*ham;
    31         ham = pep[k/ham+(k%ham!=0)];
    32         f[j][ham] += dem; if(f[j][ham] >= mod) f[j][ham] -= mod;
    33         f[j][ham] += f[j-1][ku]; if(f[j][ham] >= mod) f[j][ham]-=mod;
    34         }
    35     }
    36     }
    37     printf("%d\n",f[m][num]);
    38     return 0;
    39 }

转载于:https://www.cnblogs.com/Menhera/p/10974045.html

发表评论取消回复

表情：

评论列表（有 0 条评论，277人围观）

还没有评论，来说两句吧...

相关阅读

相关【题解】Luogu P2233 [HNOI2002] 公交路线矩乘加速递推

构造矩阵发现只能相邻两个车站转移，所以能够写出下面这个矩阵 $\{\\begin\{bmatrix\} 0&1&0&0&0&0&0&1 \\\\ 1&0&1&0&0&0&

墨蓝/ 2023年08月17日 16:49/ 0 赞/ 82 阅读

相关递推与递归

递推 include <stdio.h> include <stdlib.h> int main(int argc, char argv[])

忘是亡心i/ 2022年12月12日 04:55/ 0 赞/ 172 阅读

相关落谷3773 数论+dp递推

[https://www.luogu.org/problemnew/show/P3773][https_www.luogu.org_problemnew_show_P3773]

布满荆棘的人生/ 2022年05月14日 08:39/ 0 赞/ 94 阅读

相关 [TJOI2019]甲苯先生的字符串——矩阵乘法+递推

题目链接： [\[TJOI2019\]甲苯先生的字符串][TJOI2019] 我们用一个$26\26$的$01$矩阵记录任意两个字符是否能相邻。设$f\[i\

电玩女神/ 2022年01月13日 04:27/ 0 赞/ 203 阅读

相关 [SNOI2019]数论

其实题目并不难。。。入手想法：枚举x，不行枚举a，b考虑贡献，不行（然后就不会了）其实，枚举a，考虑可以贡献的b，，，，对b开桶，枚举a，a

野性酷女/ 2022年01月12日 10:51/ 0 赞/ 169 阅读

相关 LOJ#3093. 「BJOI2019」光线（递推+概率期望）

题面 [传送门][Link 1] 题解把\\(a\_i\\)和\\(b\_i\\)都变成小数的形式，记\\(f\_i\\)表示\\(1\\)单位的光打到第\\(

迈不过友情╰/ 2021年12月23日 05:47/ 0 赞/ 131 阅读

相关递推（二）：递推法的应用

下面通过一些典型实例及其扩展来讨论递推法的应用。【例2】骨牌铺方格在2×n的一个长方形方格中，用一种2×1的骨牌铺满方格。输入n（n<=40），

青旅半醒/ 2021年11月24日 00:22/ 0 赞/ 320 阅读

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

题目分析：对于向上取整我们总有，$\\lceil \\frac\{\\lceil \\frac\{n\}\{a\} \\rceil\}\{b\} \\rceil = \\l

电玩女神/ 2021年11月01日 22:50/ 0 赞/ 278 阅读

相关 [SNOI2019]数论

[题目][Link 1] 考虑对于每一个\\(a\_i\\)计算有多少个\\(0<x\\leq T-1\\)满足\\(x\\equiv a\_i(mod\\ P)\\)且\\

港控/mmm°/ 2021年11月01日 06:00/ 0 赞/ 284 阅读

相关整除分块（数论分块）

转载自[此博客][Link 1] 整除分块：给定n，求（Σd=1n ⌊n /d⌋）%998244353，n<=1e14 直接枚举会爆考虑优化：我们发现

绝地灬酷狼/ 2021年11月01日 03:40/ 0 赞/ 324 阅读