## 【BZOJ 4197】[NOI2015] 寿司晚宴

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 509;
const int M = 6561;

int pri[] = {2, 3, 5, 7, 11, 13, 17, 19};
int n, gpri[N], spri[N], sta1[M], sta2[M], tt[M][N][3];
LL MOD, *f, *g, *h, arr1[M], arr2[M], arr3[M], ori[M];
vector<int> sta[N];

inline void relax(LL &a, LL b) {
a = (a + b) % MOD;
}

inline int num(int x, int t) {
for (; t; x /= 3, t--);
return x % 3;
}

inline int SET(int w, int t, int v) {
static int buf[] = {1, 3, 9, 27, 81, 243, 729, 2187};
int ret = 0;
for (int i = 0; i < 8; i++, w /= 3, t >>= 1) {
if (t & 1) {
ret += buf[i] * v;
} else {
ret += buf[i] * (w % 3);
}
}
return ret;
}

int main() {
freopen("dinner.in", "r", stdin);
freopen("dinner.out", "w", stdout);
cin>>n>>MOD;
for (int i = 0; i < M; i++) {
for (int j = 0; j < 8; j++) {
int t = num(i, j);
if (t == 1) {
sta1[i] |= 1 << j;
} else if (t == 2) {
sta2[i] |= 1 << j;
}
}
}
for (int i = 0; i < M; i++) {
for (int j = 0; j < (1 << 8); j++) {
for (int k = 1; k <= 2; k++) {
tt[i][j][k] = SET(i, j, k);
}
}
}
for (int i = 2; i <= n; i++) {
gpri[i] = i;
for (int j = 0; j < 8; j++) {
if (gpri[i] % pri[j] == 0) {
spri[i] |= (1 << j);
while (gpri[i] % pri[j] == 0) {
gpri[i] /= pri[j];
}
}
}
}
f = arr1, g = arr2, h = arr3;
g[0] = f[0] = 1;
for (int i = 2; i <= n; i++) {
if (gpri[i] == 1) {
for (int j = M - 1; ~j; j--) {
if (g[j]) {
int sta = 0;
for (int k = 0; k < 8; k++) {
if (spri[i] >> k & 1) {
sta |= num(j, k);
}
}
if (sta == 0) {
relax(f[tt[j][spri[i]][1]], g[j]);
relax(f[tt[j][spri[i]][2]], g[j]);
} else if (sta < 3) {
relax(f[tt[j][spri[i]][sta]], g[j]);
}
}
}
memcpy(g, f, sizeof(arr1));
swap(f, g);
} else {
sta[gpri[i]].push_back(spri[i]);
}
}
for (int i = 2; i <= n; i++) {
if (!sta[i].empty()) {
memcpy(h, g, sizeof(arr1));
memcpy(ori, g, sizeof(arr1));
for (int j = 0; j < (int)sta[i].size(); j++) {
int vv = sta[i][j];
for (int k = M - 1; ~k; k--) {
if (g[k]) {
int s1 = vv & sta1[k];
if (!s1) {
relax(f[tt[k][vv][2]], g[k]);
}
}
}
memcpy(g, f, sizeof(arr1));
swap(f, g);
}
memcpy(f, h, sizeof(arr1));
for (int j = 0; j < (int)sta[i].size(); j++) {
int vv = sta[i][j];
for (int k = M - 1; ~k; k--) {
if (h[k]) {
int s2 = vv & sta2[k];
if (!s2) {
relax(f[tt[k][vv][1]], h[k]);
}
}
}
memcpy(h, f, sizeof(arr1));
swap(f, h);
}
for (int k = 0; k < M; k++) {
f[k] = g[k] = (f[k] + g[k] - ori[k]) % MOD + MOD;
}
}
}
LL ans = 0;
for (int i = 0; i < M; i++) {
relax(ans, f[i]);
}
printf("%lld\n", ans);
return 0;
}


## 【TopCoder SRM713】DFSCount

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int n,id[15];
bool g[15][15],vis[15];
LL f[15][17000],pw[15],pol[15];

