1. BD202317 石碑文（状压dp）
在历史的长河中，石碑静静地矗立，风雨侵蚀，岁月沧桑，它们见证了历史的变迁，承载了无数的故事和传说。这些石碑，如同历史的见证者，在它们的表面，残留下的文字，似乎在诉说着那一段段遥远的往事。
这些文字，犹如古老的诗篇，是历史与文化的交织，是时间的印记，是古人留给我们的宝贵遗产。它们笔画繁复，有的严谨大方，有的古朴深沉。每一个字都似乎在诉说着一个古老的故事，每一段文字都在细语着一段历史的传说。
在破败的石碑上，我们仿佛可以看到那些古人的智慧，他们的喜怒哀乐，他们的悲欢离合。这些文字，如同古老的旋律，或低沉悲壮，或慷慨激昂，它们是古人对历史的呼喊，是对生活的热烈歌颂。
现在小度在石碑上找到了一些文字，这些文字包含N个英文字符，这些文字依稀可以辨认出来，另一些文字难以辨认，在可以辨认出来的文字中，小度发现了他喜欢的文字“shs”，小度习惯把喜欢的事物说三遍及以上，他希望知道原始的石碑上有多少种可能性会出现三次及以上“shs”（三个“shs”不能出现重合，即“shshs”只能算出现一次“shs”），这样的碑文可能有很多，你只需要输出答案对1e9+7取模的结果即可。
格式
输入：一行输入的是整数 n，（1≤n≤106），表示碑文长度 。
输出：一行一个数字，表示有多少种字符串可能出现了三个及以上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≤107,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 _ ^ _;
}