## 【BZOJ 1442】[POI2006] Crystal

### 解题报告

1. 第i位只能填0
那么剩下的位数的可能情况就有a & (1<<i)种辣
2. 第i位可以发生折越
那么不发生折越的情况同第一类
发生折越之后，因为可以随便取，所以得乘上1<<i

### Code

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

const int N = 59;

LL n,arr[N],vout;

int main() {
cin>>n;
for (int i=1;i<=n;i++) cin>>arr[i];
for (int t=31;~t;t--) {
LL f[3],t1,t2,od; od = 0;
f[0] = 1; f[1] = f[2] = 0;
for (int i=1,tmp;i<=n;i++) {
tmp = (arr[i] & ((1LL<<t) - 1)) + 1;
if (arr[i] & (1LL<<t)) {
od ^= 1;
t1 = f[0] + (f[2] << t);
t2 = f[1] << t;
f[0] *= tmp;
(f[1] *= tmp) += t1;
(f[2] *= tmp) += t2;
} else {
f[0] *= tmp;
f[1] *= tmp;
f[2] *= tmp;
}
}
if (od) {vout += f[1] - 1; break;}
else vout += f[2];
}
cout<<vout;
return 0;
}


## 【Codeforces 747F】Igor and Interesting Numbers

### Code

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

int k,t,C[21][21],res[21];
char ori[]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};

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 LL solve(int len, bool ty) {
static LL f[2][20]; bool w,p;
memset(f,0,sizeof(f));
f[p=0][ty] = 1; w = 1;
for (int i=0;i<16;i++,w^=1,p^=1) {
memset(f[w],0,sizeof(f[w]));
for (int j=len;~j;j--)
for (int k=min(len-j,res[i]-(ty&(i==0)));~k;k--)
f[w][j+k] += f[p][j] * C[k][len-j];
}
return f[p][len];
}

int main() {
for (int i=0;i<=20;i++) {
C[0][i] = C[i][i] = 1;
for (int j=1;j<i;j++)
C[j][i] = C[j-1][i-1] + C[j][i-1];
}
for (int i=0;i<=15;i++)
res[i] = t;
LL tmp; int len=1;
while ((tmp = solve(len,0) - solve(len,1)) < k)
k -= tmp, len++;
for (int i=len,ret=1;i;ret=0,i--) {
res[ret]--;
while ((tmp = solve(i-1,0)) < k)
res[ret++]++, res[ret]--, k -= tmp;
printf("%c",ori[ret]);
}
return 0;
}


## 【CodeChef FAVNUM】Favourite Numbers

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

char pat[20];

namespace AC_Automaton{
#define AC AC_Automaton
LL f[20][2000][2];
int ch[2000][10],tag[2000],cnt,fail[2000],sta[20];
queue<int> que;

inline void insert(char *s){
int n = strlen(s+1), w = 0;
for (int i=1,c;i<=n;i++) {
c = s[i] - '0';
if (!ch[w]) {
ch[w] = ++cnt;
}
w = ch[w];
}
tag[w] = 1;
}

inline void Build(){
for (int i=0;i<=9;i++) if (ch[0][i]) {
que.push(ch[0][i]);
}

while (!que.empty()) {
int w = que.front(); que.pop();
for (int c=0;c<=9;c++) if (ch[w]) {
int nv = ch[w], pv = fail[w];
while (pv && !ch[pv]) pv = fail[pv];
fail[nv] = ch[pv];
tag[nv] |= tag[fail[nv]];
que.push(nv);
} else {
ch[w] = ch[fail[w]];
}
}
}

LL DFS(int t, int w, bool lim, bool leg) {
if (!t) {
return leg;
} else if (!lim && ~f[t][w][leg]) {
return f[t][w][leg];
} else {
LL ret = 0;
for (int i=0,ty=lim?sta[t]:9;i<=ty;i++) {
ret += DFS(t-1, ch[w][i], lim&&i==sta[t], leg|tag[ch[w][i]]);
}
return lim? ret: f[t][w][leg] = ret;
}
}

inline LL query(LL lim) {
int cnt = 0;
while (lim) {
sta[++cnt] = lim % 10;
lim /= 10;
}
memset(f,-1,sizeof(f));
return DFS(cnt,0,1,0);
}
};

