蒟蒻不想取名字

这个博客可以拿来放模板诶~

bzoj4652

这道题感觉非常优美……能有一个这么优美的题面和较高的思维难度真的不容易……

  为了表示方便,让我先讲一下两个符号。[a][a]表示如果aa为真,那么返回11,否则返回00; a⊥ba⊥b表示aa与bb互质。

  首先,我们需要考虑一个分数要成为纯循环小数需要满足什么条件。

  我们先来回想一下,我们是怎样使用除法来判断一个分数xyxy是否是纯循环小数的。显然我们是一路除下去,什么时候出现了相同的余数,那么这个数就是一个循环小数。如果第一个重复的余数是xx,那么这个数就是纯循环小数。这种方法实际上就是存在一个数l≠0l≠0,使得:

xkl≡x(mody)xkl≡x(mody)

  又由于题目要求值不重复,那么我们可以得到x⊥yx⊥y。所以,我们可以推出kl≡1(mody)kl≡1(mody)。所以我们只需k⊥yk⊥y即可。

  于是,我们实际上是要求这个式子:

=∑x=1n∑y=1m[x⊥y][y⊥k]∑y=1m[y⊥k]∑x=1n[x⊥y]∑x=1n∑y=1m[x⊥y][y⊥k]=∑y=1m[y⊥k]∑x=1n[x⊥y]

  用一下莫比乌斯反演,可以得到:

=∑y=1m[y⊥k]∑x=1n∑d|x,d|yμ(d)∑y=1m[y⊥k]∑d|ynμ(d)⌊nd⌋∑y=1m[y⊥k]∑x=1n∑d|x,d|yμ(d)=∑y=1m[y⊥k]∑d|ynμ(d)⌊nd⌋

  再通过换一下枚举顺序,可得:

==∑d=1nμ(d)⌊nd⌋∑y=1m[d | y][y⊥k]∑d=1nμ(d)⌊nd⌋∑i=1⌊md⌋[id⊥k]∑d=1n[d⊥k]μ(d)⌊nd⌋∑i=1⌊md⌋[i⊥k]∑d=1nμ(d)⌊nd⌋∑y=1m[d | y][y⊥k]=∑d=1nμ(d)⌊nd⌋∑i=1⌊md⌋[id⊥k]=∑d=1n[d⊥k]μ(d)⌊nd⌋∑i=1⌊md⌋[i⊥k]

  最后一步用了互质的一个性质,那就是[ab⊥c]=[a⊥c][b⊥c][ab⊥c]=[a⊥c][b⊥c]。这点应该很好理解吧。

  我们不妨设f(n,k)=∑ni=1[i⊥k]f(n,k)=∑i=1n[i⊥k],那么我们只要在O(1)O(1)的时间内求出ff,复杂度就是O(n)O(n),就可以得到8484分。实际上,我们可以得到一个式子:

f(n,k)=⌊nk⌋f(k,k)+f(nmodk,k)f(n,k)=⌊nk⌋f(k,k)+f(nmodk,k)

  这个应该也不难理解,因为[a⊥b]=[amodb⊥b][a⊥b]=[amodb⊥b]

  于是我们就可以对f(n,k)f(n,k)预处理出n≤kn≤k的值,每次求值就变成O(1)O(1)了。于是8484分到手了。

  我们考虑接下来该如何优化。由于⌊mx⌋⌊mx⌋只有m−−√m种取值,⌊nx⌋⌊nx⌋只有n√n种取值,于是我们显然可以分段求和。然后,我们就需要快速求出∑ni=1[i⊥k]μ(i)∑i=1n[i⊥k]μ(i)的值。

  不妨设g(n,k)=∑ni=1[i⊥k]μ(i)g(n,k)=∑i=1n[i⊥k]μ(i),我们来考虑一下这个函数如何快速求。我们先考虑kk的一个质因数pp,那么kk显然可以写成pcqpcq的形式。由于在[1,n][1,n]的范围中只有与kk互质的才是有效值,那么若x⊥kx⊥k,我们可以得到x⊥px⊥p并且x⊥qx⊥q。于是,我们可以考虑从x⊥qx⊥q的取值中减去xx不与pp互质的部分,就可以得到x⊥kx⊥k的部分。这里如果不懂的话可以自己画一个x⊥qx⊥q,x⊥px⊥p,x⊥kx⊥k的关系图理解一下。

  由于所有与qq互质的数一定可以写成pxy(y⊥q)pxy(y⊥q)的形式。那么我们需要减去的数一定满足x>0x>0。又由于当x>1x>1时μ(pxy)=0μ(pxy)=0,所以我们只需要考虑x=1x=1的情况即可。在这种情况下,我们需要考虑的数就是py(y⊥q)py(y⊥q)的形式,所以我们可以得到如下式子:

