题目描述

　　有标有数字为\(1\)~\(9\)的卡片各\(a_1,a_2\cdots a_9\)张，还有标有乘号的卡片\(m\)张。从中取出\(n\)张按任意顺序排列，取出两个乘号相邻和乘法在边界上的非法式子，剩下的都是合法式子。求所有合法式子的方案的值的和。两张数字相同的卡片是不同的，两张乘号也是不同的。答案模\({10}^9+7\)

　　\(n\leq 1000,a_i\leq {10}^8,m\leq{10}^8\)

题解

　　\(n^\underline{m}=n\times(n-1)\times(n-2)\times\cdots\times(n-m+1)=A(n,m)\)即排列数

　　我们先枚举哪些位置有乘号

　　现在我们考虑把\(1,2,3,4\)四个数字填到\(\_\_\times\_\_\)这样子的算式中。假设\(m=2\)。把式子展开

\[ \begin{align} &~~~~~\overline{ab}\times\overline{cd}\\ &=(a\times10+b)\times(c\times10+d)\\ &=a\times c\times 10\times 10+a\times d\times 10\times 1+b\times c\times 1\times 10+b\times d\times 1\times 1\\ &=100ac+10ad+10bc+bd \end{align} \]

　　我们还有另外\(23\)个式子呢

\[ \overline{ab}\times\overline{dc}\\ \overline{ba}\times\overline{cd}\\ \overline{ba}\times\overline{dc}\\ \vdots \]

　　另外我们发现，\(ac\)和\(ad\)对答案的贡献都是相似的（因为除了乘积不同之外没有什么区别）我们考虑计算系数和出现次数

　　系数会有\(10\times 10,10\times 1,1\times 10,1\times 1\)，那么怎样计算出现次数呢？

　　先钦定这两个数字放的位置（就是系数），剩下那些空位总共有两个，还剩下两个数没填，方案数就是\(2^\underline{2}=2\)

　　最后还要乘上选择乘号的方案数\(2^\underline{1}=2\)

　　于是总的贡献就是

\[ (1\times 2+1\times 3+1\times 4+\cdots+4\times 3)\times(100+10+10+1)\times 2\times 2=??? \]

　　现在我们来考虑更复杂的情况

　　\(sum\)为所有数字卡片的个数和，\(g_{i,j}\)为前\(i\)个数字中选出\(j\)个代表数字的乘积的和，\(f_{i,j}\)为前\(i\)个空填了\(j\)个乘号的合法算式的系数和，\(s_i\)为这\(n\)个空中填入\(i\)个乘号的答案。

　　这里只讲一下\(f\)的推导

\[ \begin{align} &~~~~~\overline{ab}\times \overline{cd}\\ &=100ac+10ad+10bc+bd\\ &=10(10ac+bc)+(10a+b)d\\ \end{align} \]

　　那么\(10ac+bc\)的系数就是\(\overline{ab}\times c\)的系数（前一个位置的系数），\(10a+b\)的系数就是到上一个乘号前一个位置的系数。所以我们可以枚举上一个乘号是哪个位置，然后转移

\[ g_{i,j}=\sum_{k=0}^{a_i}g_{i-1,k-j}\times i^k\times \binom{j}{k}\times a_i^\underline{k}\\ f_{i,j}=f_{i-1,j}\times10+\sum_{k=1}^{i}f_{k,j-1}\\ s_i=g_{9,i+1}\times f_{n,i}\times {(sum-i-1)}^\underline{n-i-(i+1)}\times m^\underline{i} \]

　　排列组合什么的可以预处理或暴力算

　　时间复杂度：\(O(n^2)\)

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long ll;typedef pair
          
            pii;ll p=1000000007;int a[10];ll g[10][1010];ll f[1010][1010];ll s[1010][1010];ll aa[10][1010];ll pa[10][1010];ll cc[1010][1010];ll am[1010];ll geta(ll n,ll m){ ll s=1; int i; for(i=1;i<=m;i++) s=s*(n-i+1)%p; return s;}int main(){// freopen("c.in","r",stdin);// freopen("c.out","w",stdout); int n,m,sum=0; scanf("%d%d",&n,&m); int i; for(i=1;i<=9;i++) { scanf("%d",&a[i]); sum+=a[i]; } int j,k; for(i=1;i<=9;i++) { pa[i][0]=1; aa[i][0]=1; for(j=1;j<=n;j++) { pa[i][j]=pa[i][j-1]*i%p; aa[i][j]=aa[i][j-1]*(a[i]-j+1)%p; } } for(i=0;i<=n;i++) { cc[i][0]=1; for(j=1;j<=i;j++) cc[i][j]=(cc[i-1][j]+cc[i-1][j-1])%p; } g[0][0]=1; for(i=1;i<=9;i++) for(j=0;j<=n;j++) for(k=0;k<=j&&k<=a[i];k++) g[i][j]=(g[i][j]+g[i-1][j-k]*pa[i][k]%p*cc[j][k]%p*aa[i][k]%p)%p; for(i=1;i<=n;i++) { f[i][0]=(f[i-1][0]*10+1)%p; s[i][0]=(s[i-1][0]+f[i][0])%p; for(j=1;j<=n;j++) { f[i][j]=f[i-1][j]*10%p; if(i>2) f[i][j]=(f[i][j]+s[i-2][j-1])%p; s[i][j]=(f[i][j]+s[i-1][j])%p; } } am[0]=1; for(i=1;i<=n;i++) am[i]=am[i-1]*(m-i+1)%p; ll ans=0; for(i=0;i<=(n-1)/2&&i<=m;i++) ans=(ans+g[9][i+1]*f[n][i]%p*geta(sum-i-1,n-2*i-1)%p*am[i]%p)%p; printf("%lld\n",ans); return 0;}