前言
我是傻逼，啥都不会
A题 Alice and Her Lost Cat
题意
已知有一只猫沿着简单路径从根节点跑到一个叶子节点上，第$i$个节点可以花$a_i$时间查询监控，返回是否有猫经过，如果有猫经过会告知猫的去向。也可以花$t_i$时间直接查询$i$个叶子节点是否有猫。请制定一种时间代价最小策略确定猫的位置，策略要求事先定好，开始执行策略后不能修改。
tags: 动态规划
题解
一个比较难想清楚的dp题。
设$dp[i][j][0]$表示节点$i$的子树中还有$j$个位置没有确定，且不确定子树$i$中是否有猫。
设$dp[i][j][1]$表示节点$i$的子树中还有$j$个位置没有确定，且子树$i$中一定有猫。
关键点是状态的第三维子树中是否有猫这个状态比较难设出来。
为什么要区分子树中是否已知有猫呢？
如果不知道子树中有猫，则要检查所有叶子
如果子树中已知有猫，那么可以少检查一个点。例如，子树中若有两个点，一定有猫的情况下查一个点就能知道另一个点了。1号节点就处于这种状态。
- 首先最简单的方式就是按照树上背包的方法转移不确定有猫的子树中的情况：
tmp[i + j][0] = min(tmp[i + j][0], dp[id][i][0] + dp[u][j][0]);- 如果节点$i$看了监控（此时可以不管子树i是否一定有猫），那么$i$连接的每个节点u都能确定子树u一定有猫。
tmp[i + j][1] = min(tmp[i + j][1], f[i] + dp[u][j][1]);- 如果节点$i$一定有猫，且i不看监控，那么允许一个儿子节点可以判断为一定有猫，其他儿子节点要另外检查
tmp[i + j][2] = min(tmp[i + j][2], g[i][0] + dp[u][j][0]);
tmp[i + j][3] = min(tmp[i + j][3], g[i][1] + dp[u][j][0]);
tmp[i + j][3] = min(tmp[i + j][3], g[i][0] + dp[u][j][1]);$g[i][0]$表示还没有一个儿子节点选定为一定有猫，$g[i][1]$表示已有一个儿子选定为有猫。
时间复杂度：$O(n^2)$
代码
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const LL inf = 1e18;
int n, a[2022], t[2022], leave[2022];
LL dp[2022][2022][2], tmp[2022][4], f[2022], g[2022][2];
vector<int> eg[2022];
void dfs(int id, int fa){
if(fa && eg[id].size() == 1){
dp[id][0][0] = a[id];
dp[id][0][1] = dp[id][1][0] = dp[id][1][1] = 0;
leave[id] = 1;
return;
}
else dp[id][0][0] = dp[id][0][1] = leave[id] = 0;
for(auto u : eg[id]){
if(u == fa) continue;
dfs(u, id);
}
f[0] = a[id];
for(int i = 1; i <= n; ++i) g[i][0] = g[i][1] = f[i] = inf;
g[0][0] = g[0][1] = 0;
for(auto u : eg[id]){
if(u == fa) continue;
for(int i = 0; i <= leave[id] + leave[u]; ++i)
for(int j = 0; j < 4; ++j) tmp[i][j] = inf;
for(int i = 0; i <= leave[id]; ++i)
for(int j = 0; j <= leave[u]; ++j){
tmp[i + j][0] = min(tmp[i + j][0], dp[id][i][0] + dp[u][j][0]);
tmp[i + j][1] = min(tmp[i + j][1], f[i] + dp[u][j][1]);
tmp[i + j][2] = min(tmp[i + j][2], g[i][0] + dp[u][j][0]);
tmp[i + j][3] = min(tmp[i + j][3], g[i][1] + dp[u][j][0]);
tmp[i + j][3] = min(tmp[i + j][3], g[i][0] + dp[u][j][1]);
}
leave[id] += leave[u];
for(int i = 0; i <= leave[id]; ++i){
dp[id][i][0] = tmp[i][0];
f[i] = tmp[i][1];
g[i][0] = tmp[i][2];
g[i][1] = tmp[i][3];
}
}
for(int i = 0; i <= leave[id]; ++i){
dp[id][i][0] = min(dp[id][i][0], f[i]);
dp[id][i][1] = min(dp[id][i][0], min(g[i][0], g[i][1]));
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt","w", stdout);
#endif
int T; cin >> T;
while(T--){
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int i = 1; i <= n; ++i) cin >> t[i];
for(int i = 1; i <= n; ++i) eg[i].clear();
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= n; ++j) dp[i][j][0] = dp[i][j][1] = inf;
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
eg[u].push_back(v);
eg[v].push_back(u);
}
dfs(1, 0);
LL ans = inf;
for(int i = 0; i <= n; ++i)
ans = min(ans, dp[1][i][1] + t[i]);
cout << ans << endl;
}
return 0;
}B题 Ayano and sequences
题意
有$a,b,c$三个序列，有两种操作：
- 1 l r w：$l\leq i \leq r$，$a_i = w$
- 2 l r w：$l\leq i \leq r$，$c_i += w$
每次操作后，$b_{a_i}$加上$c_i$，求最终序列b的值。
tags: 数据结构
题解
考虑线段树，线段树上节点[l, r]维护序列a值，如果区间$[l,r]$的a全部相同，则线段树对应节点为a值，否则为0。
对于每个节点再维护一个x值与val值，x值表示区间[l,r]上的c值，因为序列c的值有一个时间尺度。我们把问题转换成所有c值都是在0时刻就加上的，再用val值存储这样转换后需要减去多算部分的值。每个节点维护好x值，val值，对于一次操作2，x值与val值都能采用常规的区间加+懒标记的方法解决。
对于一次操作1，我们每次都要在a值发生变化前，将变化前的a值对序列b的答案贡献统计完之后，再将a值改变。与传统的线段树区间操作不同的是，我们每次要找到一个a值相同的区间进行操作。但是因为每次会将一个子区间全部变为一个相同的树，所以这样均摊复杂度仍是$O(n\log n)$的。
代码
#include<bits/stdc++.h>
#define LL unsigned long long
#define ls (node << 1)
#define rs (node << 1 | 1)
#define endl '\n'
using namespace std;
const int maxx = 5e5 + 10;
int n, m;
LL a[maxx], b[maxx], tr[maxx << 2], x[maxx << 2], val[maxx << 2], lazyx[maxx << 2], lazyv[maxx << 2];
void push_up(int node){
tr[node] = (tr[ls] == tr[rs]) ? tr[ls] : 0;
x[node] = x[ls] + x[rs];
val[node] = val[ls] + val[rs];
}
void push_down(int node, int l, int mid, int r){
if(tr[node] > 0){
tr[ls] = tr[rs] = tr[node];
}
if(lazyx[node] || lazyv[node]){
LL tmp = mid - l + 1;
x[ls] += lazyx[node] * tmp;
val[ls] += lazyv[node] * tmp;
lazyx[ls] += lazyx[node];
lazyv[ls] += lazyv[node];
tmp = r - mid;
x[rs] += lazyx[node] * tmp;
val[rs] += lazyv[node] * tmp;
lazyx[rs] += lazyx[node];
lazyv[rs] += lazyv[node];
lazyx[node] = lazyv[node] = 0;
}
}
void build(int node, int l, int r){
if(l >= r){ tr[node] = a[l]; return; }
int mid = (l + r) >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
push_up(node);
}
void add(int node, int l, int r, int ql, int qr, LL w, LL t){
if(ql <= l && qr >= r){
LL tmp = w * (LL)(r - l + 1);
val[node] -= tmp * (t - 1);
x[node] += tmp;
lazyx[node] += w;
lazyv[node] -= w * (t - 1);
return ;
}
int mid = (l + r) >> 1;
push_down(node, l, mid, r);
if(qr <= mid) add(ls, l, mid, ql, qr, w, t);
else if(ql > mid) add(rs, mid + 1, r, ql ,qr, w, t);
else{
add(ls, l, mid, ql, mid, w, t);
add(rs, mid + 1, r, mid + 1, qr, w, t);
}
push_up(node);
}
void update(int node, int l, int r, int ql, int qr, int w, LL t){
if(ql <= l && qr >= r && tr[node]){
LL tmp = x[node] * (t - 1) + val[node];
b[tr[node]] += tmp;
tr[node] = w;
b[tr[node]] -= tmp;
return;
}
int mid = (l + r) >> 1;
push_down(node, l, mid, r);
if(qr <= mid) update(ls, l, mid, ql, qr, w, t);
else if(ql > mid) update(rs, mid + 1, r, ql ,qr, w, t);
else{
update(ls, l, mid, ql, mid, w, t);
update(rs, mid + 1, r, mid + 1, qr, w, t);
}
push_up(node);
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt","w", stdout);
#endif
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
for(int i = 1; i <= m; ++i){
int t, l, r, w;
cin >> t >> l >> r >> w;
if(t & 1) update(1, 1, n, l, r, w, i);
else add(1, 1, n, l, r, w, i);
}
update(1, 1, n, 1, n, n + 1, m + 1);
for(int i = 1; i <= n; ++i) cout << b[i] << " \n"[i == n];
return 0;
}C题 Customs Controls 2
前言
到比赛最后才看到这题，基本想出来，但是没时间了。。。
题意
给定一个有向无环图，构造一种赋值方案：给每个点一个权值$w, w\in[1, 10^9]$，使得从点1出发到达点n的所有路径长度相同，路径长度表示为路径上所有点的点权之和。
tags: 构造，图论
题解
很容易想到，从1号点到i号点的所有路径距离也要相同。计1号点到i号点的距离为$d_i$，如果$u_1,u_2,…u_m$直接连接$v$号点，则$d_{u_1},d_{u_2}…d_{u_m}$应该相同。根据d值建立并查集，我们把每个点的所有前继点放入一个并查集，则可以得到多个不同的并查集。
一个并查集中所有点的d值都会相同，再扫描所有边，建立并查集之间的大小关系，再拓扑排序为每个并查集赋值，之后计算每个点的并查集值与前继点的并查集值的差值作为该点的权值。
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 2e5 + 10;
int n, m, a[maxx], cnt = 0;
int vis[maxx], fa[maxx], pre[maxx], d[maxx], ans[maxx];
vector<int> edg[maxx];
pair<int, int> e[maxx * 3];
int Find(int x){
return fa[x] = (fa[x] == x) ? x : Find(fa[x]);
}
void merge(int u, int v){
if(!v) return;
int fu = Find(u), fv = Find(v);
if(fu != fv) fa[fu] = fv;
}
void topo(int id){
vis[id] = 1;
a[id] = ++cnt;
for(auto u : edg[id]){
--d[u];
if(!d[u]) topo(u);
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt","w", stdout);
#endif
int T;
cin >> T;
while(T--){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
fa[i] = i;
pre[i] = vis[i] = d[i] = 0;
edg[i].clear();
}
cnt = 0;
for(int i = 1; i <= m; ++i){
int u, v;
cin >> u >> v;
e[i] = make_pair(u, v);
merge(u, pre[v]);
pre[v] = u;
}
bool flag = 1;
for(int i = 1; i <= n; ++i) pre[i] = 0;
for(int i = 1; i <= m; ++i){
int u = e[i].first, v = e[i].second;
int fu = Find(u), fv = Find(v);
if(fu == fv){ flag = 0; break; }
edg[fu].push_back(fv);
pre[fv] = fu;
++d[fv];
}
if(!flag){ cout << "No" << endl; continue; }
for(int i = 1; i <= n; ++i){
if(!d[i] && !vis[i]) topo(i);
}
for(int i = 1; i <= n; ++i)
if(d[i] > 0) flag = 0;
if(!flag){ cout << "No" << endl; continue; }
cout << "Yes" << endl;
for(int i = 1; i <= m; ++i){
int u = e[i].first, v = e[i].second;
ans[v] = a[Find(v)] - a[Find(u)];
}
ans[1] = 1;
for(int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
}
return 0;
}D题 Digits
题意
将长度为n的序列分成若干段，每一段求一个和，再将每段的和连接成一个字符串，求多少种分段方式使得最终得到的字符串是回文串。
题解
这题的关键在于能够设计出状态，再进行记忆化搜索。
设$dp[l][r][t][s]$表示区间$[l,r]$能够拼出的字符串中前缀/后缀上为字符串s的个数，用$t=0$表示前缀，$t=1$表示后缀。
考虑转移，以前缀为例，暴力枚举$i$表示区间$[l,i]$中所有数分在一段，这时能够得到这一段和的字符，与状态前缀字符串$s$作比较，有三种情况：
- 如果t是s的一个前缀，则剩余$[i + 1, r]$需要凑出前缀$s - t$
- 如果前缀字符串$s$是t的前缀，则剩余$[i + 1,r]$需要凑出后缀$t-s$
- 否则，这些数不可能作为一段
以上做法其实很暴力，但时间复杂度是有保证的。因为每个数最多为6位且只有150个数，即字符串长度最大为900，对于每个区间$[l,r]$前缀或者后缀最多只有$r - l + 1$种状态，所以用map存dp数组最多只有$O(n^3)$种状态。
时间复杂度：$O(n^3\log a)$。
代码
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int mod = 1e9 + 9;
int n, a[666];
map<string, int> dp[205][205][2];
string after_lcp(string x, string y, bool t){
if(t) reverse(y.begin(), y.end());
if(x.length() >= y.length()){
string pre = x.substr(0, y.length());
if(pre == y) return x.substr(y.length()).append("x");
else return "#";
}
else{
string pre = y.substr(0, x.length());
if(pre == x) return y.substr(x.length());
else return "#";
}
}
bool palin(string s){
string tmp = s;
reverse(tmp.begin(), tmp.end());
return (tmp == s);
}
int solve(int l, int r, bool t, string s){
if(l > r){ return palin(s); }
if(dp[l][r][t].count(s)) return dp[l][r][t][s];
int sum = 0, step = (t ? -1 : 1);
dp[l][r][t][s] = 0;
for(int i = (t ? r : l); i >= l && i <= r; i += step){
sum += a[i];
string tmp = after_lcp(s, to_string(sum), t);
if(tmp == "#") continue;
bool op = 1;
if(tmp.back() == 'x'){ tmp.pop_back(); op = 0; }
if(!t) dp[l][r][t][s] = (dp[l][r][t][s] + solve(i + 1, r, t ^ op, tmp)) % mod;
else dp[l][r][t][s] = (dp[l][r][t][s] + solve(l, i - 1, t ^ op, tmp)) % mod;
}
// cout << l << " " << r << " " << t << " #" << s << ":" << dp[l][r][t][s] << endl;
return dp[l][r][t][s];
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt","w", stdout);
#endif
int T; cin >> T;
while(T--){
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; ++j){
dp[i][j][0].clear();
dp[i][j][1].clear();
}
cout << solve(1, n, 0, "") << endl;
}
return 0;
}I题 Infection
题意
有一个n个点的树，每个点有$a_i$的概率变成传染源，每个点有$p_i$概率被其他点传染，求有$i$个点被传染的概率。
tags:动态规划
题解
设$dp[i][j][1]$表示子树$i$中传染了$j$个点且确定了传染源的概率。
设$dp[i][j][0]$表示子树$i$中传染了$j$个点且未确定了传染源的概率。
直接转移即可。
代码
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 2022, mod = 1e9 + 7;
LL n, dp[maxx][maxx][2], a[maxx], p[maxx], sz[maxx], tmp[maxx][2], ans[maxx];
vector<int> eg[maxx];
LL qpow(LL x, LL y){
LL res = 1;
while(y){
if(y & 1) res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
void dfs(int id, int fa){
dp[id][1][1] = a[id];
dp[id][1][0] = p[id];
dp[id][0][0] = (1 - p[id] + mod) % mod;
sz[id] = 1;
for(auto u : eg[id]){
if(u == fa) continue;
dfs(u, id);
for(int i = 0; i <= sz[id] + sz[u]; ++i) tmp[i][0] = tmp[i][1] = 0;
for(int i = sz[id]; i > 0; --i)
for(int j = sz[u]; j >= 0; --j){
(tmp[i + j][0] += dp[id][i][0] * dp[u][j][0]) %= mod;
(tmp[i + j][1] += dp[id][i][1] * dp[u][j][0] + dp[id][i][0] * dp[u][j][1]) %= mod;
}
sz[id] += sz[u];
for(int i = 1; i <= sz[id]; ++i) dp[id][i][0] = tmp[i][0], dp[id][i][1] = tmp[i][1];
}
for(int i = 1; i <= sz[id]; ++i){
ans[i] = (ans[i] + dp[id][i][1] * (1 - p[fa] + mod)) % mod;
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt","w", stdout);
#endif
cin >> n;
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
eg[u].push_back(v);
eg[v].push_back(u);
}
LL sum = 0;
for(int i = 1; i <= n; ++i){
LL u, v;
cin >> a[i] >> u >> v;
sum += a[i];
p[i] = u * qpow(v, mod - 2) % mod;
}
for(int i = 1; i <= n; ++i) a[i] = a[i] * qpow(sum, mod - 2) % mod;
dfs(1, 0);
for(int i = 1; i <= n; ++i) cout << ans[i] << endl;
return 0;
}K题 Middle Point Graph
题意
有$n$个点$(x_i,y_i,z_i)$，坐标在$(0,1)$里均匀随机，有$m$条边，$(x_i,y_i,z_i)$与$(a_i,b_i,c_i)$的边上存在一个中点$(\frac{a + x}{2}, \frac{b + y}{2}, \frac{c + z}{2})$。
问这$n+m$个点四点共面的期望对数。
tags：图论，三元环/四元环计数
题解
不考虑中点，任意n个点四点共面的期望为0。可以这样想：任意取三点可以构成一个面，另外$n-3$个点相当于在一个$1\times 1\times 1$的立方体里随机撒点，撒到指定面上的概率趋近于0，这就是三维对二维的降维打击。
考虑有一个中点，中点对应边的两个点一定要取，便可以得到一条线，其他任何一个点都与这条线共面。
考虑两个中点：懒得写了，自己讨论一下即可
考虑三个中点：三个中点一定在三元环上，剩下一个点在三元环上的三点中取一个。
考虑四个中点：四元环上。
剩下的问题就是三元环与四元环计数问题：
三元环计数
将无向图转变成有向图：度数大的点指向度数小的点，若度数相同则让标号大的指向标号小。
因为严格定义了点的大小关系，很显然这将是一个有向无环图。在新的有向图中，若一个点的入度为$x$，则说明有$x$个点的度数不小于$x$，则$x<=\sqrt{n}$。直接暴力在有向图上找三元环，每条边都被遍历的次数与它的入度同阶，时间复杂度为$O(m\sqrt{m})$，$m$表示边数。
四元环计数
按照以上同样的方法，将无向图转换成有向无环图。
在新图上枚举每个点，再枚举它的有向边，找到所有在四元环上与该点相邻的点，再枚举这些点的无向边，找到该点在四元环上的对角点，打上标签，计算次数。
代码
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 5e5 + 10, mod = 1e9 + 7;
int n, m;
#define int LL
pair<int, int> p[maxx];
vector<int> eg[maxx], edge[maxx];
int vis[maxx];
bool smaller(int x, int y){
return (eg[x].size() < eg[y].size()) || (eg[x].size() == eg[y].size() && x < y);
}
int solve(int x){
int cnt = 0;
if(x == 3){
for(int i = 1; i <= n; ++i){
for(auto u : edge[i]) vis[u] = 1;
for(auto u : edge[i])
for(auto v : edge[u])
cnt += vis[v];
for(auto u : edge[i]) vis[u] = 0;
}
}
else{
for(int i = 1; i <= n; ++i){
for(auto u : edge[i])
for(auto v: eg[u])
if(smaller(v, i)) cnt += vis[v]++;
for(auto u : edge[i])
for(auto v: eg[u])
vis[v] = 0;
}
}
return cnt;
}
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt","w", stdout);
#endif
int T; cin >> T;
while(T--){
cin >> n >> m;
for(int i = 1; i <= n; ++i) edge[i].clear(), eg[i].clear();
for(int i = 1, u, v; i <= m; ++i){
cin >> u >> v;
p[i] = make_pair(u, v);
eg[u].push_back(v);
eg[v].push_back(u);
}
LL ans = 0;
for(int i = 1; i <= m; ++i){
int u = p[i].first, v = p[i].second;
ans += n - 2 + m - 1;
if(smaller(u, v)) swap(u, v);
edge[u].push_back(v);
}
LL num3 = solve(3), num4 = solve(4);
ans = (ans + num3 * 3 + num4) % mod;
for(int i = 1; i <= n; ++i){
LL d = eg[i].size();
ans = (ans + d * (d - 1) / 2) % mod;
}
cout << ans << endl;
}
}M题 XOR Sum
题意
序列$A = [a_1, a_2 ,\ldots, a_k]$的值表示为
$$
\sum \limits_{i = 1}^k \sum \limits_{j = 1}^{i - 1} a_i \oplus a_j
$$
求长度为k的序列A，值为n，且每个元素的值不超过m的序列A个数。
tags: 数位dp
题解
记忆化搜索，将数字拆位，对每一位考虑，记录有多少位还有考虑不超过m的限制，$n$中在该层数上还有个“1”。
注意代码中x只要超过$81$就不要往下搜，因为每一位最多贡献81个1，如果当前位置还有81个“1”没减，则后面的层凑不齐81个“1”。
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int mod = 1e9 + 7;
LL n, m, k, maxi, dp[45][20][90], C[20][20];
void init(){
C[0][0] = 1;
for(int i = 1; i <= k; ++i){
C[i][0] = 1;
for(int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
LL dfs(int dep, int s, int x){
// cout << dep << " " << s << " " << x << endl;
if(dep == -1) return !x;
if(x < 0 || x > maxi) return 0;
if(dp[dep][s][x] != -1) return dp[dep][s][x];
dp[dep][s][x] = 0;
LL add = (n >> dep) & 1;
if(m & (1ll << dep)){
// cout << dep << endl;
for(int i = 0; i <= s; ++i){
for(int j = 0; j <= k - s; ++j){
int ones = i + j;
int zeros = k - ones;
int sum = ones * zeros;
(dp[dep][s][x] += dfs(dep - 1, i, x * 2 - sum + add) * C[s][i] % mod * C[k - s][j] % mod) %= mod;
}
}
}
else{
for(int ones = 0; ones <= k - s; ++ones){
int zeros = k - ones;
int sum = ones * zeros;
(dp[dep][s][x] += dfs(dep - 1, s, x * 2 - sum + add) * C[k - s][ones] % mod) %= mod;
}
}
return dp[dep][s][x];
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt","w", stdout);
#endif
cin >> n >> m >> k;
maxi = (k / 2) * (k - k / 2);
init();
memset(dp, -1, sizeof(dp));
cout << dfs(40, k, n >> 41);
return 0;
}