int main(){
LL L,R,k,n,bas,w,stp;
cin>>L>>R>>k>>n;
for (int i=1;i<=n;i++) {
scanf("%s",pat+1);
AC::insert(pat);
}

AC::Build();
k += AC::query(L - 1);
if (AC::query(R) < k) {
puts("no such number");
exit(0);
}

stp = 1; w = L - 1;
while (stp < (R - L + 1)) stp <<= 1;
while (stp) {
if (AC::query(w + stp) < k) {
w += stp;
}
stp >>= 1;
}
printf("%lld\n",w+1);
return 0;
}


## 【BZOJ 1799】[Ahoi2009] self 同类分布

%NanoApe，随便减一下枝就可以Rank1了：http://nanoape.is-programmer.com/posts/193348.html

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

int MOD,sta[20];
LL f[20][170][170];

LL DFS(int t, int sum, int mod, bool lim) {
if (sum > MOD) return 0;
else if (!t) {
return sum == MOD && !mod;
} else if (!lim && ~f[t][sum][mod]) {
return f[t][sum][mod];
} else {
LL ret = 0;
for (int i=0,ty=(lim?sta[t]:9);i<=ty;i++) {
ret += DFS(t-1, sum+i, (mod*10+i)%MOD, lim&&i==sta[t]);
}
return lim? ret: f[t][sum][mod] = ret;
}
}

inline LL cal(LL lim) {
int cnt = 0;
while (lim) {
sta[++cnt] = lim % 10;
lim /= 10;
}
if (cnt*9 < MOD) return 0;
else return DFS(cnt,0,0,1);
}

int main(){
LL a,b,vout=0; cin>>a>>b;
for (int i=1;i<=162;i++) {
memset(f,-1,sizeof(f));
MOD = i;
vout += cal(b);
vout -= cal(a-1);
}
printf("%lld\n",vout);
return 0;
}


## 【HDU 3709】Balanced Number

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

int sta[20];
LL f[20][20][1500];

char c=getchar(); LL ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret;
}

LL DFS(int t, int crt, int val, bool ruf) {
if (val < 0) return 0;
else if (!t) {
return !val;
} else if (~f[t][crt][val] && !ruf) {
return f[t][crt][val];
} else {
LL ret = 0;
for (int i=0,lim=ruf?sta[t]:9;i<=lim;i++) {
ret += DFS(t-1,crt,val+(t-crt)*i,ruf&&i==sta[t]);
}
return ruf? ret: f[t][crt][val] = ret;
}
}

inline LL cal(LL lim) {
int cnt = 0;
while (lim) {
sta[++cnt] = lim % 10;
lim /= 10;
}
LL ret = 0;
for (int i=1;i<=cnt;i++) {
ret += DFS(cnt,i,0,1);
}
return ret - cnt + 1;
}

int main(){
memset(f,-1,sizeof(f));
printf("%I64d\n",cal(r)-((l>0)?cal(l-1):0));
}
return 0;
}


## 【Codeforces 55D】Beautiful numbers

1）像之前的代码一样，先预处理，然后查询的时候在数组上搞一搞

2）对于每一次询问单独dp，记录是否达到上限

3）对于每一次询问DFS，如果这一位没有受到任何限制就记忆化

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

int MOD[]={1,1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,180,210,252,280,315,360,420,504,630,840,1260,2520};
int pos[2530],lcm[50][50],sta[20];
LL f[20][50][2530];

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

