[CF118D]Caesar's Legions 题解

题意简述

一个01序列由\(n_1\)个0和\(n_2\)个1组成，求最长连续0串长度不超过\(k_1\)，最长连续1串长度不超过\(k_2\)的序列的方案总数

题解

状态

方案总数

变量

已经取了i个0，j个1，当前末尾连续串长度为k，末尾为l。

转移

\[f[i][j][k][l] =
\left\{
\begin{matrix}
\sum_{x=1}^{min(j,k_2)} f[i-[l=0]][j-[l=1]][x][l\ xor\ 1] && k = 1\\
f[i-[l=0]][j-[l=1]][k-1][l] && k > 1\\
\end{matrix}
\right.
\]

注:\([i=1]\)意为在\(i=1\)时值为\(1\)，否则值为\(0\)。

代码

#include <cstdio>

#include <algorithm>

using namespace std;

const long long MOD = 100000000;

namespace fast_IO{

    const int IN_LEN = 10000000, OUT_LEN = 10000000;

    char ibuf[IN_LEN], obuf[OUT_LEN], *ih = ibuf + IN_LEN, *oh = obuf, *lastin = ibuf + IN_LEN, *lastout = obuf + OUT_LEN - 1;

    inline char getchar_(){return (ih == lastin) && (lastin = (ih = ibuf) + fread(ibuf, 1, IN_LEN, stdin), ih == lastin) ? EOF : *ih++;}

    inline void putchar_(const char x){if(oh == lastout) fwrite(obuf, 1, oh - obuf, stdout), oh = obuf; *oh ++= x;}

    inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);}

    int read(){

        int x = 0; int zf = 1; char ch = ' ';

        while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar_();

        if (ch == '-') zf = -1, ch = getchar_();

        while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar_(); return x * zf;

    }

    void write(int x){

        if (x < 0) putchar_('-'), x = -x;

        if (x > 9) write(x / 10);

        putchar_(x % 10 + '0');

    }

}

using namespace fast_IO;

long long f[105][105][11][2];

int main(){

	int n1 = read(), n2 = read(), k1 = read(), k2 = read();

	for (int i = 1; i <= k1; ++i) f[i][0][i][0] = 1;

	for (int i = 1; i <= k2; ++i) f[0][i][i][1] = 1;

	for (int i = 1; i <= n1; ++i)

		for (int j = 1; j <= n2; ++j){

			for (int k = 1; k <= min(j, k2); ++k)

				(f[i][j][1][0] += f[i - 1][j][k][1]) %= MOD;

			for (int k = 1; k <= min(i, k1); ++k)

				(f[i][j][1][1] += f[i][j - 1][k][0]) %= MOD;

			for (int k = 2; k <= min(i, k1); ++k)

				(f[i][j][k][0] += f[i - 1][j][k - 1][0]) %= MOD;

			for (int k = 2; k <= min(j, k2); ++k)

				(f[i][j][k][1] += f[i][j - 1][k - 1][1]) %= MOD;

		}

	long long ans = 0;

	for (int i = 1; i <= 10; ++i)

		(ans += f[n1][n2][i][0] + f[n1][n2][i][1]) %= MOD;

	printf("%lld", ans);

	return 0;

}

巴特西

[CF118D]Caesar's Legions 题解

题意简述

题解

状态

变量

转移

代码

最新文章

热门文章