传送门
C
题意：
有一堆题目,从中选出$k$个难度不同的题目，求方案数。
思路：
数据范围过大显然需要离散化，不难得出DP的维度跟题目的编号和已经选择的题目有关，设$dp[i][j]$为前$i$个题目中选出了$j$个题目，不难得$dp[i][j]=dp[i-1][j-1]*val[i]+dp[i-1][j]$,意思是对于当前题目我要是必选它，那么方案数就是从前$i-1$（指难度）个题目中已经选出了$j-1$再选当前第$i$个所以乘上个$val[i]$，而加上一个$dp[i-1][j]$则是不选当前位，前$i-1$已经凑够了$j$题。
code：
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
48
49
50
|
using namespace std;
#define ll long long
ll (){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
const int N=1007;
const ll p=998244353;
ll n,k,cnt[N],tot,a[N];
ll ans=1;
vector <ll> v;
int getid(ll x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
ll dp[N][N];
int main(){
n=input(),k=input();
for(int i=1;i<=n;i++){
a[i]=input();
v.push_back(a[i]);
}
sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=n;i++){
cnt[getid(a[i])]++;
}
tot=v.size();
for(int i=0;i<=N;i++) dp[i][0]=1;
for(int i=1;i<=tot;i++){
for(int j=1;j<=k;j++){
dp[i][j]=(dp[i-1][j-1]*cnt[i])%p+dp[i-1][j];
dp[i][j]%=p;
}
}
printf("%lldn",dp[tot][k]);
}
|
D
题意：
求$[1,2^b-1]$内是k的倍数的数，二进制下数位为1位的个数。
思路：
我们不妨设$dp[i][j]$为在$[1,2^i]$中余数为$j$的数，二进制下数位为1位的个数。依据转移的思路我们一直填充高位，相当于在数的左边添加$0/1$,依据直觉，当我们在数的左边添加1的时候，对于$dp[i][j]$相当于添加了$dp[i-1][j]$个$1$，所以有第一个式子$dp[i][j]=dp[i][j]+dp[i-1][j]$，而添加$1$的时候，由于数值发生了改变于是模数也随之发生了改变，相当于在添加了$dp[i-1][j]$还增加了$[1,2^{i-1}]$之间膜$k$的等于$j$的数的个数个$1$,我们设$f[i][j]$为$[1,2^i]$之间膜$k$的等于$j$的数的个数，所以可以列第二个式子$dp[i][(j+2^i)%k]+=dp[i-1][j]+f[i-1][j]$.。同时通过DP,参考$dp[i][j]$数组的维护形式，我们也能很好的维护$f[i][j]$,因此我们可以很简单的得到：
code：
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
|
using namespace std;
#define ll long long
ll (){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
int k,b;
ll dp[200][1007],f[200][1007];
const ll mod=1e9+9;
int main(){
k=input(),b=input();
f[0][0]=1;
ll pw=1;
for(int i=1;i<=b;i++){
for(int j=0;j<k;j++){
f[i][j]+=f[i-1][j];
f[i][(j+pw)%k]+=f[i-1][j];
dp[i][j]+=dp[i-1][j];
dp[i][(j+pw)%k]+=dp[i-1][j]+f[i-1][j];
}
pw=(pw*2)%k;
for(int j=0;j<k;j++) f[i][j]%=mod,dp[i][j]%=mod;
}
printf("%lldn",dp[b][0]);
}
|
近期评论