* 풀이

2진수가 11010110101 이라면 답은 당연히 11010110110 이 되겠죠.
다시 말해서, 제일 오른쪽에 있는 1을 왼쪽으로 한칸 옮겨주면 됩니다.
그런데 만약 2진수가 ...011100 이런 형태라면 어떻게 될까요?
그럼 답은 ...100011 이 됩니다.
1이 k개가 모여 있으면, 그중에서 가장 왼쪽 1을 왼쪽으로 한칸 옮겨주고,
나머지 k-1개의 1을 제일 오른쪽에 채워주면 됩니다.

아래는 대회때 작성한, 제 코드입니다.
#define FOR(i,a,b) for( int i=(a); i<(b); ++i) #define FORD(i,a,b) for( int i=(a); i>(b); --i) #define REP(i,n) for(int i=0; i<(n); ++i) #define ALL(X) (X).begin(),(X).end() #define SZ(X) (int)(X).size()   class NextNumber { public:   int getNextNumber(int); };   int dt[50];   int NextNumber::getNextNumber(int N) {   memset(dt,0,sizeof(dt));   int len=0;   while (N) {     dt[len++]=N%2;     N/=2;   }   int j=0;   REP(i,len)     if (dt[i]==1 && dt[i+1]==0) {       dt[i]=0;       dt[i+1]=1;       if (i+1==len) len++;       j=i;       break;     }     int cnt=count(dt,dt+j,1);   REP(i,j) {     if (i<cnt) dt[i]=1;     else dt[i]=0;   }     int dp=0;   FORD(i,len-1,-1) {     dp*=2;     dp+=dt[i];   }   return dp; }

그런데 대회가 끝나고 다른 사람들의 해법을 보던 중에
훨씬 쉬운 방법이 있다는 걸 알았습니다. 바로 next_permutation을 이용한 방법입니다.
2진수를 배열에 저장하고, next_permutation을 한번 실행해주면 답이 됩니다.
10000 이런 수인 경우에 자리수가 늘어나니까, 배열은 넉넉히 잡는 게 좋겠죠?

아래는 astein님의 코드입니다. 훨씬 깔끔하네요.
<pre class="problemText">#define all(x) (x).begin(),(x).end() using namespace std; struct NextNumber { int getNextNumber(int N) { vector <int> a(32, 0); for (int i = 0; i <= 31; ++i) { if (N & (1 << (31 - i))) a[i] = 1; printf("%d", a[i]); } printf("\n"); next_permutation(a.begin(), a.end()); int ret = 0; for (int i = 0; i <= 31; ++i) { ret += a[i] * (1 << (31 - i)); printf("%d", a[i]); } printf("\n"); return ret; } };

 * 풀이

이리저리 변수를 굴려보다가 우연히(?) 생각이 나서 후다닥 푼 기억이 나네요.
6개의 변수를 각각 a1 ... a6 라고 하면, a1 + a2 + a3 + a4 + a5 + a6 <= 6*M 이면서
1 <= a1 < a2 ... < a5 < a6 인 모든 경우를 세면 됩니다.

변수를 이대로 두고 풀기는 만만치가 않으니 변수를 a1 ... a6 에서 d1 ... d6로 바꿔 봅시다.
a1 = d1
a2 = d1 + d2
a3 = d1 + d2 + d3
.
.
a6 = d1 + d2 + d3 + d4 + d5 + d6

d1, d2, d3, d4, d5, d6 >= 1
6*d1 + 5*d2 + 4*d3 + 3*d4 + 2*d5 + d6 <= 6*M

이렇게 쓰면 문제 풀기가 한결 수월해집니다. DP로 풀 수 있습니다.

dy[i][j] = 마지막 i개의 변수의 합이 j 이하여야 할 때, 가능한 경우의 수

점화식을 말로 풀어쓰니 조금 어렵네요. 예를 들어 dy[1][5]는 d6 <= 5 일때, 가능한 경우의 수이고,
dy[3][10]은 3*d4 + 2*d5 + d6 <= 10 일때, 가능한 경우의 수입니다.

우선 dy[1][k] = k 인게 당연하고, dy[2][k]를 봅시다.

2*d5 + d6 <= k 인 경우겠죠. 2*d5를 k이하가 되도록 d5를 1부터 다 정해보면

dy[2][k] = dy[1][k-2] + dy[1][k-4] + dy[1][k-6] + ... // 이런 식이 됩니다.

간단한 점화식 테크닉을 이용해서 식을 바꿔보면

dy[2][k-2] = dy[1][k-4] + dy[1][k-6] + dy[1][k-8] + ...

dy[2][k] = dy[1][k-2] + dy[2][k-2]

이렇게 됩니다. dy[3][k]인 경우도 비슷하게 구하면 되겠죠?

아래는 제가 대회 때 작성했던 코드입니다.

#define FOR(i,a,b) for( int i=(a); i<(b); ++i) #define REP(i,n) for(int i=0; i<(n); ++i)   class CustomDice { public:   int countDice(int); };   #define T 1000000007   int dy[6000005]; int res[6000005];   int CustomDice::countDice(int M) {   int m=6*M+1;   REP(i,m) dy[i]=i;     FOR(i,2,7) {     memset(res,0,sizeof(res));     FOR(j,i+1,m) {       res[j]=res[j-i]+dy[j-i];       res[j]%=T;     }         memcpy(dy,res,sizeof(dy));   }     LL tmp=res[m-1];   tmp*=30;   tmp%=T;   return tmp; }

처음에 코드를 작성했을 때는 long long dy[6000005], res[6000005] 이렇게 선언했었는데요. (혹시나 overflow날까봐..)
그리고 제 컴퓨터에서 돌려보고 답이 잘 나오길래 바로 제출해버렸는데,
제출하고 답이 잘 나오나 확인해보니 "caught signal SIGKILL" 라는 runtime-error가 나는 겁니다.
나중에 알고보니 메모리를 너무 많이 잡은 거더군요. long long을 int로 바꾸니까
답이 잘 나오더라구요. =_=