首页 > 其他 > 详细

AT2294 Eternal Average

时间:2019-10-25 00:20:44      阅读:105      评论:0      收藏:0      [点我收藏+]

我们将最后剩下的数写成\(k\)进制数,即\(0.a_1a_2a_3a_4…\)

\(\therefore a_i\)代表最后第\(i\)次合并了\(a_i\)\(k-a_i\)\(0\)所得到的数.

所以我们可以设\(dp[i][j]\)表示当前的数已经有了\(i\)位,\(\sum_{j=1}^{i}a_i=j\)的方案数.

显而易见的,\(dp[i][j]=\sum_{t=\max(1,j-k)}^{j}dp[i-1][t]\).

如果状态合法,即\(j\equiv m(mod\ k)\)并且\(-j\equiv n(mod\ k)\)并且\(i*k-j\leq n\)
\[ \begin{align} ans+=\sum_{t=\max(1,j-k)}^{j-1}dp[i-1][t] \end{align} \]
为什么\(ans\)不需要加上\(dp[i-1][j]\)呢?

因为这个\(k\)进制数的末尾不能是\(0\).

如果先累加前缀和再累假答案,就让末尾为\(0\)的情况变成了合法情况,这是不对的.

最后记得取模.

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define il inline
#define rg register
#define gi read<int>
using namespace std;
const int O = 4e3 + 10, mod = 1e9 + 7;
template<class TT>
il TT read() {
    TT o = 0,fl = 1; char ch = getchar();
    while (!isdigit(ch) && ch != '-') ch = getchar();
    if (ch == '-') fl = -1, ch = getchar();
    while (isdigit(ch)) o = o * 10 + ch - '0', ch = getchar();
    return fl * o;
}
bool now;
int n, m, k, res, ans, dp[2][O];
il void Add(int & x, int y) {x += y; if (x >= mod) x -= mod;}
il void Minus(int & x, int y) {x -= y; if (x < 0) x += mod;}
int main() {
    n = gi() - 1, m = gi(), k = gi() - 1;
    for (int i = 1; i <= n + m; ++i) {
        res = 1;
        for (int j = 1; j <= m; ++j) {
            if (j > k) Minus(res, dp[!now][j - k - 1]);
            if (j % k == m % k && (k * i - j) % k == n % k && k * i - j <= n)
                Add(ans, res);
            Add(res, dp[!now][j]);
            dp[now][j] = res;
            j == k ? --res : 0;
        }
        now ^= 1;
    }
    printf("%d\n", ans);
    return 0;
}

AT2294 Eternal Average

原文:https://www.cnblogs.com/lylyl/p/11735664.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!