UPD 7:29 今天要给大爷们讲课好方啊好方啊
UPD 10:30 终于讲完了……一路口胡过去 还好没有被肛
UPD 20:40 整个晚上都在写题解……没救了
开始跟着Dirak在BZOJ上做SDOI的题目了
数位DP套AC自动机，和BZOJ1030做法有点像。
$dp_{i,j,k}$ 表示走了 $i$ 步走到 $j$，$k$ 表示当前有没有已经比n小 的方案数
为了防止单词中前导零把一些可行的情况当做不可行 需要做两遍DP
一遍是统计长度比n小，先强制第一位不为0，
然后怎么搞都可以，最后求一下$\sum_{i=1}^{len_n}{\sum_{j=0}^{Cnt}{dp_{i,j,1}}}$
一遍是统计长度等于n，这就需要用到上面的dp方法了
最后求一下$\sum_{j=1}^{Cnt}{\sum_{k=0}^{1}{dp_{len_n,j,k}}}$
加一加就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
#define MOD 1000000007
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int Mxl=1205,M=105,L=1505;
struct Trie{
Trie *next[10],*fail;
bool fin;
}a[L];
char n[Mxl],s[L];
int m,Cnt,Ans;
int dp[Mxl][L][2];
void Insert(char *s){
int len=strlen(s);
Trie *now=a;
Rep(i,0,len-1){
if (!now->next[s[i]-'0']) now->next[s[i]-'0']=++Cnt+a;
now=now->next[s[i]-'0'];
}
now->fin=1;
}
queue<Trie*>q;
void Build(){
Rep(i,0,9){
Trie *&v=a->next[i];
if (v) v->fail=a,q.push(v);
else v=a;
}
while (!q.empty()){
Trie *u=q.front();q.pop();
Rep(i,0,9){
Trie *&v=u->next[i];
if (v){
q.push(v);
Trie *Fa=u->fail;
while (!Fa->next[i]) Fa=Fa->fail;
v->fail=Fa->next[i];
v->fin|=Fa->next[i]->fin;
}
else v=u->fail->next[i];
}
}
}
int main(){
scanf("%s",n+1);
m=IN();
Rep(i,1,m){
scanf("%s",s);
Insert(s);
}
Build();
int len=strlen(n+1);
Rep(i,1,9){
Trie *u=a->next[i];
if (!u->fin) dp[1][u-a][1]++;
}
Rep(i,2,len-1) Rep(j,0,Cnt){
if (a[j].fin) continue;
Rep(k,0,9){
Trie *u=a[j].next[k];
if (!u->fin) (dp[i][u-a][1]+=dp[i-1][j][1])%=MOD;
}
}
Rep(i,1,len-1) Rep(j,0,Cnt) (Ans+=dp[i][j][1])%=MOD;
memset(dp,0,sizeof dp);
Rep(i,1,n[1]-'1'){
Trie *u=a->next[i];
if (!u->fin) dp[1][u-a][1]++;
}
Trie *u=a->next[n[1]-'0'];
if (!u->fin) dp[1][u-a][0]++;
Rep(i,2,len) Rep(j,0,Cnt){
if (a[j].fin) continue;
if (dp[i-1][j][1]){
Rep(k,0,9){
Trie *u=a[j].next[k];
if (!u->fin) (dp[i][u-a][1]+=dp[i-1][j][1])%=MOD;
}
}
if (dp[i-1][j][0]){
Rep(k,0,n[i]-'1'){
Trie *u=a[j].next[k];
if (!u->fin) (dp[i][u-a][1]+=dp[i-1][j][0])%=MOD;
}
Trie *u=a[j].next[n[i]-'0'];
if (!u->fin) (dp[i][u-a][0]+=dp[i-1][j][0])%=MOD;
}
}
Rep(i,0,Cnt) (Ans+=dp[len][i][0])%=MOD,(Ans+=dp[len][i][1])%=MOD;
OUT(Ans);
}
大大的结论题（虽然这个结论你要是够强也推得出来）
首先，
$\sum_{i=1}^{N}{\sum_{j=1}^{M}{d(ij)}}=\sum_{i=1}^{N}{\sum_{j=1}^{M}{\lfloor\frac{N}{i}\rfloor\lfloor\frac{M}{j}\rfloor[gcd(i,j)=1]}}$
为什么呢？因为：
$d(nm)=\sum_{i\mid n}{\sum_{j\mid m}{[gcd(i,j)=1]}}$
那么为什么下面那个等于上面那个呢？
很显然左边的话上面的式子就是下面的式子的前缀和 不用证了
右边的话，考虑一对互质数 $i,j$，
它对上面式子的贡献显然就是$\lfloor\frac{N}{i}\rfloor\lfloor\frac{M}{j}\rfloor$
考虑它对下面式子的贡献：
因为 $i$的倍数出现了$\lfloor\frac{N}{i}\rfloor$次，它们每次出现的时候 $j$的倍数也都出现了$\lfloor\frac{M}{j}\rfloor$次
所以也是$\lfloor\frac{N}{i}\rfloor\lfloor\frac{M}{j}\rfloor$，和上面是一样的
现在我们来证明下面那个是对的
考虑一个质数 $p$,假设$N=N'*p^{k1},M=M'*p^{k2}$,
那么它对左边（即函数 $d$）的影响就是
没有这个质因数 $p$时的答案乘上了$k1+k2+1$
它对右边的影响就是没有$p$这个质因数时的答案乘上了
只有$p$这个质因数时 $i,j$ 互质的对数，这些数对就是
$(p^{k1},1),(p^{k1-1},1),(p^{k1-2},1),...,(1,1),...(1,p^{k2-1}),(1,p^{k2})$
一共$k1+k2+1$对
然而虽然已经知道了，但是我们还是不会做。
这该怎么办呢？
现在又来了一个公式：$e(i)=\sum_{d\mid i}{\mu(d)}$
其中当$i=1$时，$e(i)=1$,否则 $e(i)=0$；而$\mu(d)$是莫比乌斯函数
我们来证明一下：
因为对于任何一个 $d$，如果它有某个质因数的次数是≥2的，
那么$\mu(d)$就为0，对答案没有贡献。
所以就可以把 $i$的所有质因数的次数都消到1次，对答案没有影响
那么 $i$ 就被拆成了 $p_1*p_2*...p_k$，且 $p_1 \sim p_k$互不相同，所以
$e(i)=C_k^0*(-1)^0*1^{k}+C_k^1*(-1)^1*1^{k-1}+....+C_k^k*(-1)^k*1^0$
根据二项式定理，上面这坨 $=(-1+1)^k$
所以只有当 $k=0$即 $i=1$的时候 $e(i)=1$，其他时候$e(i)=0$
这样就证好了。然而这有什么卵用么？
当然有！！！！这样的话最上面那坨公式右边的就变成了：
$\sum_{i=1}^{n}{\sum_{j=1}^{m}{\sum_{d\mid gcd(i,j)}{\lfloor\frac{N}{i}\rfloor\lfloor\frac{M}{j}\rfloor\mu(d)}}}$
稍微换一下就变成了
$\sum_{d=1}^{min(n,m)}{\mu(d)\sum_{i=1}^{\lfloor\frac{N}{d}\rfloor}{\lfloor\frac{N}{id}\rfloor\sum_{j=1}^{\lfloor\frac{M}{d}\rfloor}{\lfloor\frac{M}{jd}\rfloor}}}$
右边这两坨还能换一下……就是
$\sum_{d=1}^{min(n,m)}{\mu(d)\sigma_0(\lfloor\frac{N}{d}\rfloor)\sigma_0(\lfloor\frac{M}{d}\rfloor)}$
其中$\sigma_0(i)=\sum_{d\mid i}{\lfloor\frac{i}{d}\rfloor}$，就是约数个数的前缀和。
然后$\mu(i)$是积性函数，约数个数也是积性函数。
于是就可以先欧拉筛法预处理，然后分块了，
每次询问$O(\sqrt{n}+\sqrt{m})$
终于写完了……我会告诉你我写了两个半小时么。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline int IN(){
int x=0,ch=getchar(),f=1;
while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
if (ch=='-'){f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
inline void OUT(ll x){
if (x<0) putchar('-'),x=-x;
if (x>=10) OUT(x/10),putchar(x%10+'0');
else putchar(x+'0');
}
const int N=50000;
int Mn[N+5],Mu[N+5],mp[N+5],mq[N+5],ys[N+5],p[N+5],Cnt,T;
ll Calc(int n,int m){
if (n>m) swap(n,m);
ll ret=0;
for (int tmp,d=1;d<=n;d=tmp+1){
tmp=min(n/(n/d),m/(m/d));
ret+=1ll*(Mu[tmp]-Mu[d-1])*ys[n/d]*ys[m/d];
}
return ret;
}
int main(){
ys[1]=1,Mu[1]=1;
Rep(i,2,N){
if (!Mn[i]){
p[Mn[i]=++Cnt]=i;
mp[i]=i,mq[i]=1;
Mu[i]=-1,ys[i]=2;
}
Rep(j,1,Cnt){
int k=i*p[j];
if (k>N) break;
if (Mn[i]==j){
Mn[k]=j;
mp[k]=mp[i]*p[j],mq[k]=mq[i]+1;
Mu[k]=0,ys[k]=ys[i/mp[i]]*(mq[k]+1);
break;
}
else{
Mn[k]=j;
mp[k]=p[j],mq[k]=1;
Mu[k]=-Mu[i],ys[k]=ys[i]*2;
}
}
}
Rep(i,2,N) ys[i]+=ys[i-1],Mu[i]+=Mu[i-1];
T=IN();
Rep(i,1,T){
int n=IN(),m=IN();
OUT(Calc(n,m)),putchar('\n');
}
}
Aug 31, 2022 02:03:57 PM
Bangladesh Education Board DPE has conducted the class 8th grade of Junior School Certificate Exam and Junior Dakhil Certificate Exam on 1st to 15th November 2022 at all centers in division wise under Ministry of Primary and Mass Education (MOPME), and the class 8th grade terminal examination tests are successfully conducted for all eligible JSC/JDC students for the academic year of 2022. Junior Certificate Result Barisal Board The Bangladesh government Minister of Secondary Education is going to announce the JSC Result 2022 in student wise for division students in education board wise, and the result documents will be submitted to the Prime Minister of the country after then the result with mark sheet will be announced to public to check the individual result.