[规律]JZOJ 4222 恐怖的奴隶主

Description

在《炉石传说》这款游戏中，有一张随从卡牌叫做“恐怖的奴隶主”。这张卡牌的描述是这样的：每当该随从受到伤害且没有死亡，召唤另一个恐怖的奴隶主。还有一张卡牌叫做“旋风斩”，描述是“对所有随从造成1点伤害”。使用“旋风斩”后，生命值变为0的“恐怖的奴隶主”并不会立即死亡，而会先结算召唤新的“恐怖的奴隶主”再结算生命值为0的“恐怖的奴隶主”的死亡。当然，使用旋风斩后，生命值变为0的“恐怖的奴隶主”不会召唤新的“恐怖的奴隶主”。随从的数量是有上限的，在召唤一个随从前如果随从数量已经达到上限则不会召唤。现在，如果随从数量上限为k，最开始只有一个生命值为m的“恐怖的奴隶主”，而且新召唤出来的“恐怖的奴隶主”的生命值也是m，那么使用了n张“旋风斩”后还有多少个“恐怖的奴隶主”呢？

 

Input

输入共一行包含3个正整数n, m, k。

Output

输出共一行包含1个整数，表示使用n张旋风斩后“恐怖的奴隶主”的数量。

 

Sample Input

4 3 7

Sample Output

6
【样例说明】
初始有1个生命值为3的“恐怖的奴隶主”。
第1次旋风斩后，召唤了1个“恐怖的奴隶主”，剩余1个生命值为2的和1个生命值为3的。
第2次旋风斩后，召唤了2个“恐怖的奴隶主”，剩余1个生命值为1的、1个生命值为2的和2个生命值为3的。
第3次旋风斩后，召唤了3个“恐怖的奴隶主”，然后1个生命值为0的死亡，剩余1个生命值为1的、2个生命值为2的和3个生命值为3的。
第4次旋风斩后，试图召唤5个“恐怖的奴隶主”，但随从数量达到上限7，所以只召唤了1个，然后其中1个生命值为0的死亡，最后剩余2个生命值为1的、3个生命值为2的和1个生命值为3的，共6个。

 

Data Constraint

对于10%的数据，n,k<=10^3；
另有15%的数据，n,m<=10^5；
另有25%的数据，m<=10^5；
另有20%的数据，10^8<=n,m,k<=10^9；
对于全部数据，n,m,k<=10^15。

分析

看到题目就想到：所有人，都过来*n

然后比赛最后开暴力打表，发现了神奇的循环节，但是并没有发现规律

首先我们需要知道循环节是从什么时候开始：当某一时刻奴隶主（包括将死的）爆满时，下一时刻循环节开始

然后%%%WHH大爷发现了循环节神奇的规律：

当j=i%m+1（如果小于循环节开始位置就再加m+1）大于m s[i]=k-s[j-m]

否则直接为k

鬼知道为什么，但是知道循环节开始位置如果小于等于m=1的话就全部补0，那也就是k了，这样减少时空复杂度

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1e4+10;
ll n,m,k,q[N],s[N],cycle;

int main() {
    scanf("%lld%lld%lld",&n,&m,&k);
    if (n==0) {
        printf("1
");
        return 0;
    }
    if (m==1) {
        printf("0
");
        return 0;
    }
    q[0]=s[0]=1;
    for (int i=1;i<=n;i++) {
        q[i]=min(k-s[i-1],s[i-1]-(i>=m?q[i-m]:0));
        s[i]=s[i-1]+q[i]-(i>=m?q[i-m]:0);
        if (q[i]+s[i-1]==k) {
            cycle=i;break;
        }
    }
    if (cycle==n||!cycle) {
        printf("%lld
",s[n]);
        return 0;
    }
    n=n%(m+1);if (n<=cycle) n+=m+1;
    printf("%lld
",k-(n>=m?q[n-m]:0));
}