[TJOI2019 D1T3 : 唱,跳,rap,篮球题解]
zyc2003
·
·
题解
题目链接
可能更好的阅读体验
题解简述
对于 20 分和 100 分的做法进行了讲解 , 不需要多项式知识 . 该做法的复杂度是 \mathcal O(\dfrac{n^3}{12}) .
前置知识
不需要 : NTT
不需要 : 生成函数
需要 : 二项式定理基础
部分分拿法
下面我们用 $a_1,a_2,a_3,a_4$ 分别代表喜欢唱 , 喜欢跳 , 喜欢rap , 喜欢篮球的学生 , 用 $num_1,num_2,num_3,num_4$ 代表对他们的人数限制 .
我们发现 , 对于部分分 : $n=num_1=num_2=num_3=num_4\leq 500$ , 也就是说 , 实际上每一类学生的放置没有**数量上的限制** . 那么 , 如果考虑放置 $n$ 个学生的总方案数 , 且不考虑是否**合法** , 就有 $4^n$ 种方案 .
题目要求不能存在 $a_1,a_2,a_3,a_4$ 连在一起的情况出现 . 正难则反 , 我们只要求出所有**不合法**的方案总数 , 然后用 $4^n$ 减去它即可 .
所以 , 设 $f_i$ 表示已经决定了前 $i$ 个位置上的学生 , 有 $f_i$ 种方案是**不合法**的 . 首先初始状态 $f_1=f_2=f_3=0$ . 考虑 $3<i\leq n$ , 不合法情况分两种 , 第一种是 $i-3,i-2,i-1,i$ 这四个位置上恰好是 $a_1,a_2,a_3,a_4$ , 前面是否合法无所谓 ; 第二种就是 $i-3,i-2,i-1,i$ 是合法的 , 但是前面存在一些位置不合法 .
第一种情况的总数是 $4^{i-4}$ , 意味着 $1\sim i-4$ 个位置可以随便选择 , 但是 $i-3,i-2,i-1,i$ 这四个位置要放上 $a_1,a_2,a_3,a_4$ ; 所以是 $4^{i-4}*1$ 种情况 ; 第二种情况 , 就是 $4*f_{i-1}-f_{i-4}$ . 这个式子意味着第 $i$ 个位置随便放上 $4$ 种学生的任意一种 , 有 $4*f_{i-1}$ 种情况 , 而后再扣除 $i-3,i-2,i-1,i$ 为不合法的情况 , 即 $-f_{i-4}$ . 所以有 :
$$f_i=4^{i-4}+4*f_{i-1}-f_{i-4}\ \ (3<i\leq n)$$
最后答案为 $4^n-f_n$ , 可以拿到 20pts 的好成绩 .
```cpp
typedef long long LL;
typedef unsigned int ui;
inline LL read() {
LL x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline char char_read() {
char ch=getchar();
while(!isalpha(ch))ch=getchar();
return ch;
}
inline void write(LL x) {
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
inline void writes(LL x) {write(x),putchar(' ');}
inline void Writes(LL x) {write(x),putchar('\n');}
#define N 1010
#define P 998244353
int n,ans;
int num[5];
int f[N];
int Qpow(int x,int p) {int ans=1;for(;p;p>>=1,x=1ll*x*x%P)if(p&1)ans=1ll*ans*x%P;return ans;}
int main() {
n=read();
for(int i=1;i<=4;++i)
num[i]=read();
for(int i=4;i<=n;++i)
f[i]=(1ll*Qpow(4,i-4)+4ll*f[i-1]%P-1ll*f[i-4])%P;
Writes((((1ll*Qpow(4,n)-1ll*f[n])%P)+P)%P);
return 0;
}
```
### 满分做法
现在我们的每种学生的人数有了限制 , 那该怎么做呢 ?
首先考虑所有方案的总数 . 我们可以考虑先放第 $4$ 种学生 , 再放第 $3$ 种 , 再放第 $2$ 种 , 最后剩下的放第 $1$ 种学生 . 这样可以自然地想到动规式子 : $f_{i,k}$ 表示当前局面剩下 $i$ 个人 , 放好了**前** $k$ 种学生的总方案数 . 那么 :
$$f_{i,k}=\sum_{j=0}^{\min(num_k,i)}C_{i}^{j}*f_{i-j,k-1} \ \ (1<k\leq 4)$$
这个式子表示 , 我在 $i$ 个位置中选择 $j$ 个位置放置第 $k$ 种学生 , 剩下的 $i-j$ 个位置放置前 $k-1$ 种学生 .
下面考虑边界条件 .
当 $k=1$ 时 , $f_{i,1}=[i \leq num_1]$ . 如果 $i > num_1$ , 那么学生人数不足 , 根本放不上去 .
当 $i=0$ 时 , $f_{0,k}=1$ .
推荐使用**记忆化搜索** , 比较方便实现 . 注意 , 这样的复杂度是 $\mathcal O(n^2)$ .
and then ? 我们还是考虑找出所有不合法的方案 . 不过这一次有了限制 , 不能那么显然地 dp 了 ; 那么 , 设 :
$$\mathrm{mmin}=\min(n/4,num_1,num_2,num_3,num_4)$$
考虑 $n$ 个位置上有 $1,2,\dots,\mathrm{mmin}$ 个不合法的连续段 $a_1,a_2,a_3,a_4$ . 对于有 $k$ 个不合法段的情况 , 我们运用高中学过的**整体法**(没学过不要紧) , 实际上就是在 $n-3k$ 个位置中 , 选出 $k$ 个位置进行拓展成 $a_1,a_2,a_3,a_4$ 的方案数 , 也就是 $C_{n-3k}^{k}$ . 那么剩下的位置有 $n-4k$ 个 , 随意放置的方案数就是 $f_{n-4k,4}$ . 不过注意 , 每种颜色的限制应该变为 $num_i-k,i=1,2,3,4$ .
那么 , 求出来的 $C_{n-3k}^k*f_{n-4k,4}$ 代表了什么呢 ? 代表着局面上**至少**有 $k$ 个不连续段的方案数 , 但是该方案数对一些情况**算重了** . 具体地说 , 局面上有 $k$ 个不连续段的方案数被计算了 $C_k^k$ 次 , 有 $k+1$ 个不连续段的方案数被计算了 $C_{k+1}^k$ 次 , ... , 有 $\rm mmin$ 个不连续段的方案数被计算了 $C_{\mathrm{mmin}}^k$ 次 ; 那这怎么办呢 ?
这个时候 , 就需要我们的**容斥大法**了 ! 有一个需要知道的结论 :
$$\sum_{i=1}^m (-1)^{i-1}*C_{m}^{i}=1$$
证明也不难 (虽然我一时间没想出来 , 还是机房的大佬 JasonL 告诉我的) . 考虑二项式展开 :
$$\begin{aligned}
(1-1)^m &= \sum_{i=0}^m(-1)^i*C_{m}^i
\\
0&= 1+\sum_{i=1}^m(-1)^i*C_{m}^i
\\
1&= \sum_{i=1}^m(-1)^{i-1}*C_{m}^i
\end{aligned}$$
就得到了证明 . 这个容斥应当熟知 .
设 $g_k=C_{n-3k}^k*f_{n-4k,4}$ . 那么 , 我们最终**不合法的方案总数**为 :
$$\sum_{k=1}^{\mathrm{mmin}}(-1)^{k-1}g_k$$
比如 , 有 $3$ 个不连续段的情况 , 在 $g_1$ 中被算了 $C_3^1$ 次 , 在 $g_2$ 中被算了 $C_3^2$ 次 , 在 $g_3$ 中被算了 $C_3^3$ 次 . 而根据容斥 , $C_3^1-C_3^2+C_3^3=1$ , 最终只被算了一次 .
那么 , 最终的答案是 :
$$f_{n,4}-\sum_{k=1}^{\mathrm{mmin}}(-1)^{k-1}g_k$$
简单化简得 :
$$\sum_{k=0}^{\mathrm{mmin}}(-1)^{k}g_k$$
求出来 ! 就是最终答案 .
...等等 , 时间复杂度呢 ? 每次计算 $f_{n-4k,4}$ 的复杂度为 $\mathcal O(n^2)$ , 那么总复杂度为 $\mathcal O(n^3)$ 的 , 怎么通过本题呢 ? 实际验证 , 四个数字全为 $1000$ 的情况 , 在 $500\sim 1000$ 毫秒内可以轻松跑过 .
经分析 , 时间复杂度为 $\mathcal O(\frac{n^3}{\omega}) , \omega=12$ , 所以最坏情况下为 $\dfrac{1000^3}{12}\approx 8.3\times 10^7$ , 是能跑得过的 !
### 时间复杂度分析
考虑计算 $f_{n,k}$ , 对于 $k=4$ , 我们只用计算 $f_{n,4}$ 这一个值 , 而不用计算 $n-1,n-2,\dots$ ; 对于 $k=1$ , 这是边界条件 ; 那么只用考虑 $k=2,3$ , $f_{n,3}=f_{n-1,2}+f_{n-2,2}+\dots+f_{0,2}$ , 所以计算次数为 $2*(n+n-1+\dots+1)\approx n^2$ .
那么 , 总计算次数约为 $n^2+(n-4*1)^2+(n-4*2)^2+\dots+0^2$ , 也就是 :
$$\begin{aligned}
\sum_{k=0}^{\frac{n}{4}}(n-4k)^2 &=\sum_{k=0}^{\frac{n}{4}}\big ((4k)^2\big )\\
&=16\sum_{k=0}^{\frac{n}{4}} k^2 \\
&\approx 16\times \frac16 \times \frac{n}{4} \times \frac{n}{4} \times \frac{n}{2}\\
&=\frac{n^3}{12}
\end{aligned}$$
所以 , 本算法对于 $1000$ 规模的数据还是没问题的 , 但是再大一些 , 就完全不行了 QAQ ...那样的话 NTT 或者其他的 $\mathcal O(n^2)$ 做法值得选择 .
```cpp
typedef long long LL;
typedef unsigned int ui;
inline LL read() {
LL x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline char char_read() {
char ch=getchar();
while(!isalpha(ch))ch=getchar();
return ch;
}
inline void write(LL x) {
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
inline void writes(LL x) {write(x),putchar(' ');}
inline void Writes(LL x) {write(x),putchar('\n');}
#define N 1010
#define P 998244353
int n,ans;
int num[5];
int f[N][N];
int vis[N][N],cnt;
int C[N][N];
int dp(int x,int col) {
if(x < 0) return 0;
if(vis[x][col] == cnt)
return f[x][col];
vis[x][col]=cnt,f[x][col]=0;
if(x == 0)
f[x][col]=1;
else if(col == 1)
f[x][col] = (x > num[col] ? 0 : 1);
else {
for(int i=0;i<=min(num[col],x);++i)
f[x][col]=(1ll*f[x][col]+1ll*C[x][i]*dp(x-i,col-1)%P)%P;
}
return f[x][col];
}
void treat() {
for(int i=0;i<=n;++i)
C[i][0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
C[i][j]=(1ll*C[i-1][j-1]+1ll*C[i-1][j])%P;
}
int fac(int x) {
return (x&1) ? -1 : 1;//容斥系数
}
int main() {
n=read();
for(int i=1;i<=4;++i)
num[i]=read();
treat();
int mmin=n/4;
for(int i=1;i<=4;++i)
mmin=min(mmin,num[i]);
for(int i=0;i<=mmin;++i) {
cnt++;
ans=((1ll*ans+1ll*fac(i)*C[n-3*i][i]*dp(n-4*i,4)%P)%P+P)%P;
for(int j=1;j<=4;++j)
num[j]--;
}
Writes(ans);
return 0;
}
```