|
Problem B
|
Beautiful Numbers
|
Time Limit : 3 seconds
|
|||
|
An N-based number is beautiful if all of the digits from 0 to N-1 are used in that number and the difference between any two adjacent digits is exactly 1 (one). For example, 9876543210 is a 10-based beautiful number. You have to calculate the number beautiful numbers that has got atmost M digits.. Note: No leading zero is allowed in a beautiful number.
|
|||||
| Input | |||||
| The first line of input is an integer T (T<100) that indicates the number of test cases. Each case starts with a line containing two integers N and M ( 2≤N≤10 & 0≤M≤100 ). | |||||
| Output | |||||
| For each case, output the number of beautiful N-based numbers, which are using less than or equal to M digits in a single line. You have to give your output modulo 1000000007. | |||||
| Sample Input | Sample Output | ||||
|
3 2 4 3 7 10 10 |
3 31 1 |
||||
思路 dp[lastnum][dep(数字个数)][各位数使用情况（bitmask）]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
ll dp[11][110][1100];
int n,m;
ll dfs(int last,int num,int used){
if(dp[last][num][used] != -1) return dp[last][num][used];
if(num==0) return used == (1<<n)-1;
if(last == n){
ll ans = 0;
for(int i = 1; i <= n-1; i++) ans = (ans + dfs(i,num-1,1<<i))%MOD;
return dp[last][num][used] = ans;
}
ll ans = 0;
int tmp;
if(last>0){
tmp = 1<<(last-1);
ans = (ans + dfs(last-1,num-1,used|tmp))%MOD;
}
if(last<n-1){
tmp = 1<<(last+1);
ans = (ans + dfs(last+1,num-1,used|tmp))%MOD;
}
return dp[last][num][used] = ans;// 1010 10 101
}
int main(){
int ncase;
cin >> ncase;
while(ncase--){
scanf("%d%d",&n,&m);
memset(dp,-1,sizeof dp);
ll ans = 0;
for(int i = 0; i <= m; i++) ans = (dfs(n,i,0)+ans)%MOD;
cout<<ans<<endl;
}
return 0;
}