[agc019e]Shuffle and Swap

전언

계수 수준이 안 된다.n^2에서 dp라는 모형을 못 가요.

제목의 뜻

귀찮아. 사이트 봐.

DP

x개의 공용 1과 y개의 비공용 1이 있다고 가정하십시오.도론으로 이해하다.마지막으로 반드시 Y개의 체인, 몇 개의 고리를 형성한다.그 중에서 체인의 모서리는 시퀀스에서 순서대로 있고 링은 임의로 됩니다.링은 일단 놔둬도 돼.dp[i, j]를 고려하면 현재 두 개의 i+j 서열이 만들어졌는데 i개의 공용 1과 j개의 비공용 1이 있고 번호를 구분하고 순서가 있으며 j개의 체인을 형성하는 방안수가 있다.dp[i, j]=dp[i-1, j]*i*j+dp[i, j-1]*j*j가 있습니다.뒤에 있는 것이 비교적 이해하기 쉽다. 바로 마지막에 비공용 한 쌍을 추가하는 것이다. j^2가지 방법이 있다.(전역 번호를 고려하지 않고 국부적인 문제만 고려하는 번호이기 때문에 현재 번호는 1~j, 하위 문제 번호는 1~j-1이다. 만약에 새로운 번호가 1~j-1을 선택한다면 원래 가지고 있던 번호를 j로 바꾸면 되는 것이 유일한 대응 방안이다.)앞에 그거는요?i 동리는 번호 방안 수이다. 체인에 순서가 있기 때문에 마지막에 이 체인이 특정한 체인의 끝부분에 딱 붙은 다음에 대응하는 비공용 1의 위치와 바꿀 수 있다고 생각하면 순서가 있다.마지막으로 얼마나 많은 공용1을 사용하여 체인의 형성에 참여했는지 열거하고 나머지는 마음대로 한다(공용1의 번호를 두 개의 집합으로 나누어 분배한 다음에 분배해야 할 위치가 있다는 것을 기억해라).복잡도는 짠 물고기의 제곱이다.

#include
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int maxn=10000+10,mo=998244353;
char s[maxn];
int f[maxn][maxn],fac[maxn],inv[maxn],bz[maxn];
int i,j,k,l,t,n,m,ans,x,y;
int qsm(int x,int y){
    if (!y) return 1;
    int t=qsm(x,y/2);
    t=(ll)t*t%mo;
    if (y%2) t=(ll)t*x%mo;
    return t;
}
int C(int n,int m){
    if (n<m||m<0) return 0;
    return (ll)fac[n]*inv[m]%mo*inv[n-m]%mo;
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    fo(i,1,n)
        if (s[i]=='1') y++,bz[i]++;
    scanf("%s",s+1);
    fo(i,1,n)
        if (s[i]=='1'&&bz[i]) x++;
    y-=x;
    fac[0]=1;
    fo(i,1,n) fac[i]=(ll)fac[i-1]*i%mo;
    inv[n]=qsm(fac[n],mo-2);
    fd(i,n-1,0) inv[i]=(ll)inv[i+1]*(i+1)%mo;
    f[0][0]=1;
    fo(i,1,y) f[0][i]=(ll)fac[i]*fac[i]%mo;
    fo(i,1,x)
        fo(j,1,y)
            f[i][j]=(ll)((ll)f[i-1][j]*i%mo+(ll)f[i][j-1]*j%mo)*j%mo;
    fo(i,0,x)
        (ans+=(ll)f[x-i][y]*qsm(fac[i],2)%mo*C(x,i)%mo*C(x+y,i)%mo)%=mo;
    (ans+=mo)%=mo;
    printf("%d
",ans);
}