Codeforces 1228E. Another Filling the Grid
看到 $n=250$ 显然考虑 $n^3$ 的 $dp$
设 $f[i][j]$ 表示填完前 $i$ 行,目前有 $j$ 列的最小值是 $1$ 的合法方案数
那么对于 $f[i][j]$ ,枚举 $f[i-1][k]$ ,有 $f[i][j]=\sum_{k=0}^{j}\binom{n-k}{j-k}f[i-1][k](m-1)^{n-j}m^k$
这里 $m$ 就是题目的 $k$
$\binom{n-k}{j-k}$ 是因为多出来的 $j-k$ 列 $1$ 可以任选
$(m-1)^{n-j}$ 是保证没有 $1$ 的列不能填 $1$ ,只有 $m-1$ 种填的数
$m^k$ 是那些原本有保证为 $1$ 的列怎么填都行
当然剩下的那 $j-k$ 个位置显然都是 $1$ ,方案数只有 $1$
然后这样就可以做到 $n^3 \log n$ 然后发现竟然 $T$ 了,所以预处理一下 $k \in [0,n],m^k$ 和 $k \in [0,n],(m-1)^k$ 即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int mo=1e9+,N=;
inline int fk(int x) { return x>=mo ? x-mo : x; }
int n,m;
int C[N][N],f[N][N];
int mi[N],mi_1[N];
int main()
{
n=read(),m=read();
for(int i=;i<=n;i++)
{
C[i][]=;
for(int j=;j<=i;j++)
C[i][j]=fk(C[i-][j]+C[i-][j-]);
}
mi[]=mi_1[]=;
for(int i=;i<=n;i++)
{
mi[i]=1ll*mi[i-]*m%mo;
mi_1[i]=1ll*mi_1[i-]*(m-)%mo;
}
for(int j=;j<=n;j++) f[][j]=1ll*C[n][j]*mi_1[n-j]%mo;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
for(int k=;k<=j;k++)
{
int x=1ll*f[i-][k]*C[n-k][j-k]%mo;
int y=1ll*mi_1[n-j]*mi[k]%mo;
f[i][j]=fk(f[i][j]+1ll*x*y%mo);
if(j==k) f[i][j]=fk(f[i][j]-1ll*mi_1[n]*f[i-][k]%mo+mo);
}
}
printf("%d\n",f[n][n]);
return ;
}
正常的做法
但是有些神仙看完数据说:" $n$ 太小了,可以出到 $10^5$ 级别"
所以考虑一下神仙的做法
看到有限制的方案数,考虑容斥!
总方案 - (一行不合法+一列不合法) + (两行不合法+两列不合法+一行一列不合法) - ......
那么写成式子就是长这个样子:
$\sum_{i=0}^{n}\sum_{j=0}^{n}(-1)^{i+j} \binom{n}{i}\binom{n}{j}m^{n^2-n(i+j)+ij}(m-1)^{n(i+j)-ij}$
上面 $m^{n^2-n(i+j)+ij}$ 就是没限制的位置顺便填,$(m-1)^{n(i+j)-ij}$ 就是强制 $i$ 行 $j$ 列的格子不能填 $1$
然后同样预处理一下 $m$ 和 $m-1$ 的幂次就可以做到 $n^2$
对着这个式子继续搞:
$\sum_{i=0}^{n}\sum_{j=0}^{n}(-1)^{i+j} \binom{n}{i}\binom{n}{j}m^{n^2-n(i+j)+ij}(m-1)^{n(i+j)-ij}$
$\sum_{i=0}^{n}(-1)^i\binom{n}{i}\sum_{j=0}^{n}(-1)^j\binom{n}{j}m^{(n-i)(n-j)}(m-1)^{(n-i)j}(m-1)^{ni}$
$\because \sum_{j=0}^{n}(-1)^j\binom{n}{j}m^{(n-i)(n-j)}(m-1)^{(n-i)j}=(m^{n-i}-(m-1)^{n-i})^n$
$\therefore \sum_{i=0}^{n}(-1)^i\binom{n}{i}(m-1)^{ni}(m^{n-i}-(m-1)^{n-i})^n$
$\sum_{i=0}^{n}(-1)^i\binom{n}{i}(m^{n-i}(m-1)^i-(m-1)^n)^n$
然后就可以 $n \log n$ 解决了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=,mo=1e9+;
inline int fk(int x) { return x>=mo ? x-mo : x; }
int n,m,Ans;
int C[N][N],mi[N],m_1i[N];
inline int ksm(int x,int y)
{
int res=;
while(y) { if(y&) res=1ll*res*x%mo; x=1ll*x*x%mo; y>>=; }
return res;
}
int main()
{
n=read(),m=read();
for(int i=;i<=n;i++)
{
C[i][]=;
for(int j=;j<=i;j++) C[i][j]=fk(C[i-][j]+C[i-][j-]);
}
mi[]=m_1i[]=;
for(int i=;i<=n;i++)
{
mi[i]=1ll*mi[i-]*m%mo;
m_1i[i]=1ll*m_1i[i-]*(m-)%mo;
}
for(int i=;i<=n;i++)
{
int t=1ll*C[n][i]*ksm( fk(1ll*mi[n-i]*m_1i[i]%mo - m_1i[n] +mo) , n )%mo;
i& ? Ans=fk(Ans-t+mo) : Ans=fk(Ans+t);
}
printf("%d\n",Ans);
return ;
}
最新文章
- vs2013\2015UML系列之-类图
- 一次性事务和CTE插入数据的比较
- ipython的安装
- 粒子动画Particleground.js
- C#动态执行字符串(动态创建代码)
- 安卓第六天笔记--ListView
- 大数据处理-bitmap是个神马东西
- 进入GRUB改root用户密码
- box-flex 分割
- 在JSP页面中输出JSON格式数据
- 【POJ】Buy Tickets(线段树)
- Mac OS X将CSV格式转换为Excel文档格式,Excel转CSV中文乱码问题
- 搭建php环境时解决jpeg6 make: ./libtool:命令未找到
- jquery 超简单的点赞效果
- P2678 跳石头
- Django学习---快速搭建搜索引擎(haystack + whoosh + jieba)
- Flask 初印象
- 制作windows服务
- transform 属性之 transform-origin与顺序问题
- redis 指定IP访问