Hexo
0%

P7822

Posted on Edited on

思路一

十分朴素的做法，设 fi,j,kf_{i,j,k} 表示第 ii 天学习第 jj 种算法 kk 天的方案数。那么对于 fi,j,1f_{i,j,1}，自然就可得：

fi,j,1=∑x=1(x≠j)m∑y=1axfi−1,x,yf_{i,j,1}=\sum_{x=1(x\ne j)}^{m}\sum_{y=1}^{a_x}f_{i-1,x,y}

对于 fi,j,kf_{i,j,k}（k>1k>1），可得：

fi,j,k=fi−1,j,k−1f_{i,j,k}=f_{i-1,j,k-1}

显然，ii 那一维可以省去，再加上前缀和优化，时间复杂度 O(n2m)O(n^{2}m)，空间复杂度 O(n2)O(n^{2})。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<vector>
using namespace std;
int a[7005];
int n,m;
int pre[7005];
const int mod=1000000007;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int maxn=0;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        maxn=max(maxn,a[i]);
    }
    vector<vector<int> > dp(m+5,vector<int>(maxn+5));
    for(int i=1;i<=m;i++){
        dp[i][1]=1;pre[i]=1;
    }
    int cnt=m;
    for(int i=2;i<=n;i++){
        int tmp=0;
        for(int j=1;j<=m;j++){
            int temp=0;
            for(int k=a[j];k>=1;k--){
                if(k==1){
                    dp[j][k]=(cnt-pre[j]+mod)%mod;
                }else{
                    dp[j][k]=(dp[j][k-1])%mod;
                }
                temp=(temp+dp[j][k])%mod;
                tmp=(tmp+dp[j][k])%mod;
            }
            pre[j]=temp;
        }
        cnt=tmp;
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=a[i];j++){
            ans=(ans+dp[i][j])%mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}

得分：50pts。

思路二

AC 代码，设 fi,jf_{i,j} 表示第 ii 天学习第 jj 种算法的方案数，接着，枚举学习的天数，得：

fi,j=∑x=i−aji−1∑y=1(y≠j)mfx,yf_{i,j}=\sum_{x=i-a_j}^{i-1}\sum_{y=1(y\ne j)}^{m}f_{x,y}

接着，我们进行优化，用 preipre_{i} 表示 ∑x=1i∑y=1mfx,y\sum_{x=1}^{i}\sum_{y=1}^{m}f_{x,y}，用 cntj,icnt_{j,i} 表示 ∑x=1ifx,j\sum_{x=1}^{i}f_{x,j}，边 dp 边计算这两个，于是可得 fi,j=(prei−1−prei−aj−1)−(cntj,i−1−cntj,i−aj−1)f_{i,j}=(pre_{i-1}-pre_{i-a_j-1})-(cnt_{j,i-1}-cnt_{j,i-a_j-1})。最后，我们可以把 ii 这一维压掉，注意，取模时减法要加上模数再取模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=7005;
int a[N];
int dp[N];
int pre[N];
int cnt[N][N];
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		dp[i]=1;
		cnt[i][1]=1;
	}
	pre[1]=m;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i>=a[j]+1){
				dp[j]=((pre[i-1]-pre[i-a[j]-1]+mod)%mod-(cnt[j][i-1]-cnt[j][i-a[j]-1]+mod)%mod+mod)%mod;
			}else{
				dp[j]=((pre[i-1])%mod-(cnt[j][i-1])%mod+mod+1)%mod;
			}
			cnt[j][i]=(cnt[j][i-1]+dp[j])%mod;
			pre[i]=(pre[i]+dp[j])%mod;
		}
		pre[i]=(pre[i]+pre[i-1])%mod;
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		ans=(ans+dp[i])%mod;
	}
	cout<<ans<<endl;
	return 0;
}