class DFSCount {
public:
long long count(vector<string> G) {
pw[0] = 1;
for (int i=1;i<=14;i++) {
pw[i] = pw[i-1] * i;
}
n = G.size();
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
if (G[i][j] == 'Y') g[i][j] = 1;
else g[i][j] = 0;
}
}
memset(f, 0, sizeof(f));
for (int i=0;i<n;i++) {
f[i][(1<<n)-1] = 1;
}
for (int sta=(1<<n)-2;sta>0;sta--) {
for (int i=0;i<n;i++) {
if (!(sta&(1<<i))) continue;
for (int j=0;j<n;j++) {
vis[j] = (sta & (1 << j));
}
int cnt = 0;
for (int j=0;j<n;j++) {
if (g[i][j] && !(sta&(1<<j))) {
if (!vis[j]) {
DFS(j, ++cnt);
pol[cnt] = 0;
}
pol[id[j]] += f[j][(1<<j)|sta];
}
}
f[i][sta] = pw[cnt];
for (int j=1;j<=cnt;j++) {
f[i][sta] *= pol[j];
}
}
}
LL ret = 0;
for (int i=0;i<n;i++) {
ret += f[i][1<<i];
}
return ret;
}
private:
void DFS(int w, int ID) {
vis[w] = 1;
id[w] = ID;
for (int i=0;i<n;i++) {
if (g[w][i] && !vis[i]) {
DFS(i, ID);
}
}
}
};


## 【HDU 4626】Jinkeloid

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3000000;
const int M = 100009;
const int UNIVERSE = (1 << 20) - 1;
const int SGZ = 20;

char pat[M];
int n,m,sta;
LL a[N],f[N],zero;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void FWT(LL *arr, int len, int ty) {
for (int d=1;d<len;d<<=1) {
for (int i=0;i<=len;i+=d*2) {
for (int j=0;j<d;j++) {
LL t1 = arr[i+j], t2 = arr[i+j+d];
arr[i+j] = t1 + t2;
arr[i+j+d] = t1 - t2;
if (ty == -1) {
arr[i+j] /= 2;
arr[i+j+d] /= 2;
}
}
}
}
}

int main() {
memset(a, 0, sizeof(a));
scanf("%s",pat);
n = strlen(pat);
a[0]++; sta = zero = 0;
for (int i=0;i<n;i++) {
sta ^= 1 << pat[i] - 'a';
zero += a[sta]++;
}
FWT(a, UNIVERSE, 1);
for (int i=0;i<=UNIVERSE;i++) {
a[i] = a[i] * a[i];
}
FWT(a, UNIVERSE, -1);
a[0] = zero;
for (int i=1;i<=UNIVERSE;i++) {
a[i] /= 2;
}
for (int i=0;i<=UNIVERSE;i++) {
if ((i ^ UNIVERSE) < i) {
swap(a[i], a[i^UNIVERSE]);
}
}
for (int j=0;j<SGZ;j++) {
for (int i=0;i<=UNIVERSE;i++) {
if (i & (1<<j)) {
a[i^(1<<j)] += a[i];
}
}
}
for (int tt=1;tt<=m;tt++) {
int k = read(), sta = 0;
for (int i=1;i<=k;i++) {
scanf("%s",pat);
sta |= 1 << pat[0] - 'a';
}
printf("%lld\n",a[sta]);
}
}
return 0;
}


## 【HDU 4623】Crime

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3000000;
const int M = 16;

int n,mx,MX,MOD,f[N][M],cnt[M],bit[M],cur[M],sym[M],suf[M],leg[M][M];
int ty[]={0,1,2,3,2,4,5,6,2,3,7,8,5,9,10,11,2,1,5,1,7,12,13,1,5,4,14,3,10};

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int gcd(int a, int b) {
return b? gcd(b, a%b): a;
}

inline void decode(int w, int *arr) {
for (int i=mx;i;i--) {
arr[i] = w % bit[i];
w /= bit[i];
}
}

inline int solve() {
memset(cnt,0,sizeof(cnt));
mx = MX = 0;
for (int i=1;i<=n;i++) {
cnt[ty[i]]++;
mx = max(mx, ty[i]);
}
for (int i=1;i<=mx;i++) {
bit[i] = cnt[i] + 1;
MX = MX * bit[i] + cnt[i];
}
suf[mx] = 1;
for (int i=mx-1;i;i--) {
suf[i] = suf[i+1] * bit[i+1];
}
memset(f,0,sizeof(f));
f[0][0] = 1;
for (int i=0;i<MX;i++) {
decode(i, cur);
for (int j=0;j<=mx;j++) {
if (!f[i][j]) continue;
for (int k=1;k<=mx;k++) {
if ((leg[k][j] || !j) && cur[k] < cnt[k]) {
int to = i + suf[k];
f[to][k] = (f[to][k] + (LL)f[i][j] * (cnt[k] - cur[k])) % MOD;
}
}
}
}
int ret = 0;
for (int i=1;i<=mx;i++) {
ret = (ret + f[MX][i]) % MOD;
}
return ret;
}

