1 条题解

  • 0
    @ 2023-9-20 21:50:19
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    #include<cmath>
    #include<set>
    #include<queue>
    #define rep(i,a,n) for(int i = a;i <= n;i++)
    #define per(i,n,a) for(int i = n;i >= a;i--)
    #define enter putchar('\n')
    
    using namespace std;
    typedef long long ll;
    const int M = 10005;
    const ll INF = 1000000009;
    const int mod = 9397;
    
    int read()
    {
        int ans = 0,op = 1;
        char ch = getchar();
        while(ch < '0' || ch > '9')
        {
        if(ch == '-') op = -1;
        ch = getchar();
        }
        while(ch >= '0' && ch <= '9')
        {
        ans *= 10;
        ans += ch - '0';
        ch = getchar();
        }
        return ans * op;
    }
    
    int n,k,dp[105][105];
    
    bool judge(int x,int m)
    {
       int ta = min(x - 1,n - x + 1),tb = min(m - 1,n - m + 1),tc = min(m - x,n - m + x);
       return (ta == tb || tb == tc || ta == tc);
    }
    
    int dfs(int n,int k)
    {
       if(dp[n][k] != -1) return dp[n][k];
       if(n <= 2) return 0;
       int cur = 0;
       rep(x,2,n-1)
       {
          rep(j,0,k-judge(x,n)) cur += dfs(x,j) * dfs(n-x+1,k-j-judge(x,n)),cur %= mod;
       }
       return dp[n][k] = cur;
    }
    
    int main()
    {
       n = read(),k = read();
       memset(dp,-1,sizeof(dp));
       dp[2][0] = 1;
       printf("%d\n",dfs(n,k));
       return 0;
    }
    
    
    • 1

    信息

    ID
    1532
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者