AtCoder Beginner Contest 132 F

F - Small Products

뭐라고 해야 되지?현재 자신의 수준 두 등급을 초과한 문제.첫 번째 레벨 숙련 dp dp dp 두 번째 레벨 숙련 블록
참고 대장부
인접 요소 곱하기≤N≤N≤N의 시퀀스 수를 요구합니다.N ≤ 1 e 9 N≤1e9 N≤1e9
서열수 고려 d p dp dp 분명: d p [i] [j] = ∑ x ∗ j≤ N d p [i - 1] [x] dp[i] [j]=\sum{x*j≤N}dp[i-1][x]dp[i][j]=∑x∗j≤Ndp[i-1][x] 그러나 분명히 2차원 크기는 요구에 부합되지 않는다.
이런 1e9 1e9 1e9은 일반적으로 블록을 나누거나 수학(수학은 보통 1e18 1e18 1e18)이라는 문제는 블록을 나누는 방법이다. 배울 만하다.
우리는 앞의 N\sqrt {N} 개를 직접 이용할 수 있고, 뒤의 부분은 N\sqrt {N} N 블록으로 나눌 수 있음을 고려했다.ii i 블록은 i∗k≤Ni*k≤Ni∗k≤N이 성립되고 ii i의 유일한 모든 kk를 나타냅니다.즉, 이곳의 kkk는 ii와만 조합할 수 있고, i+1i+1i+1과는 조합할 수 없다(뒤에 있는 식은 제거된 것을 발견할 수 있다), i-3-1i-1i-31과 조합된 부분은 앞에 이미 있다.
ii i 블록의 수량은 N i - N i + 1\rac {N} {i} -\rac {N} {i+1} iN - i+1N 수학적 증명은 할 수 없지만 예를 들면 이해하기 쉽다.예를 들어 첫 번째 블록은 111에 의해 유일하게 제거될 수 있다.N/1 = N N/1=N N/1=N은 고유한 경우를 고려하지 않고 N/2 N/2 N/2는 고유한 경우를 고려하지 않고 222에 의해 제거됩니다.유일하게 111로 나누어진 것은 분명히 N - N/2 N-N/2 N - N - N - N/2이다.이런 식으로 유추하다.
다음은 본씬입니다.첫 번째 부분은 N\sqrt {N} N 이내의 ii i 위치를 놓고 분류 토론을 고려합니다.S[i][j]S[i][j]S[i][j] 두 번째 부분은 ii의 위치를 제외한 것으로 이때 블록으로 처리해야 한다.B [ i ] [ j ] B[i][j] B[i][j]
정답은 ∑i = 1 N S [k] [i] + B [k] [i]\sum{i=1}^{\sqrt{N}}}S[k][i]+B[k][i]∑i=1NS[k][i]+B[i][i]S[i][j]S[i][j][j]는 어떻게 dpdpdpdp로 해결할 수 있을까. jj위를 작은 수로 두면 j-3-1j-1위를 작은 수와 큰 수로 둘 수 있다.작은 수는 상관없다. 큰 수는 [j, N] [j,\sqrt {N}] [j, N]의 블록에서만 사용할 수 있다. 작은 것은 수를 너무 크게 해서 N N N N을 초과할 수 있다. 그래서 S [i] [j] = ∑k = 1 N S [i-3] [k] + ∑k = j N B [i-3 1] [k] S [i] [j] =\sum{k=1}^{\sqrt{N}} S[i-1][k]+\sum_{k=j}^{\sqrt{N}}B[i-1][k]S[i][j]=∑k=1NS[i-4-1][k]+∑k=jNB[i-1][k]는 B[i][j]B[i][j][j]에 대해 앞자리는 소수만 넣을 수 있지만 여기 jj는 블록을 표시하기 때문에 블록의 수량을 곱해야 한다.그래서 B[i] [j] = (N i - N i + 1) ∑k = 1 j S [i - 1] [k] B[i] [j] = (\rac {N} {i} -\rac {N} {i+1}) *\sum{k=1}^{j}S[i-1][k]B[i][j]=(iN - i+1N) ∑k=1j S[i - 1][k]가 jj를 초과하는 것은 분명히 초과할 것이다.
이렇게 dp dp dp의 복잡도는 k∗N k*\sqrt {N}*\sqrt {N} k∗N 고려 추가의 작업으로 접두사와 간략화할 수 있다. 접두사와 k?N k*\sqrt {N} k?N을 실현할 수 있는 작은 디테일이 바로 N\sqrt {N} 블록과 방N\sqrt {N} 등가이다.하나를 취하면 된다.

#include
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define ll long long
using namespace std;

const ll mod = 1e9+7;

ll n;int k;
ll S[110][202000],B[110][202000];

int main(){
    cin>>n>>k;
    ll d=sqrt(n);
    ll ans=0;
    S[0][1]=1;
    FOR(i,1,k){
        FOR(j,1,d)S[i-1][j]=(S[i-1][j]+S[i-1][j-1])%mod;
        FOR(j,1,d)B[i-1][j]=(B[i-1][j]+B[i-1][j-1])%mod;
        FOR(j,1,d){
            S[i][j]=(S[i-1][d]+B[i-1][d]-B[i-1][j-1]+mod)%mod;
            B[i][j]=(n/j-n/(j+1))*S[i-1][j]%mod;
            if(j==n/j)B[i][j]=0;//SжагаСЫ
        }
    }
    FOR(i,1,d)ans=(ans+S[k][i]+B[k][i])%mod;
    cout<<ans<<endl;
}