g(n,k)=∑i=1n[i⊥q]μ(i)−∑y=1⌊np⌋[py⊥q]μ(py)=g(n,q)−∑y=1⌊np⌋[y⊥q]μ(py)g(n,k)=∑i=1n[i⊥q]μ(i)−∑y=1⌊np⌋[py⊥q]μ(py)=g(n,q)−∑y=1⌊np⌋[y⊥q]μ(py)

  上面的最后一步是由于p⊥qp⊥q,所以py⊥qpy⊥q只需在保证y⊥qy⊥q即可。

  我们接着来考虑后一个式子。显然当p⊥yp⊥y的时候μ(py)=μ(p)μ(y)μ(py)=μ(p)μ(y),否则μ(py)=0μ(py)=0。于是,我们又得到了:

g(n,k)=g(n,q)−∑y=1⌊np⌋[y⊥p][y⊥q]μ(p)μ(y)=g(n,q)−μ(p)∑y=1⌊np⌋[y⊥k]μ(y)=g(n,q)+g(⌊np⌋,k)g(n,k)=g(n,q)−∑y=1⌊np⌋[y⊥p][y⊥q]μ(p)μ(y)=g(n,q)−μ(p)∑y=1⌊np⌋[y⊥k]μ(y)=g(n,q)+g(⌊np⌋,k)

  于是我们就可以递归求解了。容易发现边界情况就是n=0n=0或者k=1k=1。n=0n=0的时候直接返回00就可以了,k=1k=1的时候就是莫比乌斯函数的前缀和,用杜教筛求出来就可以了。由于每次递归要么nn会变成⌊np⌋⌊np⌋,有O(n√)O(n)种取值;要么pp少了一个质因数,有ω(k)ω(k)种取值,所以总共有O(ω(k)n√)O(ω(k)n)种取值,记忆化搜索即可。其中ω(k)ω(k)表示kk的不同的质因子数目。于是最后的总复杂度为O(ω(k)n√+n23)O(ω(k)n+n23),可以通过此题。

  两个细节:

  可以在递归求gg的时候不直接记kk,而是记录kk还剩下多少个质因数,方便存储;

  记忆化的时候可以开哈希链表存储,用mapmap也可以,或者干脆分n,mn,m以及小于、大于根号的情况存储也可以。

  第一次写这种题的题解,好像写得过于详细了(其实是因为我什么都不会),请大神们不要喷……

  下面贴代码:

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<map>

using namespace std;

#define long long long

#define to i*prime[j]

#define maxn 1000005

long n,m,k;

int p;

int miu[maxn];

int prime[maxn];

int sum[maxn];

int k_prf[10];

bool sift[maxn];

map<int,int> mp;

map<int,int> ms[10];

map<int,int> mt[10];

void init()

{

miu[1]=sum[1]=1;

for(int i=2;i<maxn;i++)

{

if(!sift[i])

{

prime[++p]=i;

miu[i]=-1;

}

sum[i]=sum[i-1]+miu[i];

for(int j=1;j<=p&&to<maxn;j++)

{

sift[to]=true;

if(i%prime[j]==0) 

{

miu[to]=0;

break;

}

else miu[to]=-miu[i];

}

}

int sum_miu(int x)

{

if(x<maxn) return sum[x];

if(mp.count(x)) return mp[x];

int ans=1;

for(int i=2,p;p<x;i=p+1)

{

p=x/(x/i);

ans-=sum_miu(x/i)*(p-i+1);

}

return mp[x]=ans;

}

long S(int x,int r)//sum_miu of 1~r coprime with the first x-th prmfactors of k

{

if(!x) return sum_miu(r);

if(r<=1) return r;

if(ms[x].count(r)) return ms[x][r];

return ms[x][r]=S(x-1,r)+S(x,r/k_prf[x]);

}

int T(int x,int r)//numbers of 1~r ...

{

if(!x) return r;

if(r<=1) return r;

if(mt[x].count(r)) return mt[x][r];

return mt[x][r]=T(x-1,r)-T(x-1,r/k_prf[x]);

}

int main()

{

init();

scanf("%lld%lld%lld",&n,&m,&k);

int kk=k;

p=0;

for(int i=1;kk>1;i++)

 {

if(kk%prime[i]==0) 

 {

k_prf[++p]=prime[i];

while(kk%prime[i]==0) 

kk/=prime[i];

}

 }

long ans=0ll;

for(int i=1,t;i<=n&&i<=m;i=t+1)

 {

t=min(m/(m/i),n/(n/i));

ans+=(n/i)*(S(p,t)-S(p,i-1))*T(p,m/i);

 }

printf("%lld",ans);

}


sdoi2016 储能表

很好的计数型数位dp,刷表法,一维表示阶段,半维限制范围,dp过程不断进行可行性剪枝

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#define F(i,j,n) for(int i=j;i<=n;i++)

#define D(i,j,n) for(int i=j;i>=n;i--)

#define ll long long

usingnamespacestd;

llt,n,m,k,p,ans,f[100][2][2][2],g[100][2][2][2],bin[100];

inlinellread()

{

llx=0,f=1;charch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

returnx*f;

}

intmain()

{

t=read();

while(t--)

{

n=read()-1;m=read()-1;k=read();p=read();

bin[0]=1;F(i,1,60)bin[i]=bin[i-1]*2%p;

ans=0;

memset(f,0,sizeof(f));memset(g,0,sizeof(g));

f[0][1][1][1]=1;

F(i,0,60)F(a,0,1)F(b,0,1)F(c,0,1)if(f[i][a][b][c])

{

lltn=n&(1ll<<(60-i))?1:0,tm=m&(1ll<<(60-i))?1:0,tk=k&(1ll<<(60-i))?1:0;

F(x,0,1)if(!a||x<=tn)F(y,0,1)if(!b||y<=tm)

{

intz=x^y;

if(c&&z<tk)continue;

intta=(a&&x==tn)?1:0,tb=(b&&y==tm)?1:0,tc=(c&&z==tk)?1:0;

(f[i+1][ta][tb][tc]+=f[i][a][b][c])%=p;

(g[i+1][ta][tb][tc]+=g[i][a][b][c])%=p;

if(z)(g[i+1][ta][tb][tc]+=bin[60-i]*f[i][a][b][c]%p)%=p;

}

}

F(a,0,1)F(b,0,1)F(c,0,1)ans=((ans+g[61][a][b][c]-k%p*f[61][a][b][c]%p)%p+p)%p;

printf("%lld\n",ans);

}

return0;

}


beijing2016 打字机

最近在看以前的题

这题和省选前集训的那道题有异曲同工之妙嘛

dp,最大的是所有可能中最小的、

嘛,过程还是比较套路

玄学过程也没啥好说的

天啊我竟然看到了yjq大爷的lofter!

嗯是不是该说点啥。。。

yjq您是我们的红太阳!

呃。。。

呃。。。

pku2774 Long Long Message

要知道,跟上一个肯定是比跟上上个的lcp更长的

可以手推一下

bzoj 2938

收获:

  1、AC自动机可以在建立fail时将一些不存在的儿子指针指向对应的位置。

  2、判断环时不要想当然地写个这样的版本:

bool dfs( int u ) {

    if( vis[u] ) return true;

    vis[u] = true;

    for( int t=0; t<g[u].size(); t++ ) {

        int v=g[u][t];

        if( dfs(v) ) return true;

    }

    vis[u] = false;

    return false;

}

原因大概是因为没有考虑下一个点可能已经处理过

它不是O(n)的,然后我就T了,搞了好久才弄好。

  3、存在一个无限长的不与给定pattern匹配的text,那么在该text上跑ac自动机会无限循环,反之一定会在有限的时间内结束。

/**************************************************************

    Problem: 2938

    User: idy002

    Language: C++

    Result: Accepted

    Time:40 ms

    Memory:2316 kb

****************************************************************/

 

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define maxn 60010

using namespace std;

 

int son[maxn][2], fail[maxn], ikey[maxn], ntot;

int vis[maxn], cir[maxn];

char str[maxn];

 

void insert( const char *P ) {

    int n=strlen(P);

    int u=0;

    for( int i=0; i<n; i++ ) {

        int c=P[i]-'0';

        if( !son[u][c] ) son[u][c] = ++ntot;

        u=son[u][c];

    }

    ikey[u] = true;

}

void build_fail() {

    queue<int> qu;

    for( int c=0; c<2; c++ ) {

        int v=son[0][c];

        if( !v ) continue;

        qu.push( v );

        fail[v] = 0;

    }

    while( !qu.empty() ) {

        int u=qu.front();

        qu.pop();

        for( int c=0; c<2; c++ ) {

            int v=son[u][c];

            int w=fail[u];

            if( !v ) {

                son[u][c] = son[fail[u]][c];

                continue;

            }

            while( w && !son[w][c] ) w=fail[w];

            fail[v] = son[w][c];

            ikey[v] |= ikey[fail[v]];

            qu.push( v );

        }

    }

}

void dfs( int u ) {

    vis[u] = true;

    for( int c=0; c<2; c++ ) {

        int v=son[u][c];

        if( cir[v] || ikey[v] ) continue;

        if( !vis[v] )

            dfs(v);

        else {

            printf( "TAK\n" );

            exit(0);

        }

    }

    cir[u] = true;

}

int main() {

    int n;

    scanf( "%d", &n );

    for( int i=0; i<n; i++ ) {

        scanf( "%s", str );

        insert( str );

    }

    build_fail();

    dfs( 0 );

    printf( "NIE\n" );

}


bzoj2818 枚举素数,发现可以用线性筛

bzoj2705 注意求欧拉函数只能用O(√n)的方法

bzoj3926 勇于用DFS,然后注意各种剪枝优化

bzoj2142 推出式子,约分化简,分解模数

bzoj1041 平方差见了要拆开,好推式子,通过gcd,可以枚举一些约数,也可以通互质指减小范围,平方数尽可能利用到根号n的枚举

bzoj2005 容斥

bzoj3209 数位dp很巧妙啊

bzoj2186 感觉是转化为一个关于m!的剩余系。。。也许做多了就熟练吧,get到一种较快的逆元线性求法。

Bzoj3122 就是先搞个等比数列,再求个逆元,再BGSG

Bzoj2257 裴蜀定理

Bzoj3738 同bzoj2142

Bzoj2119 利用原根将阶层转化为线性方程

Bzoj1951 [Sdoi2010]古代猪文

首先由欧拉定理易知当A与p互质时A^B %p=A^(B%φ(p) ) %p

这里p是一个质数 于是φ(p)=p-1=999911658

然后由于这个数不是质数 难以处理 我们将它分解质因数 然后对于每个质因数的解用中国剩余定理合并即可

然后就是999911658有一个很好的性质 999911658=2*3*4679*35617 每个质因数的次数都是1次

于是我们可以套用卢卡斯定理 预先处理出对于每个质因数的阶乘和阶乘的逆元即可

注意此题有个细节 就是欧拉定理中a与p必须互质 而当a=0(即G=p)时gcd(a,p)=p

所以有一组数据是专门卡这个地方的 这组数据是999911657 999911659 取模后是0^0 于是得到1 但是答案是0 

于是我们做一些处理 A^B %p=A^(B%φ(p)+φ(p) ) %p

这样就没问题了



裴蜀定理

说明了对任何整数a、b和它们的最大公约数d,关于未知数x和y的线性不定方程(称为裴蜀等式):若a,b是整数,且(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立

它的一个重要推论是:a,b互质充要条件是存在整数x,y使ax+by=1.

简言之,就是两瓶子倒水所能量出的最小体积是gcd