## 【BZOJ 3930】[CQOI2015] 选数

### 解题报告

PoPoQQQ大爷给了一种神奇的做法：http://blog.csdn.net/popoqqq/article/details/44917831

$\sum\limits_{i = 1}^n {\mu (i) = 1 – \sum\limits_{i = 2}^n {(0 – \mu (i)) = } 1 – \sum\limits_{i = 2}^n {(\sum\limits_{j|i} {\mu (j)} – \mu (i))} = 1 – \sum\limits_{i = 2}^n {\sum\limits_{j|i,i \ne j} {\mu (j)} } } = 1 – \sum\limits_{j = 1}^n {\mu (j) \cdot (\left\lfloor {\frac{n}{j}} \right\rfloor – 1)} = 1 – \sum\limits_{j = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {\mu (j) \cdot (\left\lfloor {\frac{n}{j}} \right\rfloor – 1)}$

—————————— UPD 2017.2.20 ——————————

## 【51NOD 1806】wangyurzee的树

1）可能有多个限制条件针对一个点，在容斥的时候要排除这种情况
2）容斥的时候，所有点的度都确定了，但度数不等于n-2的情况容斥也要排除掉

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

const int M = 20;
const int N = 1000000+9;
const int MX = 1000000;
const int MOD = 1000000007;

int POW[N],REV[N],lim[M],id[M],n,m,vout,vis[N];
set<pair<int,int> > S;

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;
}

inline int pow(int w, int t) {
if (!w || t <= 0) return 1; int ret = 1;
while (t) {
if (t & 1) ret = (LL)ret * w % MOD;
w = (LL)w * w % MOD; t >>= 1;
} return ret;
}

inline int C(int x, int y) {
int ret = (LL)POW[y] * REV[x] % MOD;
return (LL)ret * REV[y-x] % MOD;
}

void DFS(int t, int tot, int cnt, int sol, int f) {
if (tot < 0 || (tot > 0 && cnt == n)) return;
else if (t >= m + 1) {
if (!cnt) return;
else {
sol = (LL)sol * pow(n - cnt,tot) % MOD;
vout = ((vout + f*sol) % MOD + MOD) % MOD;
}
} else {
DFS(t+1, tot, cnt, sol, f);
if (!vis[id[t]]) {
vis[id[t]] = 1;
DFS(t+1, tot - lim[t], cnt + 1, (LL)sol * C(lim[t],tot) % MOD, -f);
vis[id[t]] = 0;
}
}
}

int main(){
for (int i=1;i<=m;i++) {
if (S.count(make_pair(id[i],lim[i]))) {
i--; m--;
} else {
S.insert(make_pair(id[i],lim[i]));
}
}
POW[1] = REV[1] = POW[0] = REV[0] = 1;
for (int i=2;i<=MX;i++) POW[i] = (LL)POW[i-1] * i % MOD;
REV[MX] = pow(POW[MX], MOD - 2);
for (int i=MX-1;i;i--) REV[i] = (LL)REV[i+1] * (i + 1) % MOD;

vout = pow(n, n-2);
DFS(1,n-2,0,1,1);
printf("%d\n",vout);
return 0;
}


## 【BZOJ 4517】[SDOI2016] 排列计数

$$\begin{array}{l} f(n) = n! – C_n^1 \cdot (n – 1)! + C_n^2 \cdot (n – 2)! – \cdots – C_n^n \cdot 1!\\ f(n) = \frac{{n!}}{{2!}} – \cdots – \frac{{n!}}{{n!}}\\ f(n) = n! \cdot \sum\limits_{i = 2}^n {\frac{{{{( – 1)}^i}}}{{i!}}} \\ f(n) = f(n – 1) \cdot \frac{{n!}}{{(n – 1)!}} + {( – 1)^n} \end{array}$$

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

const int N = 1000000+9;
const int MX = 1000000;
const int MOD = 1000000007;

int p[N],d[N],REV[N];

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

inline LL C(int a, int b) {
return (((LL)p[a]*REV[b])%MOD)*REV[a-b] % MOD;
}

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(){
p[1] = p[0] = REV[0] = 1; d[1] = 0; d[0] = 1;
for (int i=2;i<=MX;i++) p[i] = (LL)p[i-1]*i % MOD;
REV[MX] = pow(p[MX],MOD-2);
for (int i=MX-1;i;i--) REV[i] = (LL)REV[i+1]*(i+1) % MOD;
for (int i=2;i<=MX;i++) d[i] = ((d[i-1] + (i&1?-REV[i]:REV[i])) % MOD + MOD) % MOD;
for (int i=0;i<=MX;i++) d[i] = (LL)d[i]*p[i] % MOD;
if (m > n) puts("0");
else cout<<C(n,m)*d[n-m]%MOD<<endl;
} return 0;
}


## 【BZOJ 4572】[SCOI2016] 围棋

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)<0?-(x):(x))
using namespace std;

const int MOD = 1000000007;
const int REV = 333333336;
const int MAXN = 1 << 10;

int f[2][MAXN][2],trans[MAXN][MAXN],MX,n,m,c,q,N;
bool leg[MAXN],nxt[20][20],vis1[20],vis2[20],bit_cnt[MAXN];
char pat[2][10];

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

