[TIOJ 1250] 蕃茄蹲

作法：

只要注意到如果有兩次選的數字一樣的話，那這兩次的作用就會抵消，所以就可以得到可能的最後狀態數會 <= 2^n ，其中 n 是可選的數字數量。但其實還要滿足選的數字的個數和 m 的奇偶性相同，其中 m 是經過的回合數，所以就可以再砍到 2^(n/2) 種狀態。但把全部狀態暴力記錄起來再用個 string 排序似乎會耗太多時間，所以我把所有可能的狀態都插入到 trie 裡面，這樣可以節省記憶體，也不用把所有狀態排序，而且在輸出答案的時候也可以很方便的用遞回輸出。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=20000+10 ;
int ch[5000000][2],ccnt ;
int now[maxn],n ;
 
void insert()
{
    int u=0 ;
    for(int i=1;i<=n;i++)
    {
        if(!ch[u][now[i]])
        {
            ccnt++ ;
            memset(ch[ccnt],0,sizeof(ch[ccnt])) ;
            ch[u][now[i]]=ccnt ;
        }
        u=ch[u][now[i]] ;
    }
}
 
void print_ans(int u,int dep)
{
    if(dep==n)
    {
        for(int i=1;i<=n;i++) printf("%d",now[i]) ;
        printf("\n") ;
        return ;
    }
    if(ch[u][0])
    {
        now[dep+1]=0 ;
        print_ans(ch[u][0],dep+1) ;
    }
    if(ch[u][1])
    {
        now[dep+1]=1 ;
        print_ans(ch[u][1],dep+1) ;
    }
}
 
inline void flip(int x)
{
    for(int i=x;i<=n;i+=x) now[i]^=1 ;
}
 
main()
{
    int k,m ;
    bool fir=1 ;
    while(scanf("%d%d%d",&n,&k,&m)==3 && n+k+m)
    {
        memset(ch[0],0,sizeof(ch[0])) ; ccnt=0 ;
 
        for(int i=0;i<(1<<k);i++)
        {
            int num=0 ;
            for(int j=0;j<k;j++) if(i&(1<<j)) num++ ;
            if(num>m || (m-num)%2) continue ;
            fill(now+1,now+n+1,1) ;
            for(int j=0;j<k;j++) if(i&(1<<j)) flip(j+1) ;
            insert() ;
        }
        if(fir) fir=0 ;
        else printf("\n") ;
        print_ans(0,0) ;
    }
}