[USACO18JAN]Stamp Painting

- 日理万妓 2023-10-11 05:13 43阅读 0赞

[题目][Link 1]

考虑正难则反，拿总方案数\\(m^n\\)减掉不合法的方案

由于我们最后一次涂了一段长度为\\(k\\)的连续颜色段，所以合法的方案有一段长度至少为\\(k\\)的颜色相同段

不合法的方案一定没有，于是我们求一下有多个颜色序列没有长度大于等于\\(k\\)的颜色相同段就好了

显然我们强制往后加一段长度小于\\(k\\)的段就行了

于是有\\(f\_i=(m-1)\\sum\_\{j=i-k+1\}^\{i-1\}f\_j\\)，转移的时候维护一下前缀和就可以了

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    const int mod=1e9+7;
    const int maxn=1e6+5;
    int n,m,k,dp[maxn],pre[maxn];
    inline int qm(int x) {return x>=mod?x-mod:x;}
    inline int dqm(int x) {return x<0?x+mod:x;}
    inline int calc(int l,int r) {return dqm(pre[r]-pre[l-1]);}
    int main() {
        scanf("%d%d%d",&n,&m,&k);dp[0]=1;
        for(re int i=1;i<k;i++) dp[i]=1ll*dp[i-1]*m%mod,pre[i]=qm(pre[i-1]+dp[i]);
        for(re int i=k;i<=n;i++)
            dp[i]=1ll*(m-1)*calc(i-k+1,i-1)%mod,pre[i]=qm(pre[i-1]+dp[i]);
        int ans=1;for(re int i=1;i<=n;i++) ans=1ll*ans*m%mod;
        printf("%d\n",dqm(ans-dp[n]));
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11528942.html

[Link 1]: https://www.luogu.org/problem/P4187

发表评论取消回复

表情：

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

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

相关阅读

相关【树形计数DP】P4084 [USACO17DEC]Barn Painting G

[P4084 \[USACO17DEC\]Barn Painting G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P4084 _USACO17DEC

╰+攻爆jí腚メ/ 2024年03月16日 19:25/ 0 赞/ 177 阅读

相关 [USACO18JAN]Stamp Painting

[题目][Link 1] 考虑正难则反，拿总方案数\\(m^n\\)减掉不合法的方案由于我们最后一次涂了一段长度为\\(k\\)的连续颜色段，所以合法的方案有一段长度至少

- 日理万妓/ 2023年10月11日 05:13/ 0 赞/ 44 阅读

相关 USACO[CowCoupons]

[USACO\[CowCoupons\]][USACO_CowCoupons] 这题是个非常棒的贪心题,唯一的缺点是数据太水了,强烈要求加强数据.(当然我知道在这里喊不会有人

喜欢ヅ旅行/ 2023年06月02日 11:57/ 0 赞/ 112 阅读

相关 Paint 详解

尊重原创，[转载请标明出处][Link 1] [http://blog.csdn.net/abcdef314159][Link 1] 自定义控件具有很强的灵活性，可以根

墨蓝/ 2022年06月05日 11:44/ 0 赞/ 356 阅读

相关 USACO翻译：USACO 2013 JAN三题（1）

USACO 2013 JAN 一、题目概览 <table> <tbody> <tr> <td> <p>中文题目名称</p> </td> <td

朴灿烈づ我的快乐病毒、/ 2022年01月10日 04:53/ 0 赞/ 322 阅读

相关 USACO翻译：USACO 2014 DEC Silver三题

USACO 2014 DEC SILVER 一、题目概览 <table> <tbody> <tr> <td> <p>中文题目名称</p> </td>

不念不忘少年蓝@/ 2022年01月10日 03:53/ 0 赞/ 293 阅读

相关 USACO翻译：USACO 2012 JAN三题（2）

USACO 2012 JAN（题目二）一、题目概览 <table> <tbody> <tr> <td> <p>中文题目名称</p> </td>

曾经终败给现在/ 2022年01月10日 03:53/ 0 赞/ 367 阅读

相关 1129. Door Painting

1129. Door Painting Time limit: 0.25 second Memory limit: 64 MB There are many rooms

我不是女神ヾ/ 2022年01月05日 15:29/ 0 赞/ 367 阅读

相关 P4377 [USACO18OPEN]Talent Show

这道题可以作为最优比率背包问题的模板题了。好像属于01分数规划。我们这里用二分答案的方法解决。题目要我们求\\(\\frac\{\\sum\{t\}\}\{\\sum\

àì夳堔傛蜴生んèń/ 2021年12月22日 15:56/ 0 赞/ 260 阅读

相关【luogu4185】 [USACO18JAN]MooTube [并查集]

[P4185 \[USACO18JAN\]MooTube][P4185 _USACO18JAN_MooTube] 并查集好合并不好拆开可以考虑离线先读入从大到小排序再

小鱼儿/ 2021年11月16日 05:44/ 0 赞/ 317 阅读