2020-2021:teams:legal_string:组队训练比赛记录:contest6
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest6 [2021/07/28 18:44] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:contest6 [2021/08/11 20:47] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^ | ||
| - | | A | 2 | 0 | 0 | | + | | A | 2 | 1 | 0 | |
| | B | 1 | 2 | 2 | | | B | 1 | 2 | 2 | | ||
| | C | 1 | 1 | 2 | | | C | 1 | 1 | 2 | | ||
| - | | D | 0 | 0 | 0 | | + | | D | 2 | 0 | 0 | |
| | E | 2 | 0 | 2 | | | E | 2 | 0 | 2 | | ||
| | F | 2 | 0 | 1 | | | F | 2 | 0 | 1 | | ||
| - | | G | 2 | 0 | 0 | | + | | G | 2 | 1 | 0 | |
| | H | 0 | 0 | 0 | | | H | 0 | 0 | 0 | | ||
| | I | 2 | 0 | 1 | | | I | 2 | 0 | 1 | | ||
| 行 143: | 行 143: | ||
| } | } | ||
| } | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== D. Count ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个 $n\times n$ 的网格图，有 $k$ 个格子不能选，分别为 $(r_1,c_1),(r_2,c_2)\cdots (r_k,c_k)$。 | ||
| + | |||
| + | 在此基础上选择 $m$ 个格子，满足每行每列至少选中一个格子，$r=c$ 和 $r+c=n+1$ 的对角线上至少选中一个格子。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 考虑容斥，首先枚举 $k$ 个不能选的格子的子集，强制选中这些格子，设共选了 $c$ 个格子。 | ||
| + | |||
| + | 进一步容斥计算在强制选中这些格子对应的方案数，考虑是否禁止对角线、是否禁止某行某列。 | ||
| + | |||
| + | 设 $\text{dp}(i,j,k)$ 表示强制只选 $i$ 行，只选 $j$ 列，且这些位置中有 $k$ 个位置因为强制不选对角线被禁止的方案数。 | ||
| + | |||
| + | 于是状态 $(i,j,k)$ 对应的方案数为 ${i\times j-k-c \choose m-c}\text{dp}(i,j,k)$。接下来考虑如何计算 $\text{dp}(i,j,k)$。 | ||
| + | |||
| + | 事实上，只有形如第 $i$ 行、第 $i$ 列、第 $n+1-i$ 行、第 $n+1-i$ 列这样的四元组会对 $k$ 产生影响。 | ||
| + | |||
| + | 于是可以将每个四元组看成一个物品，$O(2^4)$ 枚举这四元组每个元素的选择情况计算对 $k$ 的影响，然后三维背包合并所有四元组贡献。 | ||
| + | |||
| + | 由于 $(i,j,k)$ 的每个维度上界都是 $O(n)$，所以总时间复杂 $O\left(2^kn^4\right)$。实际上还是比较卡的，但题目数据比较友好。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=35,MAXV=MAXN*MAXN,mod=1e4+7; | ||
| + | int dp[MAXN][MAXN][MAXN<<1],temp[MAXN][MAXN][MAXN<<1]; | ||
| + | int sr[MAXN],sc[MAXN],node[MAXN][2],frac[MAXV],invf[MAXV]; | ||
| + | int quick_pow(int n,int k){ | ||
| + | int ans=1; | ||
| + | while(k){ | ||
| + | if(k&1)ans=ans*n%mod; | ||
| + | n=n*n%mod; | ||
| + | k>>=1; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int C(int n,int m){ | ||
| + | return frac[n]*invf[m]%mod*invf[n-m]%mod; | ||
| + | } | ||
| + | int solve(int n,int _k,int _c,int _s){ | ||
| + | int tf1=2,tf2=2,cnt=0; | ||
| + | mem(sr,0);mem(sc,0); | ||
| + | _for(i,0,_k){ | ||
| + | if(_s&(1<<i)){ | ||
| + | sr[node[i][0]]=1,sc[node[i][1]]=1; | ||
| + | if(node[i][0]==node[i][1]) | ||
| + | tf1=1; | ||
| + | if(node[i][0]+node[i][1]==n+1) | ||
| + | tf2=1; | ||
| + | cnt++; | ||
| + | } | ||
| + | } | ||
| + | int ans=0; | ||
| + | _for(f1,0,tf1)_for(f2,0,tf2){ | ||
| + | mem(dp,0); | ||
| + | dp[0][0][0]=1; | ||
| + | int mr=0,mc=0,mk=0; | ||
| + | for(int p1=1,p2=n;p1<=p2;p1++,p2--){ | ||
| + | mem(temp,0); | ||
| + | if(p1!=p2){ | ||
| + | mr+=2,mc+=2,mk+=4; | ||
| + | _for(r1,sr[p1],2)_for(r2,sr[p2],2) | ||
| + | _for(c1,sc[p1],2)_for(c2,sc[p2],2){ | ||
| + | int dr=r1+r2,dc=c1+c2; | ||
| + | int dk=(r1&c1&f1)+(r2&c2&f1)+(r1&c2&f2)+(r2&c1&f2); | ||
| + | _rep(i,dr,mr)_rep(j,dc,mc)_rep(k,dk,mk) | ||
| + | temp[i][j][k]+=dp[i-dr][j-dc][k-dk]; | ||
| + | } | ||
| + | } | ||
| + | else{ | ||
| + | mr++,mc++,mk++; | ||
| + | _for(dr,sr[p1],2)_for(dc,sc[p1],2){ | ||
| + | int dk=dr&dc&(f1|f2); | ||
| + | _rep(i,dr,mr)_rep(j,dc,mc)_rep(k,dk,mk) | ||
| + | temp[i][j][k]+=dp[i-dr][j-dc][k-dk]; | ||
| + | } | ||
| + | } | ||
| + | _rep(i,0,mr)_rep(j,0,mc)_rep(k,0,mk) | ||
| + | dp[i][j][k]=temp[i][j][k]%mod; | ||
| + | } | ||
| + | _for(i,0,MAXN)_for(j,0,MAXN)_for(k,0,MAXN<<1){ | ||
| + | int tot=i*j-k; | ||
| + | if(tot>=_c){ | ||
| + | int s=C(tot-cnt,_c-cnt)*dp[i][j][k]%mod; | ||
| + | int sg=(n-i)+(n-j)+f1+f2+cnt; | ||
| + | if(sg&1) | ||
| + | ans=(ans-s)%mod; | ||
| + | else | ||
| + | ans=(ans+s)%mod; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | return (ans+mod)%mod; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),k=read_int(),c=read_int(); | ||
| + | _for(i,0,k) | ||
| + | node[i][0]=read_int(),node[i][1]=read_int(); | ||
| + | frac[0]=1; | ||
| + | _for(i,1,MAXV) | ||
| + | frac[i]=frac[i-1]*i%mod; | ||
| + | invf[MAXV-1]=quick_pow(frac[MAXV-1],mod-2); | ||
| + | for(int i=MAXV-1;i;i--) | ||
| + | invf[i-1]=invf[i]*i%mod; | ||
| + | int ans=0; | ||
| + | _for(i,0,1<<k) | ||
| + | ans=(ans+solve(n,k,c,i))%mod; | ||
| + | enter(ans); | ||
| return 0; | return 0; | ||
| } | } | ||
| 行 427: | 行 543: | ||
| jxm：找操作中的不变量可能是解题的一种思路，比如这场的 $B$ 或者博弈论题。 $A$ 据说是 $\text{dp}$ 优化题，但没看懂题解，先咕了。 | jxm：找操作中的不变量可能是解题的一种思路，比如这场的 $B$ 或者博弈论题。 $A$ 据说是 $\text{dp}$ 优化题，但没看懂题解，先咕了。 | ||
| + | |||
| + | update：补完A了，感觉性质比较玄学。 | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest6.1627469061.txt.gz · 最后更改: 2021/07/28 18:44 由 jxm2001