int main() {
for (int i=1;i<=28;i++) {
if (sym[ty[i]]) continue;
sym[ty[i]] = i;
}
for (int i=1;i<=14;i++) {
for (int j=1;j<=14;j++) {
if (gcd(sym[i], sym[j]) == 1) {
leg[i][j] = 1;
}
}
}
printf("%d\n",solve());
}
return 0;
}


## 【HDU 4628】Pieces

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char s[20];
int n,f[1<<17];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline bool judge(int x) {
int tot=0; char tmp[20];
for (int i=1;i<=n;i++,x>>=1) {
if (x&1) {
tmp[++tot] = s[i];
}
}
for (int i=1,j=tot;i<j;i++,j--) {
if (tmp[i] != tmp[j]) {
return 0;
}
}
return 1;
}

int main() {
memset(f,60,sizeof(f));
scanf("%s",s+1);
n = strlen(s+1);
for (int i=1,MX=1<<n;i<MX;i++) {
if (judge(i)) {
f[i] = 1;
} else {
for (int j=i;j;j=(j-1)&i) {
f[i] = min(f[i], f[j] + f[i^j]);
}
}
}
printf("%d\n",f[(1<<n)-1]);
}
return 0;
}


## 【日常小测】迷宫

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1004535809;

int n,tot,vout,sta[100][7],cur[7];
struct Matrix{
int f[100][100];
inline Matrix() {memset(f,0,sizeof(f));}
inline Matrix(int x) {memset(f,0,sizeof(f));for(int i=1;i<=tot;i++)f[i][i]=x;}
inline Matrix(const Matrix &M) {for(int i=1;i<=tot;i++)for(int j=1;j<=tot;j++)f[i][j]=M.f[i][j];}
inline Matrix operator * (const Matrix &M) {
Matrix ret;
for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) for (int k=1;k<=tot;k++)
ret.f[i][k] = (ret.f[i][k] + (LL)f[j][k] * M.f[i][j]) % MOD;
return ret;
}
inline Matrix operator ^ (int t) {
Matrix ret(1),tmp(*this);
for (;t;t>>=1,tmp=tmp*tmp)
if (t&1) ret=ret*tmp;
return ret;
}
inline void out() {
for (int i=1;i<=tot;i++) {
for (int j=1;j<=tot;j++) {
printf("%d ",f[j][i]);
} cout<<endl;
}
}
}ans,trans;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

void DFS(int w, int v) {
if (w == 7) {
memcpy(sta[++tot],cur,sizeof(cur));
} else {
for (int i=1;i<=3;i++) if (i != v)
cur[w] = i, DFS(w+1, i);
}
}

inline int Pow(int w, LL t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t&1) ret=(LL)ret*w%MOD;
return ret;
}

inline bool check(int a, int b) {
for (int i=1;i<=6;i++) {
if (i > 1 && sta[a][i-1] == sta[b][i]) return 0;
if (i < tot && sta[a][i+1] == sta[b][i]) return 0;
} return 1;
}

int main() {
freopen("board.in","r",stdin);
freopen("board.out","w",stdout);
for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++)
if (check(i, j)) trans.f[j][i] = 1 << 6;
for (int i=1;i<=tot;i++) if (sta[i][1] == 1) ans.f[i][1] = 1 << 5;
trans = trans ^ (n - 1); ans = ans * trans;
for (int i=1;i<=tot;i++) vout = (vout + ans.f[i][1]) % MOD;
vout = (vout - 2ll * Pow(2, n * 6ll - 1)) % MOD;
vout = (LL)vout * Pow(4, MOD-2) % MOD;
vout = (vout + Pow(2, n * 6ll - 1)) % MOD;
printf("%d\n",(vout+MOD)%MOD);
return 0;
}


## 【BZOJ 4635】数论小测验

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 10000009;
const int M = 32;

int n,m,SZ,s1[N],hc[N],to[1001];
int tot,pri[N>>3],mu[N]; bool vis[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t&1) ret=(LL)ret*w%MOD;
return ret;
}

inline void GetMu() {
mu[1] = 1;
for (int i=2;i<N;i++) {
if (!vis[i]) mu[i] = -1, pri[++tot] = i;
for (int j=1;j<=tot&&pri[j]*i<N;j++) {
vis[i*pri[j]] = 1;
if (i%pri[j]) mu[i*pri[j]] = -mu[i];
else {mu[i*pri[j]] = 0; break;}
}
mu[i] = mu[i-1] + mu[i];
}
}

