[THUPC2021] 赌徒问题

Time_tears · 2021-06-13 10:50:06 · 题解

暴力枚举 s，然后 O(nm^2) 做完全背包，这样复杂度是 O(nm^3) 的。

注意到可以把 k 的约数的背包先拿出来做了，这样优化了之后我们在后面的背包之中就只用跑剩下的只是 ks 而不是 k 的约数的数，再加上一些卡常就跑的很快了，复杂度不是很会算，O(可过)。

#include<bits/stdc++.h>
#define N 2005
using namespace std;
const int mod=1e9+7;
int n,m,K,f[11][N],F[11][N],ans,*A,*B;
inline int Mod(int x) {return x<mod?x:x-mod;}
int main() {
    cin>>n>>m>>K,f[0][0]=1;
    for(int i=1; i<=m; ++i)if(K%i==0)
        for(int k=1; k<=n; ++k)for(int j=i; j<=m; ++j)f[k][j]=Mod(f[k][j]+f[k-1][j-i]);
    for(int s=1; s<=m; ++s) {
        memcpy(F,f,sizeof(f));
        for(int i=1; i<=s; ++i)if((1ll*K*s)%i==0&&K%i!=0)for(int k=1; k<=n; ++k){A=F[k]+i,B=F[k-1];for(int j=i; j<=s; ++j)(*A)=Mod((*A)+(*B)),++A,++B;}
        ans=Mod(ans+F[n][s]);
    } cout<<ans;
    return 0;
}