AT2294 Eternal Average

1787 단어
마지막 남은 수를\(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\)\(dpi-1][j]\\\)를 추가할 필요가 없는 이유는 무엇입니까?
이\(k\)진수의 끝은\(0\)일 수 없기 때문입니다.
만약 먼저 접두사와 가짜 답안을 누적한 다음에 끝이\(0\)인 상황을 합법적인 상황으로 바꾸는 것은 옳지 않다.
마지막으로 모범을 취하는 것을 기억해라.
#pragma GCC optimize(3)
#include
#define il inline
#define rg register
#define gi read
using namespace std;
const int O = 4e3 + 10, mod = 1e9 + 7;
template
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
", ans);
    return 0;
}
너의 방법을 잠가라🔗🔗🔗
LeetCode Range Sum Query - Immutable

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage