VP 【MX-S2】 解题报告
VP result :
【MX-S2-T1】变
Description
有一个仅由小写字母构成的字符串 \(s\) ，可以将 \(s\) 中不超过 \(K\) 个字符分别替换为任意的小写字母。
定义 \(s\) 的严格循环节为:
一个字符串 \(t\) 被称为 \(s\) 的严格循环节，当且仅当 \(s\) 可以通过将 \(t\) 重复若干次来构造。
例如：
mai是maimai的严格循环节，dx是dx的严格循环节。但ov不是ovo的严格循环节。
最小化修改后的 \(s\) 的最短的严格循环节的长度
Constraints
- Subtask 0（17 pts）：\(k = 0\)，\(|s| \leq 6\)。
- Subtask 1（14 pts）：\(k = 1\)，\(|s| \leq 20\)。
- Subtask 2（16 pts）：\(k = 1\)，\(|s| \leq 500\)。
- Subtask 3（32 pts）：\(k < |s| \leq 10^5\)。
- Subtask 4（21 pts）： 无特殊限制。
对于所有测试数据，保证 \(0 \leq k < |s| \leq 10^6\)，\(s\) 中仅包含小写英文字母。
Solution
记 \(|s|=n\)
显然，严格循环节的长度 \(len\) 一定是 \(n\) 的因数
如果两个位置 \(i,j\) 满足 \(i\equiv j(\bmod len)\) ，那么我们认为 \(i,j\) 是同一类位置，因为在各自的循环节里面，\(i,j\) 所对应的位置是一样的
枚举长度，然后对于每一类位置上字符，统计出现次数，其中最多的出现次数记为 \(cnt\) ，那么把这一类位置上的字符变成一样的代价是 \(n/len -cnt\) ，\(O(N)\) check
总复杂度 \(O(d(N)*N)\) ，\(d(N)\) 表示 \(N\) 的因数个数
Code
点击查看代码
/*
枚举循环节长度，
把每一个位置上的字符取出来，然后记出现最多次数的出现了 cnt 次
那么这里需要 n/len-cnt 次操作
*/
#include<bits/stdc++.h>
using namespace std;
int K,n;
string s;
int cnt[27];
bool check(int len){
int sum=0;
for(int j=1;j<=len;j++){
int mx=0;
for(int i=j;i<=n;i+=len)cnt[s[i]-'a']++;
for(int k=0;k<26;k++)mx=max(mx,cnt[k]),cnt[k]=0;
sum+=n/len-mx;
if(sum>K)return false;
}
return true;
}
vector<int> divs;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>K;
cin>>s;
n=s.size();
s=" "+s;
for(int i=1;i*i<=n;i++)if(n%i==0){
divs.emplace_back(i);
if(i*i!=n)divs.emplace_back(n/i);
}
sort(divs.begin(),divs.end());
for(auto len:divs)
if(check(len)){
cout<<len<<"\n";
return 0;
}
return 0;
}
【MX-S2-T2】排
Description
有 \(n\) 个整数 \(a_1,a_2,\dots,a_n\)
\(f_0=0,f_i= \left\{ \begin{aligned} & f_{i-1} & \ f_{i-1}\times a_i>0, \\ & f_{i-1}+a_i & \ f_{i-1}\times a_i\le 0.\\ \end{aligned} \right. \)
重排 \(a\) 使得 \(f_n\) 最大，求 \(f_n\) 的最大值
Constraints
- Subtask 0（6 pts）：\(n\le10\)。
- Subtask 1（14 pts）：\(n\le 20\)，\(|a_i|\le10\)。
- Subtask 2（8 pts）：\(a\) 中全为正数或全为负数。
- Subtask 3（19 pts）：\(a\) 中有且只有一个正数（注意 \(a\) 中可以有 \(0\)）。
- Subtask 4（29 pts）：\(n \le 200\)，\(|a_i|\le 200\)。
- Subtask 5（24 pts）：无特殊限制。
对于所有测试数据，\(1 \le n \le 2000\)，\(|a_i|\le 2000\)。
Solution
Subtask 2
手玩得到性质，显然答案最大只能取到 \(a\) 的最最大值
Subtask 3
如果没有负数，那么答案就是那一个正数的值
否则就是最大的负数加正数
Final
考虑除去上面两种特殊情况的情况：
首先，\(0\) 对答案没有任何影响，因为不管 \(f_{i-1}\) 的值是多少，\(0\times f_{i-1}=0\) ，所以 \(f_i=f_{i-1}\)
所以 \(a\) 里面只有 \(0\) 和正数或者只有 \(0\) 和负数的情况可以被划到上面的 Subtask2 里面，下面不再考虑这两种情况
下面，我们认为 \(0\) 、正数、负数这三类数之间，两两的正负性均不同
显然， \(a_i\) 会对 \(f_i\) 产生贡献，当且仅当 \(a_i\) 和 \(f_{i-1}\) 的正负性不同
然后就可以非常自然的想到下面这个性质：
\[\forall i, \ |f_i|\le \max_{j=1}^i |a_j| \]我不会严格证明，可以这样感性理解一下：假设 \(a_m>0\) 是前 \(i\) 个数里面的最大值，我希望它能对 \(f_i\) 产生贡献。于是，在重排中，把 \(a_m\) 放在最后面，但是它产生贡献的前提条件是 \(f_{i-1}\le 0\) ，所以 \(f_i=f_{i-1}+a_i\le a_i\) ，然后这一种情况就证完了，其他的情况大概可以类似的想。
有了上面这个性质之后，我们可以猜想，答案可以被写成 \(mx+t\) ，其中 \(mx\) 是 \(a\) 的最大值，\(t\le 0\)
于是我们要找到最大的符合条件的 \(t\)
赛时到这里我就不会了，于是我就猜，如果我直接把它当成一个背包来做，应该是对的
它事实上就是对的，下面简略证明一下：
假设我们在除去 \(mx\) 的 \(a\) 中选出了若干个数，它们对 \(f\) 的贡献为 \(t\le 0\) ，并且这个 \(t\) 是最大的合法的 \(t\)
易知，\(mx>0\)
那么我们这样子构造：
把 \(mx\) 放在最后面
记选出的负数从大到小为 \(neg_1,neg_2,\dots,neg_p\) ，选出的正数从大到小为 \(pos_1,pos_2,\dots,pos_q\)
先在 1 号位置放 \(neg_1\) ，然后把所有没有被选择的负数放在它后面，容易证明，这些数都不会对 \(f\) 产生贡献
然后接下来，从大往小放正数，直到目前的 \(f\) 大于 \(0\) ，接着从大往小放负数，直到 \(f\) 小于 \(0\) ，然后放正数……这样交替操作
考虑两种情况：
- 如果正数用完了，负数还有剩的，而且 \(f\) 仍然小于 \(0\)
那么这些剩下来负数将不会对 \(f\) 产生贡献，但是它们却又被选中了，这与前提矛盾（所有被选中的数都对 \(f\) 有贡献）！
所以这种情况不会发生
- 过程无法继续进行（数放完了，或者负数放完了），而且 \(f\) 依然大于 \(0\)
这个显然不会发生，因为在前提中限制了，总贡献是 \(\le 0\) 的
所以最后肯定是两种数都用完了，并且总贡献 \(\le 0\)
这说明我们上面的构造是对的
根据上面的性质，答案的范围是 \([-2\times 10^6,2\times 10^6]\)
所以 \(dp\) 数组只要开到 \(4\times 10^6\) （下标平移来处理负数），然后因为只需要考虑可行性，所以开成 bitset
足以通过本题
Code
点击查看代码
/*
n<=10 O(N!) 暴力
先写一下特殊性质
全为正数或者全为负数：手玩得到性质
只能取到最大的数
一个正数 pos ：
没有负数的时候 ，取到 pos
否则取到 neg_max+pos
发现特殊性质，任意的 i ,|f_i|<=max_{j=1}^i |a_j|
我们希望最后答案是 pos_max + t
然后要最大化 t (t<=0)
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
const int INF=1e7;
int n;
int a[N];
namespace subtask1{
int p[20];
int calc(){
int f=0;
for(int i=1;i<=n;i++)
if(f*a[p[i]]<=0)f+=a[p[i]];
return f;
}
void solve(){
for(int i=1;i<=n;i++)p[i]=i;
int ans=0;
do{
ans=max(ans,calc());
}while(next_permutation(p+1,p+1+n));
cout<<ans<<"\n";
}
}
namespace subtask3{
bool check(){
int cntneg,cntpos;
cntneg=cntpos=0;
for(int i=1;i<=n;i++)cntneg+=(a[i]<0),cntpos+=(a[i]>0);
return cntpos==n||cntneg==n;
}
void solve(){
cout<<*max_element(a+1,a+1+n)<<"\n";
}
}
namespace subtask4{
bool check(){
bool tg=0;
for(int i=1;i<=n;i++){
if(a[i]>0){
if(tg)return false;
tg=1;
}
}
return tg;
}
void solve(){
int mx=-INF;
for(int i=1;i<=n;i++)
if(a[i]<0)mx=max(mx,a[i]);
if(mx==-INF)cout<<*max_element(a+1,a+1+n)<<"\n";//没有负数，可以直接取到 pos
else cout<<*max_element(a+1,a+1+n)+mx<<"\n"; //存在负数，取到 neg_max+pos
}
}
namespace subtaskf{
const int R=4e6;
bitset<2*R+5> dp;
#define id(i) ((i)+R)
void solve(){
sort(a+1,a+1+n);
// dp[id(0)]=1;
// dp[1]=1;
// dp|=(dp<<1);
// cout<<dp[0]<<" "<<dp[2]<<endl;
// dp.reset();
for(int i=1;i<n;i++){
if(a[i]>0)dp|=(dp<<a[i]);
else if(a[i]<0)dp|=(dp>>(-a[i]));
dp[id(a[i])]=1;
}
// int l=-R,r=R;
// for(;!dp[id(l)];l++);for(;!dp[id(r)];r--);
// cout<<"l: "<<l<<" r: "<<r<<endl;
// for(int i=l;i<=r;i++)cout<<dp[id(i)]<<" ";
for(int i=0;i>=-R;i--)
if(dp[id(i)]){
cout<<a[n]+i<<"\n";
return;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
if(n<=10)
subtask1::solve();
else if(subtask3::check()) //all pos or all neg
subtask3::solve();
else if(subtask4::check())
subtask4::solve();
else
subtaskf::solve();
return 0;
}
【MX-S2-T3】跳
Description
有一个坐标轴，范围是 \(1\sim n\) 。每个点 \(i\) 可以跳到 \(i+1\ (i+1\le n)\) 或 \(i-1\ (i-1\ge 1)\) 或者 \(i\) 的某个因数处。
每个点只能被经过一次（起点默认被经过）。
问从 \(n\) 出发，有多少种方法到达 \(1\) （一旦到达，立刻终止过程），答案对 \(p\) 取模
两种方案不同当且仅当存在一次跳跃后的位置不同或者存在一次跳跃的种类不同。（也就是说，从 \(2\) 通过 \(-1\) 到达 \(1\) 和 通过跳因数到达 \(1\) ，被视为不同的方案）
Constraints
- Subtask 0（8 pts）：\(n\le20\)。
- Subtask 1（11 pts）：\(n\le150\)。
- Subtask 2（23 pts）：\(n\le300\)。
- Subtask 3（26 pts）：\(n\le1000\)。
- Subtask 4（32 pts）：无特殊限制。
对于所有测试数据，\(1\le n\le5\times10^3\)，\(2\le p\le 10^9+7\)。
Solution
Subtask 1
暴搜
Subtask 2
赛时挣扎了很久，写出来一个糖糖的记搜
需要预处理一下每一个数的约数
\(g(cur,lw,hi,mn)\) 表示现在在 \(cur\) ，在进行 \(+1/-1\) 操作后，位置必须在 \([lw,hi]\) 这个区间内，在以往的过程中到达的最小的位置为 \(mn\) ，到达 \(1\) 的方案数
边界条件 \(g(1,*,*,*)=1\)
考虑下一步怎么走：
- \(+1\) 前提： \(cur+1\le hi\)
\(g(cur,lw,hi,mn)\gets g(cur+1,cur+1,hi,mn)\)
- \(-1\) 前提： \(cur-1\ge lw\)
\(g(cur,lw,hi,mn)\gets g(cur-1,lw,cur-1,\min(mn,cur-1))\)
- 跳因数 \(d\) 前提： \(d< mn\)
\(g(cur,lw,hi,mn)\gets g(d,1,mn-1,d)\)
答案为 \(g(n,1,n,n)\)
这个东西的正确性显然，看不懂的可以自己在纸上模拟一下，我懒得画图了
Talk is cheap, show me the code!
vector<int> dvs[N];
map<int,int> g[155][155][155];
int G(int cur,int lw,int hi,int mn){
if(g[cur][lw][hi][mn])return g[cur][lw][hi][mn];
if(cur==1)return g[cur][lw][hi][mn]=1;
if(cur+1<=hi){
g[cur][lw][hi][mn]+=G(cur+1,cur+1,hi,mn),g[cur][lw][hi][mn]%=mod;
}
if(cur-1>=lw){
g[cur][lw][hi][mn]+=G(cur-1,lw,cur-1,min(mn,cur-1)),g[cur][lw][hi][mn]%=mod;
}
for(auto d:dvs[cur]){
if(d>=mn)break;
g[cur][lw][hi][mn]+=G(d,1,mn-1,d);
g[cur][lw][hi][mn]%=mod;
}
return g[cur][lw][hi][mn];
}
Final
考虑如下 dp
\(f(i,j)\) 表示从 \(i\) 出发，途中只经过 \([1,j]\) 中的数，到达 \(1\) 的方案数
边界条件 \(f(1,*)=1\)
显然，只有 \(j\ge i\) 时，\(f(i,j)\) 的值才不为 \(0\)
首先 \(j=i\) 的情况比较好想：
因为限制只能够经过不大于 \(i\) 的值，所以第一步只能 \(-1\) 或者跳因数，有：
\[f(i,i)=f(i-1,i-1)+\sum_{d|i} f(d,i-1) \]然后是 \(j>i\) 的情况：
根据定义，\(f(i,j)\) 是包含 \(f(i,j-1)\) 的情况的，换而言之，\(f(i,j-1)\) 对 \(f(i,j)\) 有贡献
这里有另外一个显然的性质：假设在 \(pos\) 的位置做了一次跳因数，那么之后无论如何也没法走到不小于 \(pos\) 的位置了
然后又因为 \(f(i,j)\) 里面包含了 \(f(i,j-1)\) 的情况，所以它比 \(f(i,j-1)\) 多出来的只有：从 \(i\) 开始一直 \(+1\) 直到 \(j\) ，然后跳因数的情况。并且跳到的因数 \(d\) 满足 \(d<i\) ，有：
\[f(i,j)=f(i,j-1)+\sum_{\substack{ d|j \\ d<i}} f(d,i-1) \]答案是 \(f(n,n)\)
复杂度 \(O(N\sqrt N +N^2d(N))\) ，其中 \(d(N)\) 表示 \(N\) 的因数个数
Code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5005;
int n;ll mod;
vector<int> dvs[N];
ll f[N][N];
/*
f[i][j] 表示从 i 出发，只经过 [1,j] 内的数值，到达 1 的方案数
f[i][i]=f[i-1][i-1]+\sum_{d|i} f[d][i-1]
f[i][j]=f[i][j-1]+\sum_{d|j,d<i} f[d][i-1] (j>i)
边界 f[1][*] =1
*/
ll add(ll x,ll y){return (x+y>=mod?x+y-mod:x+y);}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// cout<<(1&2-1)<<" "<<(1&2)-1<<" "<<(1&(2-1))<<endl;
cin>>n>>mod;
for(int i=1;i<=n;i++){
dvs[i].emplace_back(1);
for(int j=2;j*j<=i;j++)if(i%j==0){
dvs[i].emplace_back(j);
if(j*j!=i)dvs[i].emplace_back(i/j);
}
sort(dvs[i].begin(),dvs[i].end());
}
for(int i=1;i<=n;i++)f[1][i]=1;
for(int i=2;i<=n;i++){
f[i][i]=f[i-1][i-1];
for(auto d:dvs[i])f[i][i]=add(f[i][i],f[d][i-1]);
for(int j=i+1;j<=n;j++){
f[i][j]=f[i][j-1];
for(auto d:dvs[j]){
if(d>=i)break;
f[i][j]=add(f[i][j],f[d][i-1]);
}
}
}
cout<<f[n][n]<<"\n";
// for(int i=1;i<=n;i++,cout<<endl)
// for(int j=i;j<=n;j++)cout<<f[i][j]<<" ";
return 0;
}
Before T4
阅读 T4 题解的时候看到很多人在说一个 排序网络问题 ，所以单独拉出来放在前面
本段参考 Matrix67 的博客
没准未来哪天玩 Signal State 的时候会用到这个呢
遗忘比较排序算法和排序网络
我们有一种神奇的排序算法：遗忘比较排序算法 ，这种排序算法并不依赖于待排序元素的值。具体来说，这种排序算法预先规定了一套操作流程，但是它对于任意的输入序列，都能够返回正确的排序后的序列。举个例子，冒泡排序就是一种遗忘比较排序算法。
现在我们考虑有这样一个暗箱，它有 \(n\) 个输入和 \(n\) 个输出。从输入丢进去一个序列，然后从输出会吐出一个序列。
暗箱里唯一允许的原件称为“比较器”，它的原理写成 C++ 代码大概是这样的：
void cmp(int&x,int&y){
if(x>y)swap(x,y);
}
然后我们可以按照任意顺序在暗箱里面塞若干比较器，它们会按照一个指定的顺序被应用到目前的序列上
这样子构建出的暗箱结构称为“比较网络”。如果对于任意的输入数据，这个暗箱都能够输出有序的序列，那么称其为“排序网络”。
每一种排序网络都能够对应到一个遗忘比较排序算法。
排序网络的真正研究价值在于，它可以让某一些排序在多个处理器的机器上的效率大幅提高。但是这一点和 T4 没有关系，这里不再赘述。
0-1 排序引理
下面介绍 0-1 排序引理，它提供了一种验证一个比较网络是否是排序网络的方式
下面假设固定输入序列的长度 \(n\) ，并且，输入的序列中的元素各不相同（如果有相同元素，那就把位置信息嵌入进去，把它们变成不同的，相当于就是稳定排序），换而言之，输入的可以被看作一个排列
按照排序网络的定义，朴素的验证方法是对所有的 \(n!\) 种可能的输入序列，全部放到该比较网络中，然后看输出结果是否全部有序
0-1 排序引理：我们只需要验证全部的 \(2^n\) 个可能的 01 序列作为输入时，所有的输出是否有序，就可以判断该比较网络是否为排序网络了。
证明很简单，我们直接证逆否命题：如果有一个比较网络不是排序网络，那么至少存在一个 01 序列不能被排序
根据定义，这个比较网络不是排序网络，那么必然存在一种输入的排列，这个网络的输出不是有序的，我们在里面找到一个逆序对 \((i,j)\) ，有 \(a_i>a_j\) （逆序对的定义），那么对于输入的排列，我们将其中所有小于 \(a_i\) 的数都替换为 \(0\) ，其余替换为 \(0\) ，就得到了一个长度为 \(n\) 的 01 序列。然后把这个 01 序列作为输入，原来曾经发生过交换的地方现在仍然会交换，原来不发生交换的地方现在也同样不会发生交换。所以最后这两个位置上的数的大小关系不会改变，逆序对依然存在。所以就存在至少一个 01 序列不能被排序。证毕！
至此为止，所有和 T4 有关的内容已经写完了，更多的移步 Matrix67 的文章观看（如果觉得我写的唐的也推荐去看 Matrix67 的）。
【MX-S2-T4】换
Description
给定 \(n,V\) 和一个长为 \(m\) 的序列 \((p_1,q_1),(p_2,q_2),\dots,(p_m,q_m)\)。
请求出有多少长度为 \(n\) 的正整数序列 \(a\)，其所有元素 \(a_i\) 满足 \(1\le a_i\le V\)，将其按 \(k=1,2,\dots,m\) 依次执行如下操作后，\(a\) 不降：
- 若 \(a_{p_k}>a_{q_k}\)，则交换 \(a_{p_k}\) 与 \(a_{q_k}\) 的值。
答案对 \(10^9+7\) 取模。
Constraints
- Subtask 0（8 pts）：\(n\le6\)，\(V\le 8\)，\(m \le 50\)。
- Subtask 1（31 pts）：\(n \le 8\)。
- Subtask 2（37 pts）：\(n \le 15\)。
- Subtask 3（24 pts）：无特殊限制。
对于所有测试数据，\(1\le n\le 18\)，\(1\le V\le 10^9\)，\(1\le m\le 500\)，\(1\leq p_k,q_k\leq n\)，注意不保证 \(p_k\) 和 \(q_k\) 的大小关系，且数据可能存在 \(p_k=q_k\)。
Solution
容易发现本题的这个交换操作就是前面写的比较器元件在干的事情，所以事实上给出的这 \(m\) 个操作组成了一个比较网络。
然后我们用一下 0-1 排序引理 ，虽然本题给出的比较网络不一定是排序网络，但是我们可以通过 0-1 排序引理来得出哪些 01 序列在输入网络之后得到的输出时有序的，然后把正常的序列映射到这些 01 序列上面就基本上做完了，但是由于本题值域较大，所以还有一步从原始序列映射到离散化序列上的步骤。
所以我们三步走
合法 01 序列
首先我们要算出哪些 01 序列是合法的（输入网络后得到的输出是有序的）
直接模拟，复杂度 \(O(M2^N)\)
原始序列到离散化序列
由于本题的操作是基于比较的，所以数值到底是多少不重要，我们只考虑相对顺序
可以看作给原始序列染色，枚举一个总颜色数量 \(col\) ，为了防止重复贡献，强制每一种颜色至少给一个元素染色，然后这个颜色编号大小对应的就是相对大小
然后再把数值映射到颜色上，颜色数量为 \(col\) 时，方案为 \({V \choose col}\)
复杂度 \(O(N\log N)\)
离散化序列到 01 序列
考虑什么情况下一个离散化的序列是能够被给出的比较网络排序的：我们弄一个阈值 \(t\) ，\(t\) 从小往大（或者从大往小）变化。每次把小于等于 \(t\) 的都置为 \(0\) ，把大于 \(t\) 的都置为 \(1\) ，然后如果这个过程中产生的所有 01 序列都是合法的，那么这个序列就是合法的（能够被比较网络排序）
证明思路类似上面证明 0-1 排序引理的思路，此处略去。
考虑状压 dp
\(dp_{i,j}\) 表示阈值 \(t=i\) 时，对应的 01 序列的状压为 \(j\)，且对于任意的 \(t\le i\) ，其对应的 01 序列都时合法的，满足以上条件的离散化序列的个数。有：
\[dp_{i,j}= \left\{ \begin{aligned} & 0 & \ j\notin S, \\ & \sum_{k}dp_{i-1,k} & j\in S.\\ \end{aligned} \right. \]其中 \(S\) 是合法的 01 序列的状压组成的集合，\(k\) 是 \(j\) 的二进制表示的真子集，由于上面第二步中限制了离散化序列的值域是连续的，所以阈值 \(t\) 的每一次变化都会导致对应的 01 序列产生至少一个位置的变化，所以 \(k\neq j\) 。
然后就是典中典高维前缀和
复杂度 \(O(N^22^N)\)
于是总复杂度 \(O((M+N^2)2^N)\)
Code
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int n,V,m,nPtn;
int p[505],q[505];
bool Valid[(1<<18)+5];
//Valid[ptn] 表示压缩为 ptn 的 01 串是否在经过所有操作之后合法
int o1s[20];
//01str
ll dp[20][(1<<18)+5],sum[20][(1<<18)+5];
void precompute(){
for(int ptn=0;ptn<nPtn;ptn++){
for(int i=1;i<=n;i++)o1s[i]=(ptn>>(i-1))&1;
for(int i=1;i<=m;i++)
if(o1s[p[i]]>o1s[q[i]])swap(o1s[p[i]],o1s[q[i]]);
Valid[ptn]=1;
for(int i=1;i<n;i++)Valid[ptn]&=(o1s[i]<=o1s[i+1]);
}
// for(int ptn=0;ptn<nPtn;ptn++)cout<<Valid[ptn]<<" ";cout<<"\n";
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int ptn=0;ptn<nPtn;ptn++)sum[i-1][ptn]=dp[i-1][ptn];
for(int j=0;j<n;j++)
for(int k=0;k<nPtn;k++)if(((k>>j)&1))
sum[i-1][k]=(sum[i-1][k]+sum[i-1][k^(1<<j)])%mod;
for(int ptn=0;ptn<nPtn;ptn++)if(Valid[ptn])
dp[i][ptn]=(sum[i-1][ptn]-dp[i-1][ptn]+mod)%mod;
}
}
ll qpow(ll x,ll y){
ll ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>V>>m;
nPtn=(1<<n);
for(int i=1;i<=m;i++)cin>>p[i]>>q[i];
precompute();
ll ans=0,toMul=1;
for(int col=1;col<=min(V,n);col++){
toMul=toMul*(V-col+1ll)%mod*qpow(col,mod-2)%mod;
// cout<<dp[col][nPtn-1]<<"\n";
ans=(ans+dp[col][nPtn-1]*toMul%mod)%mod;
}
cout<<ans<<"\n";
return 0;
}
事实上，到现在为止，我还是不太会用高维前缀和，以后有机会系统学一下