P4317 花神的數論題(數位dp模闆)

​​傳送門​​

這個很簡單啊…

回憶一下數位

d

p

dp

dp吧,以前學的太快了,都忘記了.

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 10000007;
int n,a[65],f[65][65][2];
int quick(int x,int n)
{
  int ans = 1;
  for( ; n ; n>>=1,x = x*x%mod)
    if( n&1 ) ans = ans*x%mod;
  return ans;
}
int dfs(int len,int limit,int yu)
{
  if( yu<0 || len<yu )  return 0;
  if( len==0 )  return ( yu==0 );
  if( f[len][yu][limit]!=-1 ) return f[len][yu][limit];
  int last = limit?a[len]:1, ans = 0;
  for(int i=0;i<=last;i++)
    ans += dfs(len-1,limit&&(i==a[len]),yu-(i==1) );
  return f[len][yu][limit] = ans;
}
void solve(int n)
{
  memset(a,0,sizeof(a));
  while( n )
  {
    a[++a[0]] = ( n&1 );
    n>>=1;
  }
}
signed main()
{
  memset( f,-1,sizeof(f) );
  cin >> n;
  solve(n);
  int ans = 1;
  for(int i=1;i<=63;i++)
    ans = ans*quick( i,dfs(a[0],1,i) )%mod ;
  cout << ans;
}