LL DFS(int t, int lm, int mod, bool top) {
if (t == 0) {
return !(mod % MOD[lm]);
} else if (~f[t][lm][mod] && !top) {
return f[t][lm][mod];
} else {
LL ret = 0;
for (int i=0,ty=(top>0?sta[t]:9),tmp;i<=ty;i++) {
tmp = lcm[lm][i];
ret += DFS(t-1,tmp,(mod*10+i)%2520,top&&i==sta[t]);
}
}
}

inline LL cal(LL lim) {
int cnt = 0;
while (lim) {
sta[++cnt] = lim % 10;
lim /= 10;
}
return DFS(cnt,1,0,1);
}

char c=getchar(); LL 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(){
memset(f,-1,sizeof(f));
for (int i=1;i<=48;i++) {
pos[MOD[i]] = i;
}
for (int i=0;i<=48;i++) {
for (int j=0;j<=48;j++) {
lcm[i][j] = pos[LCM(MOD[i],MOD[j])];
}
}
printf("%I64d\n",cal(r)-cal(l-1));
}
return 0;
}


## 【BZOJ 4513】[SDOI2016] 储能表

—– UPD 2016.9.29 —–

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

LL f[62][2][2][2],g[62][2][2][2],n,m,MOD,k;

int main(){
int T; cin>>T; while (T--) {
cin>>n>>m>>k>>MOD;
memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
g[61][0][0][0] = 1;
for (int i=60;~i;i--) {
int t1 = (n>>i)&1, t2 = (m>>i)&1, t3 = (k>>i)&1;
for (int a=0;a<2;a++) for (int b=0;b<2;b++) for (int c=0;c<2;c++) if (g[i+1][a][b]) {
for (int x=0,w,wa,wb,wc;x<2;x++) for (int y=0;y<2;y++) {
if (w=x^y, (!a&&x>t1) || (!b&&y>t2) || (!c&&w<t3)) continue;
wa = (a||x<t1); wb = (b||y<t2); wc = (c||w>t3);
(g[i][wa][wb][wc] += g[i+1][a][b]) %= MOD;
(f[i][wa][wb][wc] += ((f[i+1][a][b] + (((w-t3)*((1LL<<i)%MOD))%MOD)*g[i+1][a][b]%MOD)%MOD + MOD) % MOD) %= MOD;
}
}
}
cout<<f[0][1][1][1]<<endl;
}
return 0;
}


## 【BZOJ 4521】[Cqoi2016] 手机号码

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

LL f[12][10][5][5],l,r;

char c=getchar(); LL 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 void prework(){
for (int i=0;i<=9;i++) if (i != 4 && i != 8) f[1][i][1][0] = 1;
f[1][4][1][1] = f[1][8][1][2] = 1;
for (int i=2;i<=11;i++) for (int j=0;j<=9;j++) {
if (j == 4) {
for (int p=0;p<=9;p++) if (p != j) for (int k=1;k<=2;k++) for (int ty=0;ty<=1;ty++)
f[i][j][1][1] += f[i-1][p][k][ty];
f[i][j][2][1] = f[i-1][4][1][1];
f[i][j][3][1] = f[i-1][4][2][1];
for (int p=0;p<=9;p++) for (int ty=0;ty<=1;ty++)
f[i][j][3][1] += f[i-1][p][3][ty];
} else if (j == 8) {
for (int p=0;p<=9;p++) if (p != j) for (int k=1;k<=2;k++) f[i][j][1][2] += f[i-1][p][k][0] + f[i-1][p][k][2];
f[i][j][2][2] = f[i-1][8][1][2];
f[i][j][3][2] = f[i-1][8][2][2];
for (int p=0;p<=9;p++) f[i][j][3][2] += f[i-1][p][3][0] + f[i-1][p][3][2];
} else for (int t=0;t<=2;t++) {
for (int p=0;p<=9;p++) if (p != j) for (int k=1;k<=2;k++) f[i][j][1][t] += f[i-1][p][k][t];
f[i][j][2][t] = f[i-1][j][1][t];
f[i][j][3][t] = f[i-1][j][2][t];
for (int p=0;p<=9;p++) f[i][j][3][t] += f[i-1][p][3][t];
}
}
}

