题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3662
之前写过这道题，结果被康神吐槽说代码写的挫。
的确，那时候想法太挫了。
题意：
给你三个数n，m，k。
问你存在多少个数列 a1,a2,...,ak，使得他们的和为n，他们的最小公倍数为m。
想法一：
因为 lcm(a1,a2,...,ak)=m，所以a1,a2,a3,...,ak都是m的约数。
因此预处理出来m的约数，记在w[i]里。
设计状态dp[i][j][k]代表有i个数的数列，和为j，最小公倍数为k的个数。
转移：dp[i][j][k] = sigma( dp[i-1][s][t] ) 其中 s+w[i] = j，lcm( t,w[i] ) = k
于是写成 dp[i][s+w[i]][lcm(t,w[i])] = sigma( dp[i-1][s][t] )
需要优化的部分较多，需要滚动数组，很容易TLE掉。
时间复杂度O( n*m*k*sqrt(n) )
于是被康神吐槽了。。
#include <bits/stdc++.h>
using namespace std; const int MOD = ;
int n,m,kk;
int a[],ptr;
int lcmn[][];
int dp[][][];
int ss[][][]; void getlcmn(){
for(int i=;i<;i++){
for(int j=;j<;j++){
lcmn[i][j] = i / __gcd(i,j) * j;
}
}
} int main(){
getlcmn();
while(scanf("%d%d%d",&n,&m,&kk)!=EOF){
ptr = ;
for(int i=;i*i<=m;i++){
if( m%i== ){
a[ptr++] = i;
if( i*i!=m ) a[ptr++] = m/i;
}
}
//for(int i=0;i<ptr;i++) printf("%d ",a[i]); puts("");
memset(dp,,sizeof(dp));
for(int i=;i<=min(m,n);i++) dp[][i][i] = ;
for(int i=;i<=kk;i++){
for(int j=;j<=n;j++){
for(int k=;k<=m;k++) dp[i&][j][k] = ;
for(int s=;s<ptr;s++){
if( j-a[s]>= ){
for(int t=;t<ptr;t++) {
if(lcmn[a[s]][a[t]]<=m) {
dp[i&][j][lcmn[a[s]][a[t]]] += dp[(i-)&][j-a[s]][a[t]];
dp[i&][j][lcmn[a[s]][a[t]]] %= MOD;
}
}
}
}
}
}
printf("%d\n",dp[kk&][n][m]);
}
return ;
}
想法一
当时听康神说所谓的正解，还真是没听懂，正巧昨天做了这道题：http://www.cnblogs.com/llkpersonal/p/4037686.html
于是今天早上就想起这个题目，也想了想“正解”。
由题意我们知道，m是a1,a2,...,ak的最小公倍数，因此，将a1,a2,a3,...,an质因数分解，取每一个质因数的最高次幂，然后乘起来就是m。
那么我们先对m进行质因数分解，然后划分状态，假设有sn个质因数，那么总状态数就是(1<<sn)-1个。
然后去分解m的因数，给每个因数定状态，如果说因数k的质因数的指数等于m的指数，那么就给该状态标1。记作v[i]
然后去跑完全背包。
定义状态dp[i][j][k][mask]代表数列有i个数，从前j个数里选，和为k，状态为mask。
状态转移：dp[i][j][k][mask] = sigma( dp[i-1][j-1][s][t] ) 其中s+w[i] = k , t|v[i]=mask
于是有dp[i][j][s+w[i]][t|v[i]] = sigma( dp[i-1][j-1][s][t] ) 对于每一个i，都相当于是一次独立的完全背包。
由于是完全背包，因此j维可以省掉。
于是化为
dp[j][s+w[i]][t|v[i]] = sigma( dp[j-1][s][t|v[i]] )
正向递推
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <iterator>
#include <vector>
using namespace std;
typedef long long LL; int n,m,k;
int p[],h[],w[],v[],ptr;
int dp[][][<<];
const int MOD = ; void prime_factor(int x){
for(int i=;i*i<=x;i++){
while( x%i== ){
p[i]++;
x /= i;
}
}
if( x!= ) p[x] = ;
} void handle(int x){
w[++ptr] = x;
for(int i=;i*i<=x;i++){
int t = ;
while( x%i== ){
t ++;
x /= i;
}
if( t&&t==p[i] ) v[ptr] |= (<<(h[i]-));
}
if( x!=&&p[x]== ) v[ptr] |= (<<(h[x]-));
} int main(){
while(scanf("%d%d%d",&n,&m,&k)!=EOF){
ptr = ;
memset(p,,sizeof(p));
memset(w,,sizeof(w));
memset(v,,sizeof(v));
memset(h,,sizeof(h));
prime_factor(m);
int sn = ;
for(int i=;i<;i++){
if( p[i] ) {
h[i] = ++sn;
}
}
for(int i=;i*i<=m;i++){
if( m%i== ) {
handle(i);
if( i*i!=m ) handle(m/i);
}
}
memset(dp,,sizeof(dp));
dp[][][] = ;
for(int j=;j<=k;j++){
for(int i=;i<=ptr;i++){
for(int k=;k<=n;k++){
for(int mask=;mask<(<<sn);mask++){
if( k+w[i]<=n&&(mask|v[i])<(<<sn) ){
dp[j][k+w[i]][mask|v[i]] = (dp[j][k+w[i]][mask|v[i]]+dp[j-][k][mask])%MOD;
}
}
}
}
}
printf("%d\n",dp[k][n][(<<sn)-]);
}
return ;
}
想法二