计数问题2
计数问题2
一些公式
吸收/提取恒等式：i⋅(i−1j−1)=j⋅(ji)i \cdot \binom{i-1}{j-1} = j \cdot \binom{j}{i}
上指标反转：(rk)=(−1)k(k−r−1k)\binom{r}{k} = (-1)^k \binom{k-r-1}{k}
范德蒙德卷积公式：∑k(rm+k)(sn−k)=(r+sm+n)\sum_k \binom{r}{m+k} \binom{s}{n-k} = \binom{r+s}{m+n}
上指标卷积公式：∑k=0n(ka)(n−kb)=(n+1a+b+1)\sum_{k=0}^n \binom{k}{a} \binom{n-k}{b} = \binom{n+1}{a+b+1}
奇怪的分组
板子，没啥好说的，代码：
#include
using namespace std;
#define int long long
const int N=1e6+5;
const int mod=1e9+7;
int m,n,x,c;
int inv[N],ninv[N];
int mi(int x,int y){
int res=1;
while(y){
if(y&1) (res*=x)%=mod;
y>>=1,(x*=x)%=mod;
}
return res;
}
void init(){
inv[0]=ninv[0]=1;
for(int i=1;i
`#include
using namespace std;
#define int long long
const int N=1e6+5;
const int mod=1e9+7;
int m,n,x,c;
int inv[N],ninv[N];
int mi(int x,int y){
int res=1;
while(y){
if(y&1) (res*=x)%=mod;
y>>=1,(x*=x)%=mod;
}
return res;
}
void init(){
inv[0]=ninv[0]=1;
for(int i=1;i
inv[i]=(i*inv[i-1])%mod;
ninv[i]=(mi(i,mod-2)*ninv[i-1])%mod;
}
}
int C(int x,int y){
return inv[x]*ninv[y]%mod*ninv[x-y]%mod;
}
signed main(){
init();
scanf("%lld%lld",&n,&m);
for(int i=1;iscanf("%lld",&x),c+=x;
printf("%lld",C(n-c-1,m-1));
return 0;
}`
P6057 [加油武汉] 七步洗手法 - 洛谷
考虑容斥，计算异色三元环，发现每个异色三元环会有两个异色角，统计所有异色角的个数，除以二，减掉就行了。
代码：
#include
using namespace std;
#define int long long
const int N=1e6+100;
int solve(int n){
return n*(n-1)*(n-2)/6;
}
long long n,m,ans,cnt;
int u[N];
signed main(){
cin>>n>>m;
ans=solve(n);
for(int i=1;i>x>>y;
u[x]++;
u[y]++;
}
for(int i=1;i
`#include
using namespace std;
#define int long long
const int N=1e6+100;
int solve(int n){
return n*(n-1)*(n-2)/6;
}
long long n,m,ans,cnt;
int u[N];
signed main(){
cin>>n>>m;
ans=solve(n);
for(int i=1;i
int x,y;
cin>>x>>y;
u[x]++;
u[y]++;
}
for(int i=1;i
cnt+=((u[i])*(n-u[i]-1));
}
cout2
}`
P4163 [SCOI2007] 排列
状压 DP，状态表示当前选择的方案，再加一维余数就行。
注意统计后要除以每个数的全排列方案数，去除重复计算的。
代码：
#include
using namespace std;
#define int long long
int T;
char s[15];
int n,d;
int dp[(1
`#include
using namespace std;
#define int long long
int T;
char s[15];
int n,d;
int dp[(111)][1005],a[15],cnt[10],pre[15];
void solve(){
memset(dp,0,sizeof dp);
memset(cnt,0,sizeof cnt);
dp[0][0]=1;
scanf("%s%d",s,&d);
n=strlen(s);
for(int i=0;ia[i+1]=s[i]-'0',cnt[a[i+1]]++;
for(int i=0;i1
for(int j=0;j
for(int k=0;k
if(!(i&(1dp[i|(110+a[k+1])%d]+=dp[i][j];
for(int i=0;i9;i++) dp[(11][0]/=pre[cnt[i]];
printf("%lld\n",dp[(11][0]);
}
signed main(){
pre[0]=1;
for(int i=1;i10;i++) pre[i]=pre[i-1]*i;
scanf("%d",&T);
while(T--) solve();
return 0;
}`
P14321 「ALFR Round 11」D Adjacent Lifting, Fewest Rounds
先把问题转化一下，将出现偶数次的奇数偶数之一设为 1，剩下一个设为 0；
那么问题转化为了 01 串操作问题。
不难发现，操作一没有贡献，操作二就是改变 01，最后答案应该是 01 串中的 1 两两就近匹配的之间的距离和。
所以，只有在两个 1 之间的 0 会对答案造成贡献，这个条件等价与这个 0 前面有奇数个 1，
设 0 有 aa 个，1 有 bb 个，枚举每个 0 和 奇数个 1，左右计算组合数，使用乘法原理相乘：
∑i=1a∑i=1b2(i+2j−22j−1)(n−i−2j+1b−2j+1)=∑i=1b2∑i=1a(i+2j−22j−1)(n−i−2j+1b−2j+1)=∑i=1b2(nb+1)=b2(nb+1)\begin{aligned}
&\sum^{a}{i=1} \sum^{\frac{b}{2}}{i=1}
\begin{pmatrix} i+2j-2 \ 2j-1 \end{pmatrix} \begin{pmatrix} n-i-2j+1 \ b-2j+1 \end{pmatrix}
\
=&\sum^{\frac{b}{2}}{i=1} \sum^{a}{i=1}
\begin{pmatrix} i+2j-2 \ 2j-1 \end{pmatrix} \begin{pmatrix} n-i-2j+1 \ b-2j+1 \end{pmatrix}
\
=&\sum^{\frac{b}{2}}_{i=1} \begin{pmatrix} n \ b+1 \end{pmatrix}
\ =&\frac{b}{2} \begin{pmatrix} n \ b+1 \end{pmatrix} \end{aligned}
在用加法原理加上 1 的贡献 b2(nb)\frac{b}{2} \begin{pmatrix} n \ b \end{pmatrix} ，
不要忘记奇偶是可以任意排列的，所以再乘上 a!b!a!b!。
代码：
#include
using namespace std;
#define int long long
const int N=1e7+5;
int T,mod;
int n;
int pre[N],inv[N];
int qpow(int x,int y){
int res=1;
while(y){
if(y&1) (res*=x)%=mod;
(x*=x)%=mod,y>>=1;
}
return res;
}
void init(){
pre[0]=1;
for(int i=1;i=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m){
return pre[n]*inv[m]%mod*inv[n-m]%mod;
}
void solve(){
scanf("%lld",&n);
int a=n/2,b=n-a;
if(b&1) swap(a,b);
printf("%lld\n",(((pre[a]*pre[b]%mod)*(b/2%mod)%mod)%mod*(C(n,b+1)+C(n,b))%mod)%mod);
}
signed main(){
scanf("%lld%lld",&T,&mod);
init();
while(T--) solve();
return 0;
}
`#include
using namespace std;
#define int long long
const int N=1e7+5;
int T,mod;
int n;
int pre[N],inv[N];
int qpow(int x,int y){
int res=1;
while(y){
if(y&1) (res*=x)%=mod;
(x*=x)%=mod,y>>=1;
}
return res;
}
void init(){
pre[0]=1;
for(int i=1;ipre[i]=pre[i-1]*i%mod;
inv[N-1]=qpow(pre[N-1],mod-2);
for(int i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m){
return pre[n]*inv[m]%mod*inv[n-m]%mod;
}
void solve(){
scanf("%lld",&n);
int a=n/2,b=n-a;
if(b&1) swap(a,b);
printf("%lld\n",(((pre[a]*pre[b]%mod)*(b/2%mod)%mod)%mod*(C(n,b+1)+C(n,b))%mod)%mod);
}
signed main(){
scanf("%lld%lld",&T,&mod);
init();
while(T--) solve();
return 0;
}`
P8594 「KDOI-02」一个仇的复
考虑枚举 i,ji,j 分别表示竖着的 1*2 方格的数量和分成的若干矩形的数量。
首先考虑放好 ii 个竖着的 1*2 方格后插空放置 jj 个空矩形，有 (i+1j)\begin{pmatrix} i+1 \ j \end{pmatrix} 种方案。
其次考虑每一段分多少长度，即 n−in-i 分给 jj，方案数 (n−i−1j−1)\begin{pmatrix} n-i-1 \ j-1 \end{pmatrix}。
最后考虑每段内的方案数，设第 ll 段分到 ala_l 的长度，需要使用 blb_l 个横着的矩形。
再次考虑插板法，把两行拼接成一行，相当于少了一个空且事先放好一个板子，方案数 (2al−2bl−2)\begin{pmatrix} 2a_l-2 \ b_l-2 \end{pmatrix}，
考虑所有段放在一起利用乘法原理，得到：
∑∑a=n−i∑b=k−j∏l=1j(2al−2bl−2)=(2(n−i)−2k−j−2)\begin{aligned} &\sum_{\substack{\sum a=n-i \ \sum b=k-j}} \prod_{l=1}^{j} \begin{pmatrix} 2a_l-2 \ b_l-2 \end{pmatrix} \ =&\begin{pmatrix} 2(n-i)-2 \k-j-2 \end{pmatrix} \end{aligned}
以上三个计算出来的利用乘法原理乘一起就行了，
代码：
#include
using namespace std;
typedef long long ll;
const int N=5e7+5;
const int mod=998244353;
int n,k;
ll ans;
int pre[N],inv[N];
ll qpow(ll x,int y){
ll res=1;
while(y){
if(y&1) (res*=x)%=mod;
(x*=x)%=mod,y>>=1;
}
return res;
}
void init(){
pre[0]=1;
for(int i=1;i=0;i--) inv[i]=(ll)inv[i+1]*(i+1)%mod;
}
ll C(ll x,ll y){
if(xx) return 0;
return (ll)pre[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main(){
init();
scanf("%d%d",&n,&k);
for(int i=0;i
`#include
using namespace std;
typedef long long ll;
const int N=5e7+5;
const int mod=998244353;
int n,k;
ll ans;
int pre[N],inv[N];
ll qpow(ll x,int y){
ll res=1;
while(y){
if(y&1) (res*=x)%=mod;
(x*=x)%=mod,y>>=1;
}
return res;
}
void init(){
pre[0]=1;
for(int i=1;ipre[i]=(ll)pre[i-1]*i%mod;
inv[N-1]=qpow(pre[N-1],mod-2);
for(int i=N-2;i>=0;i--) inv[i]=(ll)inv[i+1]*(i+1)%mod;
}
ll C(ll x,ll y){
if(x0||y0||y>x) return 0;
return (ll)pre[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main(){
init();
scanf("%d%d",&n,&k);
for(int i=0;i
for(int j=0;j
(ans+=(ll)C(2*n-2*i-2*j,k-i-2*j)*(ll)C(n-i-1,j-1)%mod*(ll)C(i+1,j)%mod)%=mod;
printf("%lld",ans+(n==k));
return 0;
}`