inline bool judge(LL w) {
static int dig[15]; bool t1=0,t4=0,t8=0;
for (int i=1;i<=11;i++) dig[i] = w % 10, w /= 10;
for (int i=1;i<=11;i++) if (dig[i] == 4) t4 = 1;
for (int i=1;i<=11;i++) if (dig[i] == 8) t8 = 1;
for (int i=3;i<=11;i++) if (dig[i] == dig[i-1] && dig[i-1] == dig[i-2]) t1 = 1;
return t1 && !(t4 && t8);
}

inline LL cal(LL lim) {
LL ret = 0; bool t4=0, t8=0, CNT=0; static int dig[15];
for (int i=1;i<=11;i++) dig[i] = lim % 10, lim /= 10;

for (int i=1;i<dig[11];i++) for (int ty=0;ty<=2;ty++) ret += f[11][i][3][ty];
for (int k=10;k;k--) {
if (dig[k+1] == 4) t4 = 1; if (dig[k+1] == 8) t8 = 1;
if (t4 && t8) break;

int cnt = 1; for (int w=k+2;w<=11;w++) if (dig[w] != dig[k+1]) break; else cnt++;
if (cnt >= 3) CNT = 1;

for (int j=0,tmp=(k!=1);j<=dig[k]-tmp;j++)
if (CNT) for (int t=1;t<=3;t++) {
ret += f[k][j][t][0];
if (!t4) ret += f[k][j][t][2];
if (!t8) ret += f[k][j][t][1];
} else {
if (dig[k+1] == j) {
int stp = max(1,3-cnt);
for (int t=stp;t<=3;t++) {
ret += f[k][j][t][0];
if (!t4) ret += f[k][j][t][2];
if (!t8) ret += f[k][j][t][1];
}
} else {
ret += f[k][j][3][0];
if (!t4) ret += f[k][j][3][2];
if (!t8) ret += f[k][j][3][1];
}
}
}
return ret;
}

int main(){
prework();
cout<<cal(r)-cal(l)+judge(l);
return 0;
}


## 【HDU 2089】不要62

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 10;

int f[MAXN][MAXN];

inline void prework(){
for (int i=0;i<=9;i++) f[1][i] = (i != 4);
for (int k=2;k<=6;k++) {
for (int i=0;i<=9;i++) {
if (i == 4) continue;
else for (int j=0;j<=9;j++)
if (i == 6 && j == 2) continue;
else f[k][i] += f[k-1][j];
}
}
}

inline int cal(int w){
if (!w) return 0;

int ret=0,tot=0,arr[MAXN];
memset(arr,0,sizeof(arr));
while (w) arr[++tot] = w % 10, w /= 10;

for (int i=tot-1;i;i--) for (int j=1;j<=9;j++) ret += f[i][j];
for (int i=tot;i;i--) {
for (int j=(i==tot?1:0);j<arr[i];j++)
if (arr[i+1] == 6 && j == 2) continue;
else ret += f[i][j];
if ((arr[i] == 2 && arr[i+1] == 6) || arr[i] == 4) break;
else if (i == 1) ret ++;
}
return ret;
}

int main(){
prework(); int a,b;
while (scanf("%d%d",&a,&b) && (a || b))
printf("%d\n",cal(b)-cal(a-1));
return 0;
}


## 【BZOJ 1833】[ZJOI2010] count 数字计数

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

const int MAXN = 20;

LL f[MAXN][MAXN][MAXN],ans[MAXN],p[MAXN];

inline void prework(){
p[0] = 1; p[1] = 10;
for (int i=2;i<=12;i++) p[i] = p[i-1]*10;
for (int i=0;i<=9;i++) f[1][i][i] = 1;
for (int k=2;k<=12;k++) {
for (int i=0;i<=9;i++) {
for (int j=0;j<=9;j++) {
for (int h=0;h<=9;h++) {
f[k][i][h] += f[k-1][j][h];
}
}
f[k][i][i] += p[k-1];
}
}
}

