今天的题还是比较水的。。涨自信？
第一题。。显而易见的dp：dp[i][j][k][l][m]:表示i位，j个1，k是否顶上界，l个前导零，是否仍在前导零上。转移方程比较复杂，详见代码。
第二题比较复杂，大意就是把[ai，bi] 作为区间，落在[1，N]上，互不重叠，长度互不相等。然后dp[j][k]表示在i位，选了k个，其和为j。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 long long dp[50][50][2][50][2]; 6 long long work(long long x) 7 { 8 long long top[200]; 9 memset(dp,0,sizeof(dp)); 10 memset(top,0,sizeof(top)); 11 long long i=1; 12 long long j=1; 13 if(x==0) return 0; 14 while(x/j) 15 { 16 i++; 17 j*=2; 18 } 19 if(i) 20 i--; 21 long long n=i; 22 while(x) 23 { 24 top[i]=x%2; 25 x/=2; 26 i--; 27 } 28 // for(int i=1;i<=n;i++) 29 // cout<<top[i]; 30 // cout<<endl<<endl; 31 dp[1][0][1][0][0]=1; 32 // for(int i=1;i<=n;i++) 33 // cout<<top[i]; 34 // cout<<endl; 35 for(i=1;i<=n;i++) 36 for(j=0;j<=n/2;j++) 37 for(int k=0;k<=n;k++) 38 { 39 dp[i+1][j][0][k+1][0]+=dp[i][j][0][k][0]; 40 dp[i+1][j+1][0][k][1]+=dp[i][j][0][k][0]; 41 if(top[i]==0) 42 dp[i+1][j][1][k+1][0]+=dp[i][j][1][k][0]; 43 else 44 { 45 dp[i+1][j][0][k+1][0]+=dp[i][j][1][k][0]; 46 dp[i+1][j+1][1][k][1]+=dp[i][j][1][k][0]; 47 } 48 for(long long l=0;l<=1;l++) 49 dp[i+1][j+l][0][k][1]+=dp[i][j][0][k][1]; 50 for(long long l=0;l<=top[i];l++) 51 dp[i+1][j+l][l==top[i]][k][1]+=dp[i][j][1][k][1]; 52 // cout<<dp[i][j][up]<<endl; 53 } 54 long long ans=0; 55 for(int k=0;k<=n;k++) 56 for(int i=1;i<=(n-k)/2;i++) 57 { 58 ans+=dp[n+1][i][0][k][1]+dp[n+1][i][1][k][1]; 59 } 60 61 // for(int j=1;j<=n+1;j++) 62 // for(int k=0;k<=n;k++) 63 // for(int i=1;i<=n;i++) 64 // cout<<dp[j][i][0][k][1]; 65 return ans; 66 } 67 void work() 68 { 69 freopen("testA.in","r",stdin); 70 freopen("testA.out","w",stdout); 71 long long L,R; 72 cin>>L>>R; 73 if(L==1) 74 cout<<work(R)<<endl; 75 else 76 cout<<work(R)-work(L-1)<<endl; 77 // cout<<work(R)<<" "<<work(L-1)<<endl; 78 } 79 int main() 80 { 81 work(); 82 return 0; 83 }
然后答案就是
，详见标程代码（我还没有写出来）。
1 #include <map> 2 #include <set> 3 #include <queue> 4 #include <stack> 5 #include <cctype> 6 #include <cstdio> 7 #include <string> 8 #include <vector> 9 #include <cstring> 10 #include <iostream> 11 #include <algorithm> 12 using namespace std; 13 14 typedef long long LL; 15 typedef pair<int, int> PII; 16 17 const int N = 1005; 18 const int mod = 1000000007; 19 int f[N][N]; 20 int c[N][N]; 21 LL fact[N]; 22 23 inline void add(int &x, int y) { 24 x += y; 25 if (x >= mod) 26 x %= mod; 27 } 28 29 int main() { 30 31 freopen("testB.in","r",stdin); 32 freopen("testB.out","w",stdout); 33 f[0][0] = f[0][1] = 1; 34 for (int d = 1; d < N - 1; d++) 35 for (int i = N - 1; i >= d; i--) 36 for (int j = min(d + 1, 50); j > 0; j--) 37 add(f[i][j], f[i - d][j - 1]); 38 39 for (int i = 0; i < N; i++) { 40 c[i][0] = c[i][i] = 1; 41 for (int j = 1; j < i; j++) { 42 c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; 43 if (c[i][j] >= mod) 44 c[i][j] -= mod; 45 } 46 } 47 fact[0] = 1; 48 for (int i = 1; i < N; i++) 49 fact[i] = fact[i - 1] * i % mod; 50 51 int T; 52 scanf("%d", &T); 53 while (T--) { 54 int n, k; 55 scanf("%d%d", &n, &k); 56 if (n < k) 57 puts("0"); 58 else { 59 LL ans = 0; 60 for (int x = 0; x <= n - k; x++) { 61 LL s = (LL)c[n - x][k] * f[x][k] % mod; 62 ans += s; 63 if (ans >= mod) 64 ans -= mod; 65 } 66 printf("%I64d\n", ans * fact[k] % mod); 67 } 68 } 69 return 0; 70 }
第三题比较水，我就不多说什么了，多特判就好了。。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int main() 5 { 6 freopen("testC.in","r",stdin); 7 freopen("testC.out","w",stdout); 8 int n,m,x; 9 cin>>n>>m>>x; 10 if(x<0) 11 { 12 cout<<0<<endl; 13 return 0; 14 } 15 if(x==0) 16 { 17 cout<<n*m/2<<endl; 18 return 0; 19 } 20 x-=1; 21 n-=2*x; 22 m-=2*x; 23 if(n<=0||m<=0) 24 cout<<0<<endl; 25 else if(n==1||m==1) 26 cout<<n*m-n*m/2<<endl; 27 else 28 cout<<(n+m)-2<<endl; 29 return 0; 30 }
原文：http://www.cnblogs.com/JackSlowFuck/p/3831941.html
