[bzoj5510]唱跳rap和篮球

「爱情、让人受尽委屈。」 2021-11-17 15:34 185阅读 0赞

显然答案可以理解为有（不是仅有）0对情况\-1对情况\+2对情况……

考虑这个怎么计算，先计算这t对情况的位置，有c(n-3t,t)种情况（可以理解为将这4个点缩为1个，然后再从中选t个位置），然后相当于在剩下n-4t的位置上摆上4种东西，且每种东西有数量限制（ai-t个）。

这个东西dp一下即可，用f\[i\]\[j\]表示选了前i中东西，用了j个位置的方案数，则有转移$f\[i\]\[j\]=\\sum\\limits\_\{ai-t\\geq j-k\\geq 0,j\\geq 0\}f\[i-1\]\[k\]\\cdot c(n-4t-k,n-4t-j)$，这样的时间复杂度是$o(n^\{3\})$（然后卡卡常就过去了，仅20s），无法通过。

显然发现可以用fft优化，具体操作将c(i,j)以j为第一维预处理，则第一维就不与k有关了，而第二位与fft的形式很像，只要注意删掉不合法的f状态（置为0）即可，总时间复杂度为$o(n^\{2\}log\_\{n\})$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define mod 998244353
     4 int n,ans,a[11],c[1001][1001],f[11][1001];
     5 int main(){
     6     scanf("%d",&n);
     7     for(int i=0;i<4;i++)scanf("%d",&a[i]);
     8     for(int i=0;i<=n;i++)c[i][i]=c[i][0]=1;
     9     for(int i=2;i<=n;i++)
    10         for(int j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    11     for(int i=0;i<=n/4;i++){
    12         memset(f,0,sizeof(f));
    13         for(int j=0;j<=a[0]-i;j++)f[0][j]=c[n-4*i][j];
    14         for(int j=1;j<4;j++)
    15             for(int k=0;k<=n-4*i;k++)
    16                 for(int l=max(0,k-a[j]+i);l<=k;l++)
    17                     f[j][k]=(f[j][k]+1LL*f[j-1][l]*c[n-4*i-l][n-4*i-k])%mod;
    18         ans=(ans+1LL*(1-i%2*2+mod)*f[3][n-4*i]%mod*c[n-3*i][i])%mod;
    19     }
    20     printf("%d",ans);
    21 }

转载于:https://www.cnblogs.com/PYWBKTDA/p/11249996.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/cd8bb07406384c6fb12eb7a734cee482.png