https://codeforces.com/contest/1174/problem/E
dp
好题
*(if 满足条件)
满足条件 *1
不满足条件 *0
///这代码虽然写着方便，但是常数有点大
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=1e6+10; 15 16 /* 17 dp题 18 检查： 19 1.认真检查公式 20 2.认真检查代码 21 3.造一个规模适中的数据 22 手动推导 23 对应程序的结果 24 判断是否相同 25 */ 26 27 ///+1 20->21 2->3 28 ///0->-1 前面加一个辅助数组，这个数组里的所有元素数值为0 29 ///x1*y1+x2*y2+x3*y3+...x20*y20 有可能会超long long, 所以所有乘法运算后面都加%mod 30 ///1e18*k k<=9 31 int f[maxn][21][3],v[21][3]; 32 33 int main() 34 { 35 int n,two,three,i,j,k; 36 scanf("%d",&n); 37 two=log(n+eps)/log(2);///+eps 38 three=(1.0*n/(1<<two)>=1.5); 39 for (i=0;i<=two;i++) 40 for (j=0;j<=three;j++) 41 v[i][j]=n/((1<<i)*(j==0?1:3)); 42 43 f[1][two][0]=1; 44 if (three==1) 45 f[1][two-1][1]=1; 46 for (i=2;i<=n;i++) 47 for (j=0;j<=two;j++) 48 for (k=0;k<=three;k++) 49 ///乘1ll,最后强制转换long long 转 int 50 f[i][j][k]=( 1ll*f[i-1][j][k]*(v[j][k]-(i-1))*((v[j][k]-(i-1))>=0)%mod + 1ll*f[i-1][j+1][k]*(v[j][k]-v[j+1][k])*(j!=two)%mod + 1ll*f[i-1][j][k+1]*(v[j][k]-v[j][k+1])*(k!=three)%mod )%mod; 51 printf("%d",f[n][0][0]); 52 return 0; 53 }
推荐比如说这个xiongdi的代码
https://codeforces.com/contest/1174/submission/56391704
超内存的代码
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=1e6+10; 15 16 /* 17 dp题 18 检查： 19 1.认真检查公式 20 2.认真检查代码 21 3.造一个规模适中的数据 22 手动推导 23 对应程序的结果 24 判断是否相同 25 */ 26 27 ///+1 20->21 2->3 28 ///0->-1 前面加一个辅助数组，这个数组里的所有元素数值为0 29 ///x1*y1+x2*y2+x3*y3+...x20*y20 有可能会超long long, 所以所有乘法运算后面都加%mod 30 ///1e18*k k<=9 31 ll f[maxn][21][3],v[21][3]; 32 33 int main() 34 { 35 int n,two,three,i,j,k; 36 scanf("%d",&n); 37 two=log(n+eps)/log(2);///+eps 38 three=(1.0*n/(1<<two)>=1.5); 39 for (i=0;i<=two;i++) 40 for (j=0;j<=three;j++) 41 v[i][j]=n/((1<<i)*(j==0?1:3)); 42 43 f[1][two][0]=1; 44 if (three==1) 45 f[1][two-1][1]=1; 46 for (i=2;i<=n;i++) 47 for (j=0;j<=two;j++) 48 for (k=0;k<=three;k++) 49 f[i][j][k]=( f[i-1][j][k]*(v[j][k]-(i-1))*((v[j][k]-(i-1))>=0)%mod + f[i-1][j+1][k]*(v[j][k]-v[j+1][k])*(j!=two)%mod + f[i-1][j][k+1]*(v[j][k]-v[j][k+1])*(k!=three)%mod )%mod; 50 51 printf("%lld",f[n][0][0]); 52 return 0; 53 }