洛谷P 4831 Scarlet loves WenHuaKe

問題面
に言及
m
やり方
n,mがいずれも2000以下である場合,直接何列かに1つの駒が置かれ,何列も駒が置かれていないことを記録し,行ごとに移行する.2000より大きい場合、n-m<=10 n-m<=10 n-m<=10 n-m<=10の性質を利用して、最後の列にいくつかの駒を置くことを考慮して、以下の3つの方案に分けて討論することができる:1.最後の列に2つの駒を置いて、この2つの駒が存在する2行の他の2つの駒a,b:a,bが同じ列にある場合、f(m,n)+=f(m−2,n−2)∗(m∗(m−1)/2)∗(n−1)f(m,n)+=f(m−2,n−2)*(m*(m−(m−1)/2)*(n−1)f(m,n)+=f(m−2,n−2,n−2)f(m(m,n)+=f(m−2,n−2)∗(m∗(m∗(m∗(m∗(m87(m−1)／2)∗(n−1)とは逆に,この2行のf(m,n)+=f(m−1,n−1)∗(m∗(m−1)/2)∗2 f(m,n)+=f(m−1,n−1)*(m*(m−1)/2)*2 f(m,n)+=f(m−1,n−1)∗(m−1)/2)最後の列に1つの駒しか置かないと、その駒が行っているもう1つの駒の所在列には最大1つの駒が置かれるので、その列に2つの駒が置かれている案数を減算すれば直接移行することができる.3.最後の列に駒を置かないとf(m,n)+=f(m,n−1)f(m,n)+=f(m,n−1)f(m,n)+=f(m,n)+=f(m,n−1)
コード#コード#

#include
#define ll long long
#define P pair
#define mp make_pair
#define fi first
#define se second
#define N 100100
#define M 998244353
using namespace std;

ll m,n,dp[N][15];

inline ll C2(ll u){return u*(u-1)/2%M;}
ll dfs(ll u,ll v);
inline ll calc(ll u,ll v){return C2(u)*((2*dfs(u-1,v)+(u+v-1)*dfs(u-2,v)%M)%M)%M;}
ll dfs(ll u,ll v)
{
    if(!u&&!v) return 1;
    if(u<0 || v<0) return 0;
    if(dp[u][v]!=-1) return dp[u][v];
    ll res=0;
    res+=calc(u,v);
    if(v)
    {
	res+=u*(u+v-1)%M*((dfs(u-1,v)+M-calc(u-1,v))%M)%M;
	res+=dfs(u,v-1);
    }
    return dp[u][v]=res%M;
}

namespace solve
{
    ll jl[2010][2010];
    ll dfs(ll u,ll v)
    {
	if(u*2+v+m*2==n*2) return 1;
	if(jl[u][v]!=-1) return jl[u][v];
	ll res=0;
	if(u>1) res+=dfs(u-2,v+2)*u*(u-1)/2%M;
	if(u&&v) res+=dfs(u-1,v)*u*v%M;
	if(v>1) res+=dfs(u,v-2)*v*(v-1)/2%M;
	return jl[u][v]=res%M;
    }
    void work()
    {
	memset(jl,-1,sizeof(jl));
	cout<<dfs(n,0);
    }
}

int main()
{
    memset(dp,-1,sizeof(dp));
    ll i,j;
    cin>>m>>n;
    if(m<=2000&&n<=2000)
    {
	solve::work();
	return 0;
    }
    cout<<dfs(m,n-m);
}