inline int cal(int mx) {
int ret = 0;
for (int l=1,r,tmp;l<=mx;l=r+1) {
r = mx / (mx / l);
tmp = (LL)(mu[r] - mu[l-1]) * hc[mx/l] % MOD;
ret = (ret + tmp) % MOD;
}
return (ret + MOD) % MOD;
}

struct Matrix{
int a[M][M];
inline Matrix() {memset(a,0,sizeof(a));}
inline Matrix(const Matrix *A) {
for (int i=0;i<M;i++) for (int j=0;j<M;j++) a[i][j] = A->a[i][j];
}
inline Matrix(int x) {
memset(a,0,sizeof(a));
for (int i=0;i<SZ;i++) a[i][i] = x;
}
inline void operator *= (const Matrix &A) {
Matrix ret;
for (int i=0,*t1,*t3;i<SZ;i++) {
t1 = ret.a[i]; const int *t2 = A.a[i];
for (int j=0;j<SZ;j++) {
t3 = a[j];
for (int k=0;k<SZ;k+=4) {
t1[k] = (t1[k] + (LL)t3[k] * t2[j]) % MOD;
t1[k+1] = (t1[k+1] + (LL)t3[k+1] * t2[j]) % MOD;
t1[k+2] = (t1[k+2] + (LL)t3[k+2] * t2[j]) % MOD;
t1[k+3] = (t1[k+3] + (LL)t3[k+3] * t2[j]) % MOD;
}
}
}
for (int i=0;i<SZ;i++) for (int j=0;j<SZ;j++) a[i][j] = ret.a[i][j];
}
inline Matrix operator ^ (int t) {
Matrix ret(1),w(this);
for (;t;t>>=1,w*=w) if (t&1) ret*=w;
return ret;
}
}ans,trans;

inline int solve(int w) {
tot = 0;
for (int i=2,tmp=w;i<=tmp;i++) {
if (tmp % i == 0) {
pri[++tot] = i; tmp /= i;
while (tmp % i == 0) pri[tot] *= i, tmp /= i;
}
}
ans = Matrix(); trans = Matrix();
ans.a[0][0] = 1; SZ = 1 << tot;
memset(to,0,sizeof(to));
for (int i=1,t=1,ww;ww=pri[i],i<=tot;i++,t<<=1)
for (int j=ww;j<=m;j+=ww) to[j] |= t;
for (int i=1,tt;tt=to[i],i<=m;i++) {
for (int p=0,ww;ww=p,p<SZ;p++)
++trans.a[p|tt][p];
}
trans = trans ^ n;
ans *= trans;
return ans.a[SZ-1][0];
}

int main() {
if (type == 1) {
GetMu();
for (int t=1,vout;vout=0,t<=T;t++) {
for (int l=1,r;l<=m;l=r+1) {
r = m / (m / l);
hc[m / l] = Pow(m / l, n);
}
for (int l=L,r,tmp;l<=R;l=r+1) {
r = m / (m / l); tmp = cal(m / l);
vout = (vout + (min(r,R)-max(L,l)+1ll) * tmp) % MOD;
}
printf("%d\n",vout);
}
} else if (type == 2) {
for (int t=1,vout,l,r;vout=0,t<=T;t++) {
for (int w=l;w<=r;w++) vout = (vout + solve(w)) % MOD;
printf("%d\n",vout);
}
}
return 0;
}


## 【日常小测】排列

### 解题报告

GEOTCBRL就是用这个A的，太强大了_(:з」∠)_

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int n,K,t,tot,itr[1000],num[1000];
struct Matrix{
int a[70][70];
inline Matrix() {memset(a,0,sizeof(a));}
inline Matrix(Matrix *tmp) {memcpy(a,tmp->a,sizeof(a));}
inline Matrix(int v) {memset(a,0,sizeof(a));for(int i=0;i<tot;i++)a[i][i]=v;}
inline void reset() {memset(a,0,sizeof(a));}
inline Matrix operator * (const Matrix &B) {
Matrix ret;
for (int i=0;i<tot;i++) for (int j=0;j<tot;j++) for (int k=0;k<tot;k++)
ret.a[i][j] = (ret.a[i][j] + (LL)a[k][j] * B.a[i][k]) % MOD;
return ret;
}
inline Matrix operator ^ (int t) {
Matrix ret(1),w(this);
for (;t;t>>=1,w=w*w)
if (t&1) ret=ret*w;
return ret;
}
}ans,tra;

