bzoj 2173 정수 lqp 분할 | dp | 법칙 찾기

이 문제의 예시 해석에 문제가 있는 것 같습니까?
f[1]=1 f[2]=1 f[3]=2
3=1+1+1 ->1*1*1=1
3=1+2->1*1=1
3=2+1->1*1=1
3=3->2=2
이 때문에 오랫동안 고민했는데...방정식 dp[i]=sigma(dp[j]*f[i-j])

    
    
    
    

     
     
     
     #include<cstdio>
    
    
    
    
    
    
    
    

     
     
     
     #include<cstdlib>
    
    
    
    
    
    
    
    

     
     
     
     #include<cstring>
    
    
    
    
    
    
    
    

     
     
     
     #include<algorithm>
    
    
    
    
    
    
    
    

     
     
     
     #include<cmath>
    
    
    
    
    
    
    
    

     
     
     
      
    
    
    
    
    
    
    
    

     
     
     
     #define md 1000000007
    
    
    
    
    
    
    
    

     
     
     
     #define ll long long
    
    
    
    
    
    
    
    

     
     
     
     #define inf (int) 1e9
    
    
    
    
    
    
    
    

     
     
     
     #define eps 1e-8
    
    
    
    
    
    
    
    

     
     
     
     #define N 1000010
    
    
    
    
    
    
    
    

     
     
     
     using 
     
     
     
     namespace 
     
     
     
     std;
    
    
    
    
    
    
    
    

     
     
     
     ll f[N];
    
    
    
    
    
    
    
    

     
     
     
     int 
     
     
     
     main()
    
    
    
    
    
    
    
    

     
     
     
     {
    
    
    
    
    
    
    
    

     
     
     
         
     
     
     
     int 
     
     
     
     n; 
    
    
    
    
    
    
    
    

     
     
     
         
     
     
     
     scanf
     
     
     
     (
     
     
     
     "%d"
     
     
     
     ,&n);
    
    
    
    
    
    
    
    

     
     
     
         
     
     
     
     f[0]=0; f[1]=1;
    
    
    
    
    
    
    
    

     
     
     
         
     
     
     
     for 
     
     
     
     (
     
     
     
     int 
     
     
     
     i=2;i<=n;i++) f[i]=(2*f[i-1]+f[i-2])%md;
    
    
    
    
    
    
    
    

     
     
     
         
     
     
     
     printf
     
     
     
     (
     
     
     
     "%lld
"
     
     
     
     ,f[n]);
    
    
    
    
    
    
    
    

     
     
     
         
     
     
     
     return 
     
     
     
     0;
    
    
    
    
    
    
    
    

     
     
     
     }