2023.5.29测试
T2~T4 全是计数题，败了
T2 网格
只会这一题
\(n\) 行 \(m\) 列的矩阵，一开始均为 \(0\)。有两种操作：将一行全部颠倒（\(0\rightarrow 1,1\rightarrow 0\)）或者将一列全部颠倒，每种操作分别进行 \(r\) 和 \(c\) 次，求最后最后矩阵有 \(s\) 个 \(1\) 的方案数
两种方案不同是指：存在某行或者某列，在两种方案中，操作的次数不同。
\(n,m,r,c\leq 1555\)
从对不同方案的定义，加上一点手推及猜想可知，两种操作的顺序并不会对最终的结果造成影响。也就是说，当我们知道哪行哪列进行过奇数次操作，我们就可以推出最后有多少个 \(1\)
我们枚举实际有用的操作次数 \(r',c'\space(\:0\leq r'\leq \min(n,r),0\leq c'\leq \min(c,m),(r-r')\mid2,(c-c')\mid 2\:)\)，那么简单推算可知最后矩阵就有 \(mr'+nc'-2r'c'\) 个 \(1\)，对于结果等于 \(s\) 的 \(r',c'\)，设 \(k=(r-r')/2\)，\(t=(c-c')/2\)，我们用点组合数学的知识和插板法就可以知道它的贡献为
预处理组合数，\(O(n^2)\) 轻松过掉
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1600,MOD=555555555;
int T,n,m,r,c,s;
LL f[2*N][2*N],ans;
void prework()
{
for(int i=0; i<=2*1555; i++)
f[i][0]=1;
for(int i=1; i<=2*1555; i++)
for(int j=1; j<=i; j++)
f[i][j]=(f[i-1][j]+f[i-1][j-1])%MOD;
}
int main()
{
prework();
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%d",&n,&m,&r,&c,&s);
ans=0;
for(int i=0; i<=min(r,n); i++)
{
if((r-i)%2!=0)
continue;
for(int j=0; j<=min(c,m); j++)
{
if((c-j)%2!=0)
continue;
if(n*j+m*i-2*i*j!=s)
continue;
int k=(r-i)/2,t=(c-j)/2;
LL tmp=1LL*f[n][i]*f[k+n-1][n-1]%MOD*f[m][j]%MOD*f[t+m-1][m-1]%MOD;
(ans+=tmp)%=MOD;
}
}
printf("%lld\n",ans);
}
return 0;
}
T3 双数组
求有多少对不同的数组 \((x,y)\)，满足以下所有条件：
- \(x,y\) 均有 \(n\) 个数
- \(1\leq x_i,y_i\leq s\quad(1\leq i\leq n)\)
- \(x_i\neq y_i\quad(1\leq i\leq n)\)
- \(x_i\neq x_j,y_i\neq y_j\quad(1\leq i<j\leq n)\)
\(1\leq n,s\leq 5\times 10^5\)
脑瘫了没想出来
考场上用 \(\rm dfs\) 发现对于任意满足条件的 \(x\)，它对应的满足条件的 \(y\) 的数量都相等，就考虑 \(\rm dp\) 计算出这个数量，可惜失败了。只能 \(\rm dfs\) 拿到 \(25\) 分
其实是道简单的容斥题
不考虑第 \(3\) 个条件的话 \(ans=A_s^n\times A_s^n\)，下面考虑容斥：
枚举 \(x_i=y_i\) 的数量 \(cnt\)，则它的贡献为 \(C_n^{cnt}\times A_s^{cnt}\times A_{s-cnt}^{n-cnt}\times A_{s-cnt}^{n-cnt}\) 。再根据奇加偶减原则容斥即可
#include<bits/stdc++.h>
using namespace std;
const int N=500010,MOD=1000000007;
int n,s,ans;
int fac[N],inv[N];
int ksm(int x,int y)
{
int res=1;
while(y)
{
if(y&1)
res=(1LL*res*x)%MOD;
x=(1LL*x*x)%MOD;
y>>=1;
}
return res;
}
void prework()
{
fac[0]=1; inv[0]=1;
for(int i=1; i<=s; i++)
{
fac[i]=(1LL*fac[i-1]*i)%MOD;
inv[i]=ksm(fac[i],MOD-2);
}
}
int A(int a,int b)
{
return 1LL*fac[a]*inv[a-b]%MOD;
}
int C(int a,int b)
{
if(b==0)
return 1;
return 1LL*fac[a]*inv[a-b]%MOD*inv[b]%MOD;
}
int main()
{
scanf("%d%d",&n,&s);
prework();
ans=1LL*A(s,n)*A(s,n)%MOD;
for(int i=1; i<=n; i++)
{
int a=C(n,i),b=A(s,i),c=A(s-i,n-i);
if(i&1)
ans=(ans-1LL*a*b%MOD*c%MOD*c%MOD+MOD)%MOD;
else
ans=(ans+1LL*a*b%MOD*c%MOD*c%MOD)%MOD;
}
printf("%d",ans);
return 0;
}
T4 字符串
给定一个原串 \(T\)，全是小写字母。\(n\) 次操作，每次往 \(T\) 中的任意位置插入任意一个小写字母，问最后的串有多少种可能。答案模 \(10^9+7\)
\(1\leq n,|T|\leq 10^6\)
只看了题根本没写
法一：
从结果开始考虑，设 \(len=|T|\)，问题转化为有一个长度为 \(len+n\) 的串，串中必须含有给定的字母并且按一定顺序排列，问最后有多少个不同的串？
显然 \(26^n\) 是错误的
有一种“套路”，我们考虑 \(T\) 中每个字母第一次出现的位置，假设 \(T=abc\)，那么 \(a\) 第一次出现的位置前都只有 \(25\) 种选法，\(a\) 和 \(b\) 之间的也有 \(25\) 种，\(b\) 和 \(c\) 之间的也是，但 \(c\) 之后的就有 \(26\) 种，所以我们不难发现，其实答案只和最后一个字符出现的位置有关
因此，我们枚举最后一个字符出现的位置 \(i\)，它的贡献则为
len=strlen(s);
n+=len;
prework(); //预处理阶乘、逆元，和上题一样
for(int i=len; i<=n; i++)
(ans+=1LL*ksm(25,i-len)*ksm(26,n-i)%MOD*C(i-1,len-1)%MOD)%=MOD;
printf("%d",ans);
法二：
大佬hpz倾情提供
其实考场上不一定想得出套路，但一定有能力爆搜。hpz通过爆搜发现答案和 \(T\) 长啥样无关，重要的是 \(T\) 的长度。所以直接令 \(T=aaa\dots\)，那么枚举 \(a\) 出现的次数 \(i\:(len\leq i\leq n+len)\)，贡献则为
for(int i=len; i<=n; i++)
(ans+=1LL*C(n,i)*ksm(25,n-i)%MOD)%=MOD;
其实还有mzm大佬的 \(\rm dp\)，但是比较抽象
T5 赠送笔记本
有 \(n\) 个宿舍，每个宿舍 \(4\) 个人，第 \(i\) 个宿舍有 \(a_i\) 个人有笔记本。现在每个人将笔记本赠送给他人，每个人最多接收 \(1\) 本，求有多少种赠送方案，答案模 \(1234567891\)
\(1\leq n\leq 47\)，\(0\leq a_i\leq 4\)
又是插入 \(\rm dp\)，又不会
本题的赠送方案涉及往前也有往后，所以用插入 \(\rm dp\) 的思想，我们对于第 \(i\) 个宿舍只考虑将自己的往前送和接收前面的，不考虑往后送和接收后面的，这部分在后面的阶段会考虑到。设 \(f[i][j]\) 表示考虑到第 \(i\) 个宿舍，还剩下 \(j\) 本笔记本没送。
首先我们考虑接收前面的。设 \(k\:(0\leq k\leq 4)\) 表示接收前面 \(k\) 本，那么贡献为 \(A_j^k\times C_4^k\)
再考虑往前送。设 \(t\:(0\leq t\leq a_i)\) 表示往前送 \(t\) 本，这时我们需要计算出前面有多少人还没收到笔记本，显然这个数量 \(s=4\times(i-1)-(a_1+\cdots+a_{i-1}-j)\)，贡献为 \(A_s^t\times C_{a_i}^t\)
综上，得出状态转移方程：
时间复杂度 \(O(n^2\times 4^3)\)
prework();
int sum=0;
f[0][0]=1;
for(int i=1; i<=n; i++)
{
for(int j=0; j<=sum; j++)
{
for(int k=0; k<=4; k++)
{
for(int t=0; t<=a[i]; t++)
{
int s=4*(i-1)-(sum-j);
LL x=A(j,k)*C(4,k)%MOD,y=C(a[i],t)*A(s,t);
(f[i][j-k+(a[i]-t)]+=f[i-1][j]*x%MOD*y%MOD)%=MOD;
}
}
}
sum+=a[i];
}
printf("%lld",f[n][0]);
\(100+100+25+0+0=225\)，\(\rm rk 10\)