只是基础题目
首先直接当成有 \(n\) 个白球做
这题目转移还是比较套路的
\(f_{i,j}\) 表示 \(i\) 个白球，\(j\) 个颜色的方案数
转移直接分为两种情况：
直接添加一个白球和添加一种颜色
添加白球直接添加即可，即
f[i][j]=add(f[i][j],f[i-1][j]);
然后直接找空位组合数添加就好了，即
f[i][j]=add(f[i][j],f[i][j-1]*(n-j+1)%mod*C(n*k-i-1-(j-1)*(k-1),k-2)%mod);
关于为啥后面的是 \(k-2?\)
首先剩下了 \(k-1\) 个带颜色的，然后钦定第一个位置是当前颜色，否则会记重
最后答案 \(f_{n,n}\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,a,b) for(register int i=a;i<=b;++i)
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
return res*f;
}
const int mod=1e9+7,N=4e6+10;
int fac[N],inv[N],n,k,f[2010][2010];
inline int ksm(int x,int y)
{
int res=1; for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
return res;
}
inline int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
signed main()
{
fac[0]=1; inv[0]=1;
For(i,1,N-1) fac[i]=fac[i-1]*i%mod;
inv[N-1]=ksm(fac[N-1],mod-2);
for(int i=N-2;i>=1;--i) inv[i]=inv[i+1]*(i+1)%mod;
n=read(); k=read();
for(int i=0;i<=n;++i) f[i][0]=1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=i;++j)
{
f[i][j]=add(f[i][j],f[i-1][j]);
f[i][j]=add(f[i][j],f[i][j-1]*(n-j+1)%mod*C(n*k-i-1-(j-1)*(k-1),k-2)%mod);
}
} printf("%lld\n",f[n][n]);
return 0;
}
}
signed main(){return yspm::main();}
这题数形结合好
考虑每个 \(i,j\) 的本质
是在一个平面直角坐标系里面从\((-a_i,-b_i)\) 到 \((a_j,b_j)\) 的方案
然后把所有的撒到一个平面直角坐标系里面然后做转移
最后减掉那些自己转移到自己的
#include<bits/stdc++.h>
using namespace std;
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
return res*f;
}
const int M=2e5+10,N=4040,mod=1e9+7,s=2010;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int del(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int id1(int x){return x+s;}
inline int id2(int x){return s-x;}
int a[M],b[M],f[N][N],inv[N],fac[N],ans,n;
inline int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int ksm(int x,int y){int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod; return res;}
signed main()
{
fac[0]=1; inv[0]=1; for(int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%mod;
inv[N-1]=ksm(fac[N-1],mod-2); for(int i=N-2;i>=1;--i) inv[i]=1ll*inv[i+1]*(i+1)%mod;
n=read();
for(int i=1;i<=n;++i)
{
a[i]=read(),b[i]=read();
++f[id2(a[i])][id2(b[i])];
}
for(register int i=1;i<=s*2;++i)
{
for(register int j=1;j<=s*2;++j)
{
f[i][j]=add(f[i][j],f[i-1][j]);
f[i][j]=add(f[i][j],f[i][j-1]);
}
}
for(int i=1;i<=n;++i) ans=add(ans,f[id1(a[i])][id1(b[i])]),ans=del(ans,C(2*(a[i]+b[i]),2*a[i]));
ans=1ll*ans*inv[2]%mod; cout<<ans<<endl;
return 0;
}
}
signed main(){return yspm::main();}
[MtOI2018]情侣？给我烧了！ 的加强版
先用高考数学的知识推出来这样一个式子
\(g_i\) 表示 \(i\) 对情侣的错排方案
然后推这个错排的式子
按照普通错排的做法
钦定第一排是错误的，这里要乘上 \(2n\times (2n-2)\)
然后考虑剩下的方案
两对情侣中剩下的两个人不坐在一起，那么是一个 \(g_{i-1}\)
反之则为 \(2\times(i-1)\times g_{i-2}\)
（选择一个座位）
所以就可以 \(O(n)\) 预处理，然后可以 \(O(1)\) 回答
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(register int i=a;i<=b;++i)
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
return res*f;
}
const int mod=998244353,N=5e6+10;
int inv[N],fac[N],g[N],p[N],n,k;
inline int C(int n,int m){return 1ll*inv[m]*fac[n]%mod*inv[n-m]%mod;}
inline void work(int n,int k)
{
printf("%lld\n",1ll*C(n,k)*C(n,k)%mod*fac[k]%mod*p[k]%mod*g[n-k]%mod);
return ;
}
inline int ksm(int x,int y)
{
int res=1; for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
return res;
}
signed main()
{
fac[0]=inv[0]=p[0]=1; g[0]=1;
For(i,1,N-1) fac[i]=1ll*fac[i-1]*i%mod,p[i]=1ll*p[i-1]*2%mod;
For(i,2,N-1) g[i]=1ll*2*i%mod*(2*i-2)%mod*((1ll*2*(i-1)%mod*g[i-2]%mod+g[i-1])%mod)%mod;
inv[N-1]=ksm(fac[N-1],mod-2); for(int i=N-2;i>=1;--i) inv[i]=1ll*inv[i+1]*(i+1)%mod;
int T=read();
while(T--)
{
n=read();
for(int i=0;i<=n;++i) work(n,i);
}
return 0;
}
}
signed main(){return yspm::main();}
代码粘的是 \(Luogu\) 普通版的
原文：https://www.cnblogs.com/yspm/p/13485197.html