int main() {
for (;~scanf("%d%d",&n,&t);tot=0) {
t <<= 1; K = 1 << t;
ans.reset(); tra.reset();
for (int i=0;i<K;i++) {
if (__builtin_popcount(i) != t/2) continue;
else itr[i] = tot, num[tot++] = i;
}
for (int h=0,cur,i;i=num[h],h<tot;h++) {
for (int j=0;j<=t;j++) {
if (i&(1<<j)) continue;
cur = i | (1 << j);
if (!(cur&1)) continue;
tra.a[h][itr[cur>>1]] = 1;
}
}
t = itr[(1<<(t/2))-1]; ans.a[t][0] = 1;
tra = tra ^ n; ans = ans * tra;
printf("%d\n",ans.a[t][0]);
}
return 0;
}


## 【BZOJ 4762】最小集合

### 解题报告

1. $f[i][j][k] \to f[i+1][j|a_i][k-(k \& a_i)]$表示不强制非法
2. $-f[i][j][k] \to f[i+1][j|a_i][(k-(k \& a_i))|(a_i-(a_i \& j))]$表示强制非法
ps: 根据容斥原理，第二种转移会配上$-1$的系数

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1001;
const int M = (1 << 10) - 1;
const int MOD = 1000000007;

int n,vout,a[N],f[1<<10][1<<10];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main() {
for (int i=1;i<=n;i++) a[i] = read() ^ M;
f[0][0] = 1;
for (int t=1;t<=n;t++) {
for (int i=M,ti,tj,uni;~i;--i) {
if ((ti = (a[t] | i)) > i) {
uni = ti - i;
for (int j=i;;(--j)&=i) {
tj = (j - (j & a[t]));
f[ti][tj] = (f[ti][tj] + f[i][j]) % MOD;
f[ti][tj|uni] = (f[ti][tj|uni] - f[i][j]) % MOD;
if (!j) break;
}
}
}
}
printf("%d\n",(f[M][0]+MOD)%MOD);
return 0;
}


## 【TopCoder】[TCO2013 2B] Lit Panels

### 解题报告

topcoder_LitPanels

## 【BZOJ 4416】[SHOI2013] 阶乘字符串

slide

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = (1<<21) + 9;
const int M = 500;
const int SGZ = 21;

int n,m,f[N],last[SGZ],nxt[M][21];
char pat[M];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int main() {
scanf("%s",pat+1);
n = strlen(pat+1);
if (m > 21) {
puts("NO");
continue;
}
for (int i=0;i<m;i++)
last[i] = nxt[n+1][i] = n + 1;
for (int i=n;~i;i--) {
for (int j=0;j<m;j++)
nxt[i][j] = last[j];
if (i) last[pat[i]-'a'] = i;
}
for (int i=1,lim=1<<m;i<lim;i++) {
f[i] = 0;
for (int j=0;j<m;j++) {
if (i & (1 << j)) {
f[i] = max(f[i], nxt[f[i^(1<<j)]][j]);
}
}
}
if (f[(1<<m)-1] <= n) puts("YES");
else puts("NO");
}
return 0;
}


## 【BZOJ 4145】[AMPPZ2014] The Prices

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100+9;
const int M = 65536;

int n,m,cost[N],f[M];
pair<int,int> que[M];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

void DFS(int w, int sta, int c) {
if (w == m + 1) {
f[sta] = min(f[sta], c);
} else {
DFS(w+1, sta, c);
DFS(w+1, sta|(1<<w-1), c+cost[w]);
}
}

void update(int t, int sta, int w) {
if (t == m + 1) {
f[sta|w] = min(f[sta|w], f[sta] + f[w]);
} else {
update(t+1, sta, w);
if ((sta&(1<<(t-1))) == 0)
update(t+1, sta, w|(1<<(t-1)));
}
}

int main() {
memset(f,60,sizeof(f));
for (int i=1,d;i<=n;i++) {
for (int j=1;j<=m;j++)
DFS(1, 0, d);
}
for (int i=1,lim=1<<m;i<lim;i++)
que[i] = make_pair(__builtin_popcount(i), i);
sort(que+1, que+(1<<m));
for (int i=1,lim=1<<m;i<lim;i++)
update(1, que[i].second, 0);
printf("%d\n",f[(1<<m)-1]);
return 0;
}


—————————— UPD 2017.2.7 ——————————

for (int i=s;i;i=(i-1)&s) {}