题解 | #Mate in 33#F IUPC

题意: n个数 有t时间 每个时间可以选择一个合法的数（每个数只能选择一次），连续k个时间最多选m个，问有多少种方法数

思路：想到区间k状态必须要2^k表示对于t 300 ，剩余只有10+的空间给n，思考每次可以选择前缀所有，故每次可以可能可以选多个 看前一状态，若前一个状态选到j个那这个可以选到num[i]-j个

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int n,t,m,k,dp[305][15][1<<11],num[305],a[15];
signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>t>>k>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        num[a[i]]++;
    }
    for(int i=1;i<=t;i++){
        num[i]=num[i]+num[i-1];
    }
    dp[0][0][0]=1;
    for(int i=1;i<=t;i++){
        for(int j=0;j<=num[i-1];j++){//此处已经做了多少题
            for(int s=0;s<(1LL<<k);s++){
                dp[i][j][s>>1]=(dp[i][j][s>>1]+dp[i-1][j][s])%mod;
                int nx = (s>>1)|(1<<(k-1));
                int res = __builtin_popcount(nx);
                //1.新状态1个数x<=m,x<=num[i]
                //2.j<num[i]
                if(res<=m&&res<=num[i]&&j<num[i]){
                    dp[i][j+1][nx]=(dp[i][j+1][nx]+dp[i-1][j][s]*(num[i]-j)%mod)%mod;
                }
            }
        }
    }
    int ans = 0;
    for(int i=0;i<(1LL<<k);i++){
        ans=(ans+dp[t][n][i])%mod;
    }
    cout<<ans<<'\n';
    return 0;
}