计数问题2 · ooliver

计数问题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; }`