2023暑期多校10F

题目数据范围很小，可以考虑用状态压缩dp来写。

状态压缩dp的本质就是用二进制01表示不同的状态，然后删除或者压缩掉一些不必要的状态来对状态转移进行优化。 先把我们想要的dp数组写出来，dp[i][j][h]表示前i时刻过了j题的方案数，后面那个h是二进制状态，至于是什么状态我们应该先分析为题目再考虑h的状态。

回到这道题目上，题目要求的是方案总数，也就是说我们只需要考虑总的方案数，不需要考虑每个具体方案是怎么样的。

题目中的提交题目要求是在x[i]时间后都可以提交，也就是说在x[i]~t这段时间内提交第i题都是合法的。那换句话来说，对于t1时刻 对任意的i<t1只要都没交我们都可以在这个时刻提交（但只能交一题，且过了的不能重复提交）

题目的第二个限制是k时刻内只能叫t道题。一般情况下，我们的状态h存放的是每道题的过题状态。然而由于这个限制的存在，如果我们h存放每道题的过题状态，我们需要往前看k个时刻，显然这样写是非常麻烦的。

但是题目只要求方案总数，前面m时刻具体过哪些题，我们并不需要取关心，我们只需要关心前面k个时刻过了几题，这意味着我们的状态表示为前面k个状态过的题目，每到一个新的状态，我们就可以左移一位（记得与1<<k取and，保持一直是k位二进制）然后最右边那位考虑当前时刻过不过题，0为不过题，继承上一个状态，1为过题，看看当前时刻能过几题，设s[i]为i时刻能过的题目总数，那能过的题就是（s[i]-j)不需要管是哪一题，因为求的是方案总数。

#include<iostream>
#include<algorithm>
const int MOD = 1e9+7;
using namespace std;
int n,t,k,m;
int x[20];

long long dp[302][19][10000];//前i个时间过j题的状态是k
int s[301];
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> t >> k >> m;
    int val = 1;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i];
   
        val *=2;
    }
      int U = (1 << k) - 1;//k位二进制100000-1就是011111，方便给最高位取1表示过题
   // cout<<U<<endl;
     sort(x+1,x+1+n);
    int l = 1;
    for(int i = 1; i <= t; i++)
    {
        s[i] = s[i]+s[i-1];
        while(i == x[l] )
        {
            s[i]++;
            l++;
        }
       // cout<<i<<":"<<s[i]<<endl;
    }
    dp[0][0][0] = 1;
    for(int i = 0; i <= t; i ++)
    {
        for(int j = 0; j <= s[i] ; j++)
        {
    
            for(int h = 0 ; h <= (1<<k); h++)
            {
                int m1 = (h << 1) & U; //当前时刻不过题，最右边取0
                dp[i+1][j][m1] =(dp[i][j][h]+ dp[i+1][j][m1])% MOD;
            
                int m2 = (h << 1 | 1)& U;
                  if (__builtin_popcount(m2) > m) continue;//__builtin_popcount()用于计算一个 32 位无符号整数有多少个位为1
                dp[i+1][j+1][m2] = (dp[i+1][j+1][m2]+ dp[i][j][h]*(s[i]-j))% MOD;
            }
        }
    }
    long long res = 0;
    for(int i = 0; i <= (1 << k) ; i++)
    {
        res = (res + dp[t+1][n][i])% MOD;
    }
    cout<<res;
}