USACO 2018 January Contest, Gold Problem 3. Stamp Painting
USACO 2018 January Contest, Gold Problem 3. Stamp Painting
2018年1月USACO美国计算机奥赛金级题3
Bessie has found herself in possession of an NN-unit long strip of canvas (1≤N≤1061≤N≤106), and she intends to paint it.
However, she has been unable to acquire paint brushes. In their place she has MM rubber stamps of different colors (1≤M≤1061≤M≤106), each stamp KK units wide (1≤K≤1061≤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 KK 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 KK 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+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≤103.
INPUT FORMAT (file spainting.in):
The first and only line of input has three integers, NN, MM, and KK. It is guaranteed that K≤NK≤N.
OUTPUT FORMAT (file spainting.out):
A single integer: the number of possible paintings, modulo 109+7109+7.
SAMPLE INPUT:
3 2 2
SAMPLE OUTPUT:
6
If the two stamps have colors A and B, the possible paintings are AAA, AAB, ABB, BAA, BBA, and BBB.
以上就是关于【USACO 2018 January Contest, Gold Problem 3. Stamp Painting】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。
往期文章阅读推荐：
5金3银！2026 IOAI国际人工智能奥赛收官！中国队取得历史性突破！
AI奥赛2026国家队名单公布！ 新赛季翰林助力直通IOAI全球总决赛！
翰林AMC8视频课重磅上线！
国际竞赛真题资源免费领取
