【模拟8.01】matrix（DP杂题，思维题）

很神的题，感谢lnc大佬的指点。

先设1-LL[i]统称左区间，RR[i]-m为右区间

用L[i]统计从1-i列，出现的左区间端点的前缀和，R[i]是右区间....

f[i][j]中j表示当前在第i列，右区间的左端点（RR[i]）到i存在的1的个数，总体表示当前方案数。

所以，我们分几种情况

两种是直接转移的

f[i+1][j]=f[i][j]表示i向右移动但j不变方案转移

f[i+1][j+1]=f[i][j]*(r[i+1]-j)表明又选了一个，当前新的1可以从r[i+1]（即右区间的个数）-j转移

一种是用排列.......

f[i][j]=f[i][j]*A(i-j-L[i-1],L[i]-L[i-1])

表示当前与上步操作中多出的区间是L[i]-L[i-1],这是必须填上1的

i-j-L[i-1]表示最多放的，又因为顺序不定，所以是排列......

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<string>

 4 #include<algorithm>

 5 #include<cmath>

 6 #include<vector>

 7 #include<map>

 8 #include<cstring>

 9 #define int long long

10 #define MAXN 3010

11 #define mod 998244353

12 using namespace std;

13 int jie[MAXN],ni[MAXN],ni_c[MAXN];

14 int f[MAXN][MAXN];

15 int A(int x,int y)

16 {

17     if(y==0)return 1;

18    // printf("x=%lld x-y=%lld %lld %lld\n",x,x-y,jie[x],ni_c[x-y]);

19     return jie[x]*ni_c[x-y]%mod;

20 }

21 int n,m;

22 int l[MAXN],r[MAXN];

23 signed main()

24 {

25     scanf("%lld%lld",&n,&m);

26     jie[0]=1; ni[0]=1; ni_c[0]=1;

27     jie[1]=1; ni[1]=1; ni_c[1]=1;

28     for(int i=2;i<=m;++i)

29     {

30         jie[i]=(jie[i-1]*i)%mod;

31         //printf("jie[%lld]=%lld\n",i,jie[i]);

32         ni[i]=(mod-mod/i)*ni[mod%i]%mod;

33         ni_c[i]=(ni_c[i-1]*ni[i])%mod;

34     }

35     for(int i=1;i<=n;++i)

36     {

37         int x,y;

38         scanf("%lld%lld",&x,&y);

39         l[x]++;r[y]++;

40     }

41     for(int i=1;i<=m;++i)

42     {

43         l[i]+=l[i-1];

44         r[i]+=r[i-1];

45     }

46     f[1][0]=1;

47     for(int i=1;i<=m;++i)

48     {

49         for(int j=0;j<=r[i];++j)

50         {

51              if(l[i]-l[i-1]>i-j-l[i-1])break;

52              f[i][j]=(f[i][j]*A(i-j-l[i-1],l[i]-l[i-1]))%mod;

53              f[i+1][j]+=f[i][j];

54              f[i+1][j+1]+=f[i][j]*(r[i+1]-j)%mod;

55              //printf("f[%lld][%lld]=%lld\n",i,j,f[i][j]);

56         }

57     }

58     printf("%lld\n",f[m][n]);

59 }

巴特西

【模拟8.01】matrix（DP杂题，思维题）

最新文章

热门文章