一道好玩的组合数学的推公式题(绿名题, 1879C - Make it Alternating

1879C - Make it Alternating

先贴代码，看能不能理解

str a;
ll v[N];//装着01化为-1,1的数的数组
ll f[N];//装着预处理的组合数
void moon(){
  cin>>a;
  n=0;
  m=a.size();
  eps(i,0,m+10)v[i]=0; //eps()是一个陋习，define 定义的for循环
  for(auto p:a){
 v[++n]=(p=='1'?1:-1);
  }
  ll res=v[1],ans=0,nres=0;
  multiset<ll>s;//计数，比较方便
  eps(i,2,n)
  {
    while(res==v[i]){
        ans++;i++;//因为记住的不包括自己，所以后面是(p+1)
    }
    nres+=ans;
    if(ans>0)
    s.insert(ans);
    ans=0;
    res=v[i];
  }
    cout<<nres<<' ';
    res=1;
    for(auto p:s){
   //   if(p+1==nres)res=res%mod+1;
      res=res%mod*(p+1)%mod;  //所有可消除元素的连乘法，是一个乘法原理
    }
    res=res%mod*f[(nres)]%mod;//乘以取出来的数的阶乘，用来排位置
    cout<<res%mod<<endl;  
}
int main()
{
  icc(); 
  f[0]=1;
  eps(i,1,N)
f[i]=i%mod*f[i-1]%mod;
 cin>>_;
  while(_--)
  moon();
  return 0;
}

思想分析：

题目先要求的是最小操作次数

很容易贪心贡献的想到,常见的标 -1,1 （当然这个题没用

我们要交替，也就是连续不相等，那么连续相等的元素我们只会保留一个

所以用了一个multiset装着每一次去掉的数，最后输出res(和)

重点的是接下来的东西

我们怎么计算多少种操作方法，显然每个连续的数我们都可以取走(ans-1)个留下一个，也就是一个简单的乘法原理了，ans1 * ans2 * ans3 * ...吗？

100010 中间三个0是我们要清理的，显然是有顺序的，我们可以先拿左边两个，到处拿取，看看样例，它的拿取是有顺序的！

所以我们拿出元素后我们还得排序，分析拿取顺序，乘以(k)! (k是拿出元素的总和)

那么公式就出现了 ∏(1,s.size())len * (k)! (那个特殊字符是连乘)