inline void prework() {
memset(trans,0,sizeof(trans));
for (int w=0,sign;w<=MX;w++) {
leg[w] = sign = 1; bit_cnt[w] = __builtin_popcount(w)&1;
for (int i=1;i<=N&&sign;i++) if (w&(1<<(i-1))) for (int j=i+1;j<=N&&sign;j++) if (w&(1<<(j-1)) && j-i < c)
for (int t=0;t<2&&sign;t++) for (int k=1;k<=c-j+i&&sign;k++) if (pat[t][k] != pat[t][j-i+k]) sign = leg[w] = 0;
}
for (int i=1,sign;i<=N;i++) for (int j=1;j<=N;j++) {
nxt[i][j] = sign = 1; if (abs(i-j+1) > c) continue;
if (i < j) {for (int k=1;k<=c-j+i&&sign;k++) if (pat[0][k] != pat[1][j-i+k]) nxt[i][j] = sign = 0;}
else for (int k=1;k<=c+j-i&&sign;k++) if (pat[1][k] != pat[0][i-j+k]) nxt[i][j] = sign = 0;
}
for (int w1=0;w1<=MX;w1++) if (leg[w1]) {
memset(vis1,0,sizeof(vis1));
for (int i=1;i<=N;i++) if (w1&(1<<(i-1))) for (int j=0;j<c;j++) vis1[i+j] = 1;
for (int w2=0,sign;w2<=MX;w2++) if (sign=1, leg[w2]){
for (int i=1;i<=N;i++) if (w1&(1<<(i-1))) for (int j=1;j<=N;j++) if (w2&(1<<(j-1)) && !nxt[i][j]) sign = 0;
if (!sign) continue; int tmp = 1; memset(vis2,0,sizeof(vis2));
for (int i=1;i<=N;i++) if (w2&(1<<(i-1))) for (int j=0;j<c;j++) vis2[i+j] = 1;
for (int i=1;i<=n;i++) if (!vis2[i]) tmp = tmp*3LL % MOD; else if (!vis1[i]) tmp = (LL)tmp*REV % MOD;
trans[w1][w2] = tmp;
}
}
}

inline void solve() {
int cur = 0, p = 1, vout = pow(3,n*m);
memset(f[p],0,sizeof(f[p])); f[p][0][0] = pow(3,n);
for (int stp=2;stp<=m;stp++,cur^=1,p^=1) {
memset(f[cur],0,sizeof(f[cur]));
for (int w1=0;w1<=MX;w1++) for (int t=0;t<2;t++) if (f[p][w1][t])
for (int w2=0;w2<=MX;w2++) (f[cur][w2][t^bit_cnt[w2]] += (LL)f[p][w1][t] * trans[w1][w2] % MOD) %= MOD;
}
for (int w=0;w<=MX;w++) (vout -= f[p][w][0]) %= MOD, (vout += f[p][w][1]) %= MOD;
printf("%d\n",(vout%MOD+MOD)%MOD);
}

int main(){
cin>>m>>n>>c>>q;
MX = (1 << (n - c + 1)) - 1; N = n - c + 1;
for (int i=1;i<=q;i++) {
scanf("%s%s",pat[0]+1,pat[1]+1);
prework(); solve();
}
return 0;
}


## 【BZOJ 1853】[Scoi2010] 幸运数字

↓↓↓↓↓↓这个是GIF，要点开才能感受到来自心灵的震撼！↓↓↓↓↓↓

#include<iostream>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;

const int MAXN = 20000;

int cnt,tot;
LL arr[MAXN],buf[MAXN],l,r,vout;

void DFS(LL w){
if (w > r) return;
buf[++cnt] = w;
DFS(w*10+6);
DFS(w*10+8);
}

inline void prework(){
DFS(6); DFS(8);
sort(buf+1,buf+cnt);
for (int i=1,tag=0;i<=cnt;i++,tag=0) {
for (int j=i-1;j;j--) if (buf[i]%buf[j]==0) {tag=1;break;}
if (!tag) arr[++tot] = buf[i];
}
for (int i=1;i*2<=tot;i++) swap(arr[i],arr[tot-i+1]);
}

LL GCD(LL a, LL b){return b?GCD(b,a%b):a;}

void solve(int step, int sz, LL w){
if (step == tot+1) {
if (sz & 1) vout += r/w - (l-1)/w;
else if (sz) vout -= r/w - (l-1)/w;
} else {
solve(step+1,sz,w);
double tmp = (double)w*arr[step]/GCD(w,arr[step]);
if (tmp <= r) solve(step+1,sz+1,w/GCD(w,arr[step])*arr[step]);
}
}

int main(){
scanf("%lld%lld",&l,&r);
prework();
solve(1,0,1);
printf("%lld\n",vout);
return 0;
}


## 【BZOJ 2393】Cirno的完美算数教室

#include<iostream>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;

const int MAXN = 2000;

int l,r,arr[MAXN],tmp[MAXN],vout,cnt,tot;

void DFS(LL w){
if (w > r) return;
tmp[++cnt] = w;
DFS(w*10+2);
DFS(w*10+9);
}

inline void prework(){
DFS(2); DFS(9);
sort(tmp+1,tmp+cnt);
for (int i=1,tag=0;i<=cnt;i++,tag=0) {
for (int j=i-1;j;j--) if (tmp[i] % tmp[j] == 0) {tag = 1; break;}
if (!tag) arr[++tot] = tmp[i];
}
for (int i=1;i*2<=tot;i++) swap(arr[i],arr[tot-i+1]);
}

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

void solve(int step, int sz, int w){
if (step == tot+1) {
if (sz & 1) vout += r/w - (l-1)/w;
else if (sz) vout -= r/w - (l-1)/w;
} else {
solve(step+1,sz,w);
LL buf = (LL)w/GCD(w,arr[step])*arr[step];
if (buf <= r) solve(step+1,sz+1,buf);
}
}

int main(){
scanf("%d%d",&l,&r);
prework();
solve(1,0,1);
printf("%d\n",vout);
return 0;
}