Codeforces 1546 D. AquaMoon and Chess —— 组合数学,一点点想法

This way

题意:

给你一个01串s,你每次可以做一个操作如果s[i]=1:
1.如果i+2<=n且s[i+2]=0且s[i+1]=1,那么可以将s[i]的1移到s[i+2]
2.如果i-1>=1且s[i-2]=0且s[i-1]=1,那么可以将s[i]的1移到s[i-2]
问你经过若干次操作之后串s有多少种可能性。

题解:

可以发现1个连续的1不能动,2个连续的1可以乱移,3个连续的1会有一个被留下来,四个连续的1又可以乱移。那么有一个规律,偶数个连续的1就可以一起或者分开乱跑。那么该怎么计算有多少种情况。
可以将字符串看成这种形式:11111…11000…0100…0100…001000…
那么前面连续的1如果是偶数的,它们两两为一组可以到处跑,如果是奇数的,第一个1不能动。于是第一个1存不存在都没有意义,就可以将其当成偶数个1.然后可以发现如果单单前面连续的1中最后两个1一起移动的话,它们遇到了单个的1之后就被分开来,然后后面两个1又可以向后跑,举个例子:
11111100010010
将位置5,6的1往后移到第一个单独的1的位置时,它是长这样的:
11110001110010,然后往后移一格:
11110001011010
那么可以发现,前面三个0依旧在,后面的相对位置也没变,也就是说两个1的移动不会对这个字符串的其它元素的相对位置造成影响。并且可以发现,单独的1是否存在对于字符串也不会有任何影响。那么上面的字符串可以看成:
111111000000
到现在我们可以知道答案只和连续的偶数1和零的个数会有影响。
那么我们需要将两个相邻1看成一个整体进行移动,于是上面这个字符串也就可以看成:
三个1和六个0有多少种组合方式。答案也就呼之欲出了:假设有n个11,m个0,他们的组合情况数有 C n + m n C_{n+m}^n Cn+mn​种。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const int N=1e5+5;
ll fac[N],inv[N];
ll qpow(ll a,ll b){ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
char s[N];
int main()
{
    fac[0]=1;
    for(int i=1;i<N;i++)
        fac[i]=fac[i-1]*i%mod;
    inv[N-1]=qpow(fac[N-1],mod-2);
    for(int i=N-2;~i;i--)
        inv[i]=inv[i+1]*(i+1)%mod;
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d%s",&n,s);
        int one=0,zero=0,sum=0;
        for(int i=0;i<n;i++){
            if(s[i]=='0')zero++,one+=sum/2,sum=0;
            else sum++;
        }
        one+=sum/2;
        printf("%lld\n",fac[one+zero]*inv[one]%mod*inv[zero]%mod);
    }
    return 0;
}
上一篇:一和零


下一篇:【Linux】零拷贝技术(Zero Copy)