Warning: session_start(): open(/tmp/sess_8b32b3ebe0d6c9ec27f164363b343c10, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:组队训练比赛记录:contest6 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:legal_string:组队训练比赛记录:contest6

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
2020-2021:teams:legal_string:组队训练比赛记录:contest6 [2021/08/01 12:17]
lgwza [补题情况]
2020-2021:teams:legal_string:组队训练比赛记录:contest6 [2021/08/11 20:47] (当前版本)
jxm2001
行 7: 行 7:
 |  B  |  1  |  2  |  2  |  |  B  |  1  |  2  |  2  | 
 |  C  |  1  |  1  |  2  |  |  C  |  1  |  1  |  2  | 
-|  D  |  ​ ​| ​ 0  |  0  | +|  D  |  ​ ​| ​ 0  |  0  | 
 |  E  |  2  |  0  |  2  |  |  E  |  2  |  0  |  2  | 
 |  F  |  2  |  0  |  1  |  |  F  |  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;
 } }
2020-2021/teams/legal_string/组队训练比赛记录/contest6.1627791433.txt.gz · 最后更改: 2021/08/01 12:17 由 lgwza