Codeforces Round #240 DIV1 B問題 (1000pt)
Codeforces Round #240 DIV2 D問題 (2000pt)
Problem description
要素数 $K$ で,$1$ 以上 $N$ 以下の整数からなる数列 $b_1, b_2, \ldots, b_K, \;\; 1 \leq b_k \leq N$ であって,任意の $k$ に対して $b_{k+1}$ が $b_k$ の倍数となっているものはいくつあるのかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.
状態を(現在まで見た要素数,最後に使った整数)でDPする.
配るDPをすると書きやすい.
状態遷移は,最後に使った整数の倍数にしか行かないので,時間計算量は $O(NK \log N)$ になる.
(高速化する方法として,高々12回ぐらいしか増加しないので,何回増加するかを全部試して,増加する場所のパターン数をコンビネーションを使って求めると,計算量がだいぶ減る)
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define M 1000000007
#define mygc(c) (c)=_getchar_nolock()
#define mypc(c) _putchar_nolock(c)
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
ll dp[2100][2100];
int main(){
int N, K;
int i, j, m;
reader(&N);
reader(&K);
rep(i,K+1) rep(j,N+1) dp[i][j] = 0;
rep(j,N+1) dp[1][j]++;
REP(i,1,K) REP(j,1,N+1){
dp[i][j] %= M;
for(m=j;m<=N;m+=j) dp[i+1][m] += dp[i][j];
}
m = 0;
REP(j,1,N+1) m = (m + dp[K][j]) % M;
writer(m, '\n');
return 0;
}
Current time: 2024年04月20日14時48分51秒
Last modified: 2014年04月07日06時20分45秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF240 CF_Div1_B CF_Div2_D
トップページに戻る
Logged in as: unknown user (not login)