• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[HAOI 2011] Problem C

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

[题目链接]

         https://www.lydsy.com/JudgeOnline/problem.php?id=2302

[算法]

          记 s[i] 表示已经确定的m人中编号大于等于i的人数

          考虑dp , 记fi,j表示剩余(n - m)人中编号大于等于i的人已经确定j个人的编号的方案数,则:f[i][j] = sigma(f[i + 1][j - k] * C(j , k))

          时间复杂度 : O(N ^ 3)

[代码]

       

#include<bits/stdc++.h>
using namespace std;
#define N 310
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int n , m , M;
int cnt[N] , C[N][N] , dp[N][N];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
    T f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}

int main()
{
        
        int T;
        read(T);
        while (T--)
        {
                read(n); read(m); read(M);
                memset(cnt , 0 , sizeof(cnt));
                memset(C , 0 , sizeof(C));
                memset(dp , 0 , sizeof(dp));
                for (int i = 1; i <= m; ++i)
                {
                        int x , y;
                        read(x); read(y);
                        ++cnt[y];        
                }        
                for (int i = n; i >= 1; --i) cnt[i] += cnt[i + 1];
                bool tag = true;
                for (int i = 1; i <= n; ++i)
                {
                        if (cnt[i] > n - i + 1)
                                tag = false;
                }
                if (!tag)
                {
                        printf("NO\n");
                        continue;
                }
                for (int i = 0; i <= n; ++i)
                {
                        C[i][0] = 1;
                        for (int j = 1; j <= i; ++j)
                                C[i][j] = (1LL * C[i - 1][j] + 1LL * C[i - 1][j - 1]) % M;
                }
                dp[n + 1][0] = 1;
                for (int i = n; i >= 1; --i)
                {
                        for (int j = 0; j <= n - i + 1 - cnt[i]; ++j)
                        {
                                for (int k = 0; k <= j; ++k)
                                {
                                        dp[i][j] = (dp[i][j] + 1LL * dp[i + 1][j - k] % M * C[j][k] % M) % M;
                                }
                        }
                }
                printf("YES %d\n" , dp[1][n - m]);
        }
        
        return 0;
    
}

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[原创]C#序列化/反序列化对象.将对象写入文件,从文件读取对象. ...发布时间:2022-07-13
下一篇:
C#之理解接口的作用发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap