期中测：光之箭矢
题意：
随机一个排列，按照排列的顺序选取物品，问期望有多少子集使得选取方案与最优方案相同
做法：
注意到对于一个子集，答案与未选取的部分如何排列无关，可以将其转化为一个计数问题，即对每一个子集，统计合法排列的方案数，再乘上01可重排列数，将答案相加，最后除以全排列数即为所求期望。
有注意到，对于一个子集，答案与选取顺序无直接联系，只与最后选了那些元素有关。所以设三进制状压DP，0表示不在子集中，1表示在子集中且被选中，2表示在子集中且未被选中，表示1和2在子集中，按排列顺序选中了1中的元素的排列个数。这里必须用三进制状压，否则无法区分出元素是否在子集中，而这两者是有区别的。
转移时考虑把一个不在子集中元素加入子集中，如果能装入背包就装，否则不装，由于转移是无序的（状压的转移都是无序的），所以转移囊括了子集所有的排列方案。
我们还需要一个小优化，如果dp[s]=0就跳过，事实上可以证明有效状态不超过350万，再卡卡常即可AC。
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register
#define go(i,a,b) for(re int i=a;i<=b;++i)
#define com(i,a,b) for(re int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
const int inf=0x3f3f3f3f,N=15,mod=998244353;
typedef long long ll;
int n,V,v[20],w[20],pw3[20],a[3],inv[20],fac[20],dp[15010000];
ll ansex[1<<N],sv[1<<N],sw[1<<N];
inline void read(int &x){
x=0;char c=getchar(),f=1;
while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
x*=f;
}
template<typename T>inline void gmax(T &x,const T &y){ x=x>y?x:y; }
template<typename T>inline void add(T &x,const T &y){ x=(x+y>=mod?x+y-mod:x+y); }
void init(){
read(n),read(V);
go(i,0,n-1) read(v[i]),read(w[i]);
pw3[0]=1;
go(i,1,n) pw3[i]=pw3[i-1]*3;
fac[0]=1;
go(i,1,n) fac[i]=(ll)fac[i-1]*i%mod;
inv[0]=inv[1]=1;
go(i,2,n) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
go(i,1,n) inv[i]=(ll)inv[i-1]*inv[i]%mod;
}
signed main(){
//freopen("input.txt","r",stdin);
int ans=0;
init();
for(re int i=1;i<1<<n;++i){
sv[i]=sv[i-1&i]+v[__builtin_ctz(i)];
sw[i]=sw[i-1&i]+w[__builtin_ctz(i)];
if(sv[i]<=V) ansex[i]=sw[i];
go(j,0,n-1) if(i>>j&1) gmax(ansex[i],ansex[i^1<<j]);
}
dp[0]=1;
for(re int i=0;i<pw3[n];++i) if(dp[i]){
mem(a,0);
go(j,0,n-1) a[i/pw3[j]%3]|=1<<j;
go(j,0,n-1)
if(a[0]>>j&1){
if(sv[a[1]]+v[j]<=V) add(dp[i+pw3[j]],dp[i]);
else add(dp[i+2*pw3[j]],dp[i]);
}
}
int sum;
for(re int i=0;i<1<<n;++i){
sum=0;
for(re int j=i;;j=(j-1)&i){
if(ansex[i]==sw[j]){
int s=0;
go(k,0,n-1){
if(j>>k&1) s+=pw3[k];
else if(i>>k&1) s+=2*pw3[k];
}
add(sum,dp[s]);
}
if(!j) break;
}
add(ans,int((ll)sum*fac[n]%mod*inv[__builtin_popcount(i)]%mod));
}
cout<<(ll)ans*inv[n]%mod;
return 0;
}期末测：黑白剑士
事实上该题较期中测更简单，但我却耗费了更长的时间，一是因为身体原因，二是因为此题更不易理解
题意：
给出一个01矩阵，第i行第j个点的权值为ia+jb（这是此题能做的关键，也就是该题不同于其他题的“特殊性质”，也就是解题的关键所在，考试时我们要关注这样的特殊性质），我们可以对每一行每一列取反，求最大权值，a，b可以小于0。
思路：
暴力：注意到m<=10，可以枚举，然后每行就只有两种状态，且互相独立，可以取较大值，复杂度\(O(n2^m)\)。
70分做法：由于所有数初始都为1，故枚举列之后，每行选取的数相同，故一行的权值只与行数i有关。对应取反或不取反两种状态，可表示为ff1=ai+b和f2=ci+d，为两条一次函数，只有一个或0个交点，所以可以二分交点的位置，交点之前某条直线优，交点之后另一条直线更优，可以做到logn快速计算
100分做法：受70分做法启发，我们把初始状态相同的行分为一组，这样的组最多2^m个，再用70分的做法计算，复杂度\(O(log(n)*2^2m)\)。