luogu4187 [USACO28JAN]Stamp Painting

luogu4187 [USACO28JAN]Stamp Painting

​​‎

题目描述

Bessie has found herself in possession of an NNN -unit long strip of canvas (1≤N≤1061 \leq N \leq 10^61≤N≤106 ), and she intends to paint it. However, she has been unable to acquire paint brushes. In their place she has MMM rubber stamps of different colors (1≤M≤1061 \leq M \leq 10^61≤M≤106 ), each stamp KKK units wide (1≤K≤1061 \leq K \leq 10^61≤K≤106 ). Astounded by the possibilities that lie before her, she wishes to know exactly how many different paintings she could conceivably create, by stamping her stamps in some order on the canvas.

To use a stamp, it must first be aligned with exactly KKK neighboring units on the canvas. The stamp cannot extend beyond the ends of the canvas, nor can it cover fractions of units. Once placed, the stamp paints the KKK covered units with its color. Any given stamp may be used multiple times, once, or even never at all. But by the time Bessie is finished, every unit of canvas must have been painted at least once.

Help Bessie find the number of different paintings that she could paint, modulo 109+710^9 + 7109+7 . Two paintings that look identical but were painted by different sequences of stamping operations are counted as the same.

For at least 75% of the input cases, N,K≤103N,K \leq 10^3N,K≤103 . 输入输出格式 输入格式：

The first and only line of input has three integers, NNN , MMM , and KKK . It is guaranteed that K≤NK \leq NK≤N . 输出格式：

A single integer: the number of possible paintings, modulo 109+710^9 + 7109+7 . 输入输出样例 输入样例#1： 复制

3 2 2

输出样例#1： 复制

6

说明

If the two stamps have colors A and B, the possible paintings are AAA, AAB, ABB, BAA, BBA, and BBB.

动态规划计数dp 每次可以用长度为k的一块覆盖线段覆盖出来都是相同的颜色现在求 方案数是多少 那么可以感知到我这样做的话最后的序列里一定有一块长度为k的块那么我就这么dp即可 当时想的时候在这里我也和zhx巨佬一样想不动了 后来正解我也想了 很久 正解：既然正着不好考虑就倒着考虑即可 就直接考虑 计算不存在k长度连续区间相同的方案数 那么设dp[i]表示长度为i的这个方案数即可 那么dp[i]=∑k−1j=1(m−1)∗dp[j] ∑ j = 1 k − 1 ( m − 1 ) ∗ d p [ j ]

#include#define ll long long#define mod 1000000007#define N 1100000ll dp[N],sum1,sum;int n,m,k;int main(){// freopen("spainting.in","r",stdin);// freopen("spainting.out","w",stdout); scanf("%d%d%d",&n,&m,&k);sum1=1;dp[0]=1; for (int i=1;i<=n;++i){ sum+=dp[i-1];sum%=mod;sum1*=m;sum1%=mod; if(i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。