1. BD202317 石碑文（状压dp）

在历史的长河中，石碑静静地矗立，风雨侵蚀，岁月沧桑，它们见证了历史的变迁，承载了无数的故事和传说。这些石碑，如同历史的见证者，在它们的表面，残留下的文字，似乎在诉说着那一段段遥远的往事。

这些文字，犹如古老的诗篇，是历史与文化的交织，是时间的印记，是古人留给我们的宝贵遗产。它们笔画繁复，有的严谨大方，有的古朴深沉。每一个字都似乎在诉说着一个古老的故事，每一段文字都在细语着一段历史的传说。

在破败的石碑上，我们仿佛可以看到那些古人的智慧，他们的喜怒哀乐，他们的悲欢离合。这些文字，如同古老的旋律，或低沉悲壮，或慷慨激昂，它们是古人对历史的呼喊，是对生活的热烈歌颂。

现在小度在石碑上找到了一些文字，这些文字包含N个英文字符，这些文字依稀可以辨认出来，另一些文字难以辨认，在可以辨认出来的文字中，小度发现了他喜欢的文字“shs”，小度习惯把喜欢的事物说三遍及以上，他希望知道原始的石碑上有多少种可能性会出现三次及以上“shs”（三个“shs”不能出现重合，即“shshs”只能算出现一次“shs”），这样的碑文可能有很多，你只需要输出答案对1e9+7取模的结果即可。

格式

输入：一行输入的是整数 n，（1≤n≤10⁶），表示碑文长度。
输出：一行一个数字，表示有多少种字符串可能出现了三个及以上shs。

样例

输入：10
输出：104

说明

样例解释：shsshsshs* 26种，* shsshsshs 26种，shsshs* shs 26种，shs* shsshs 26种。

点击查看代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);
#define int long long
#define mod 1000000007

using namespace std;

const int N = 1e6 + 10;

int n, m;
int f[N][10];

void solve()
{
	cin >> n;
	f[0][0] = 1;
	for(int i = 0; i < n; i ++)
	{
		for(int j = 0; j < 10; j ++)
		{
			if(j == 9)
				f[i + 1][j] = (f[i + 1][j] + 26 * f[i][j]) % mod;
			else if(j % 3 == 1)
			{
				f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;
				f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j]) % mod;
				f[i + 1][j / 3 * 3] = (f[i + 1][j / 3 * 3] + 24 * f[i][j]) % mod;
			}
			else
			{
				f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j]) % mod;
				f[i + 1][j / 3 * 3] = (f[i + 1][j / 3 * 3] + 25 * f[i][j]) % mod;
			}
		}
	}
	cout << f[n][9] << '\n';
}

signed main()
{
	IOS;
	// get();
	int _ = 1;
	// cin >> _;
	while(_ --)
		solve();
	return _ ^ _;
}

2. BD202318 染色游戏

小度在公园玩一个染色游戏，染色板为一个长为 n，宽为 m 的长方形网格，一开始它们的颜色都是白色。
小度的颜料可以将其中的 k 个的格子染成黑色，颜料需要用完，且不能重复染色。
最终的要求是任意相邻两行或任意相邻两列要么保证完全一致，要么完全不一致。

完全一致指相邻行/列中相邻的格子要么同为白色，要么同为黑色。
完全不一致指相邻行/列中相邻的格子一个为白色，一个为黑色。

请计算有多少种染色方案。

格式：

输入：一行，三个整数 n,m,k(1≤n,m≤10⁷,0≤k≤n × m) 。
输出：一行，输出答案，由于答案过大所以输出答案对 998244353 取模的结果。

样例

输入：2 2 2
输出：6

说明

点击查看代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);
#define int long long
#define fi first
#define se second
#define pb push_back
// #define mod 1000000007
#define mod 998244353

using namespace std;

const int N = 1e7 + 10;

int n, m, k, ans;
int inv[N];
int cm[N], cn[N];

int qmi(int a, int b)
{
	int ans = 1;
	while(b)
	{
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

void init()
{
	inv[0] = inv[1] = 1;
	int t = max(n, m);
	for(int i = 2; i <= t; i ++)
		inv[i] = ((mod - mod / i) * inv[mod % i]) % mod;
	cm[0] = cn[0] = 1;
	for(int i = 1; i <= m; i ++)
		cm[i] = (((cm[i - 1] * (m - i + 1)) % mod) * inv[i]) % mod;
	for(int i = 1; i <= n; i++)
		cn[i] = (((cn[i - 1] * (n - i + 1)) % mod) * inv[i]) % mod;
}

void solve()
{
	cin >> n >> m >> k;
	if(k == 0||k == n * m)
	{
		cout << "1\n";
		return ;
	}
	init();
	int t = m / 2;
	for(int i = 0; i < t; i ++)
	{
		int a = (m - i) * n - k;
		int b = (m - 2 * i);
		if(a < 0||a % b||a / b > n)
			continue;
		int y = a / b;
		ans = (ans + cm[i] * cn[y]) % mod;
	}
	if(!(m & 1)&&(n * m / 2) == k)
		ans = (ans + cm[m / 2] * qmi(2, n - 1)) % mod;
	cout << ans << '\n';
}

signed main()
{
	IOS;
	// get();
	int _ = 1;
	// cin >> _;
	while(_ --)
		solve();
	return _ ^ _;
}

526互联

2023年百度之星初赛第三场

2. BD202318 染色游戏