F题解 | #IUPC#

F题解 | #IUPC#

dp题，p = 1<<k, a[t]表示在t时刻可以提交的总题目数。dp[i][j][ij] 表示在时间i时解决j题，在[i-k+1,i]时间内的提交题目的二进制标志是ij。则有

1、ij1 = (ij<<1) % p;

2、 a[i+1] >0 , dp[i][0][0] =1;

3、dp[i+1][j][ij1] = dp[i+1][j][ij1] + dp[i][j][ij];

4、dp[i+1][j+1][ij1+1] = dp[i+1][j+1][ij1+1] + dp[i][j][ij] * (a[i+1]-j)。

时间复杂度O(t * n * 2^k)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <set>
#include <iostream>
typedef long long ll;
using namespace std;
int check(ll x){
    int y=0;
    while(x>0){
        y+=x%2;x=x/2;
    }
    return y;
}
void my_ans(){
    ll x1,x2,y1,y2,i,j,ij,q,n,m,l,r,k,t,x,y,Max = 31,ans=0, mod =1000000007;
    cin>>n>>t>>k>>m;
    int a[t+1];
    memset(a,0,sizeof(a));
    for(i=0;i<n;++i){
        cin>>x;++a[x];
    }
    for(i=1;i<=t;++i)a[i]+=a[i-1];
    y=1<<k;
    ll dp[t+1][n+1][y+1];
    for(i=0;i<=t;++i) for(j=0;j<=n;++j) for(ij=0;ij<=y;++ij) dp[i][j][ij] = 0;
    for(i=0;i<t;++i) {
        if (a[i+1]>0) dp[i][0][0] = 1;
        for(j=0;j<=n;++j) for(ij=0;ij<y;++ij) if (dp[i][j][ij]>0){
            x1 = (ij<<1) % y;
            if (a[i+1]>0 && a[i+1]>=j && check(x1)<=m) dp[i+1][j][x1] = (dp[i+1][j][x1] + dp[i][j][ij]) % mod;
            if (a[i+1] - j>0){
                x1 = x1 +1;
                if (check(x1)<=m)
                    dp[i+1][j+1][x1] = (dp[i+1][j+1][x1] + dp[i][j][ij]*(a[i+1]-j)) % mod;
            }
        }
    }
    
    for(ij=0;ij<y;++ij) ans = (ans+dp[t][n][ij]) % mod;
    cout<<ans<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    long long t=1,i,j;
    //scanf("%d",&t);
    //cin>>t;
    while(t>0){
        --t;my_ans();
    }
    return 0;
}
// 64 位输出请用 printf("%lld")