保存されている過去のバージョンの一覧

2014年04月07日06時20分45秒
2014年04月07日04時05分55秒

Codeforces Round #240 DIV1 B問題/DIV2 D問題 - Mashmokh and ACM

Source

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回ぐらいしか増加しないので，何回増加するかを全部試して，増加する場所のパターン数をコンビネーションを使って求めると，計算量がだいぶ減る）

C++のスパゲッティなコード

#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月17日04時36分21秒
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)

ログイン：