inline void cal(LL w, int t){
if (!w) return;
else {
int tot = 0, arr[20]; LL tmp = w;
memset(arr,0,sizeof(arr));
while (w) arr[++tot] = w % 10, w /= 10;

for (int i=tot-1;i;i--) for (int j=1;j<=9;j++)
for (int k=0;k<=9;k++) ans[k] += f[i][j][k]*t;
for (int i=tot;i;i--) {
for (int j=(i==tot?1:0);j<=arr[i]-(i==1?0:1);j++)
for (int k=0;k<=9;k++) ans[k] += f[i][j][k]*t;
if (i>1) ans[arr[i]] += (tmp % p[i-1] + 1)*t;
}
}
}

int main(){
prework();
LL a,b; cin>>a>>b;
cal(b,1);
cal(a-1,-1);
for (int i=0;i<9;i++) printf("%lld ", ans[i]);
printf("%lld",ans[9]);
return 0;
}


## 【HDU 3555】Bomb

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

const int MAXN = 30;

LL f[MAXN][MAXN][2];

char c=getchar(); LL ret = 0;
while (c<'0'||c>'9') c = getchar();
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret;
}

inline void prework(){
for (int i=0;i<=9;i++) f[1][i][0] = 1;
for (int k=2,tmp=0;k<=28;k++) {
for (int i=0;i<=9;i++) {
for (int j=0;j<=9;j++) {
if (i == 4 && j == 9) f[k][i][1] += f[k-1][j][0];
else f[k][i][0] += f[k-1][j][0];
f[k][i][1] += f[k-1][j][1];
}
}
}
}

inline LL cal(LL w){
if (!w) return 0;
else {
int tot = 0, arr[20]; LL ret = 0, tmp = w, t2;
memset(arr,0,sizeof(arr));
while (w) arr[++tot] = w % 10, w /= 10;

for (int i=1;i<tot;i++) for (int j=1;j<=9;j++) ret += f[i][j][1];
for (int i=1;i<arr[tot];i++) ret += f[tot][i][1];
for (int i=tot-1;i;i--){
for (int j=0;j<arr[i];j++) ret += f[i][j][1];
if (arr[i+1] == 4 && arr[i] == 9) {
ret += tmp%(LL)(pow(10,i-1)+0.1)+1;
break;
}
}
return ret;
}
}

int main(){
prework();
while (T--) {
cout<<cal(a)<<endl;
}
return 0;
}


## 【BZOJ 1026】[SCOI2009] windy数

#include<iostream>
#include<cstdio>
#include<cstring>
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int MAXN = 20;

int f[MAXN][MAXN],a,b;

inline void prework(){
for (int i=0;i<=9;i++) f[1][i] = 1;
for (int k=2;k<=10;k++) {
for (int i=0;i<=9;i++) {
for (int j=i+2;j<=9;j++) f[k][i] += f[k-1][j];
for (int j=i-2;j>=0;j--) f[k][i] += f[k-1][j];
}
}
}

inline int cal(int w){
int tot=0,arr[MAXN],ret=0;
memset(arr,0,sizeof(arr));
while (w) arr[++tot] = w % 10, w /= 10;

for (int i=1;i<tot;i++) for (int j=1;j<=9;j++) ret += f[i][j];
for (int i=1;i<arr[tot];i++) ret += f[tot][i];
for (int i=tot-1;i>0;i--) {
for (int j=0;j<=arr[i]-(i==1?0:1);j++)if (abs(j-arr[i+1]) >= 2) ret += f[i][j];
if (abs(arr[i]-arr[i+1]) < 2) break;
}
return ret+(tot==1);
}

int main(){
prework();
scanf("%d%d",&a,&b);
printf("%d",cal(b)-cal(a-1));
return 0;
}