51nod 最近刷题 简要题解

时间：2022-06-04 00:23:35

51nod 1564

由于数据是随机的，可以证明，对于每一个数，向左或右找比它小的数，长度是logn级别的

考虑枚举最大值

注意，对于每一个最大值，如果直接用2个循环枚举左右端点的话，理论是lognlogn级别的，但是还是很容易被卡的，换成贪心，用2个指针指着左右端点，每一次移动我们往数大的那个方向移动

代码：

  //File Name: nod1564.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月10日 星期一 19时59分32秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#define LL long long

using namespace std;

const int MAXN =  + ;

const LL INF = (<<);

LL a[MAXN],ans[MAXN];

int l[MAXN],r[MAXN];

void solve(int n){

    l[] = ;

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

        l[i] = i;

        while(l[i] >  && a[l[i]-] <= a[i])

            l[i] = l[l[i]-];

    }

    r[n] = n;

    for(int i=n-;i>;i--){

        r[i] = i;

        while(r[i] < n && a[r[i]+] < a[i])

            r[i] = r[r[i]+];

    }

    memset(ans,,sizeof ans);

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

        LL mi1 = a[i];

/*

        for(int j=i;j>=l[i];j--){

            mi1 = min(mi1,a[j]);

            LL mi2 = mi1;

            for(int k=i;k<=r[i];k++){

                mi2 = min(mi2,a[k]);

                ans[k-j+1] = max(ans[k-j+1],a[i] * mi2);

            }

        }

*/

        int j = i,k = i;

        while(true){

            ans[k-j+] = max(ans[k-j+],mi1 * a[i]);

            if(j == l[i] && k == r[i]) break;

            else if(j == l[i] && k < r[i])

                k+=,mi1 = min(mi1,a[k]);

            else if(j > l[i] && k == r[i])

                j-=,mi1 = min(mi1,a[j]);

            else{

                if(a[j-] >= a[k+])

                    j-=,mi1 = min(mi1,a[j]);

                else

                    k+=,mi1 = min(mi1,a[k]);

            }

        }

    }

    for(int i=n-;i>=;i--)

        ans[i] = max(ans[i],ans[i+]);

}

int main(){

    int n;

    scanf("%d",&n);

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

        scanf("%lld",a + i);

    solve(n);

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

        printf("%lld\n",ans[i]);

    return ;

}

51nod 1375

给出n个数，问从中找出刚好k个数或者任意个数，使得这些数的gcd = 1的方案数

枚举gcd，mobius反演下就可以了

代码：

  //File Name: nod1375.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月10日 星期一 13时28分47秒

#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <string.h>

#define LL long long

using namespace std;

const int MOD = ;

const int MAXN =  + ;

const int N =  + ;

int s[MAXN],K;

int mu[MAXN],prime[MAXN];

bool check[MAXN];

LL p2[N],jie[N];

LL qp(LL x,LL y){

    LL res = ;

    for(;y>;y>>=){

        if(y & ) res = res * x % MOD;

        x = x * x % MOD;

    }

    return res;

}

LL C(LL x,LL y){

    if(y <  || y > x) return ;

    if(y ==  || y == x) return ;

    return jie[x] * qp(jie[y] * jie[x-y] % MOD,MOD - ) % MOD;

}

void mobius(){

    memset(check,false,sizeof check);

    mu[] = ;

    int tot = ;

    for(int i=;i<MAXN;i++){

        if(!check[i]){

            prime[tot++] = i;

            mu[i] = -;

        }

        for(int j=;j<tot;j++){

            if(i * prime[j] >= MAXN) break;

            check[i * prime[j]] = true;

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

                mu[i * prime[j]] = ;

                break;

            }

            else{

                mu[i * prime[j]] = -mu[i];

            }

        }

    }

}

void init(){

    p2[] = jie[] = ;

    for(int i=;i<N;i++){

        p2[i] = p2[i-] *  % MOD;

        jie[i] = jie[i-] * i % MOD;

    }

    mobius();

}

LL cal(int sum){

    if(K == -) return p2[sum] - ;

    return C(sum,K);

}

LL solve(int n,int ma){

    LL ans = ;

    for(int k=;k<=ma;k++){

        int sum = ;

        for(int i=k;i<=ma;i+=k)

            sum += s[i];

        ans = (ans + mu[k] * cal(sum) + MOD) % MOD;

    }

    return ans;

}

int main(){

    init();

    int n,ma = ;

    scanf("%d %d",&n,&K);

    for(int i=,u;i<n;i++){

        scanf("%d",&u);

        ma = max(ma,u);

        s[u]++;

    }

    printf("%lld\n",solve(n,ma));

    return ;

}

51nod 1269

简单容斥，求组合数的时候C(n，m) % p,虽然n是10^16级别的，但是p是素数，m才20左右，直接暴力求就可以了

  //File Name: nod1269.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月10日 星期一 13时11分23秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#define LL long long

using namespace std;

const int MOD = (int)1e9 + ;

int inv[];

LL a[];

LL qp(LL x,LL y){

    LL res = ;

    for(;y>;y>>=){

        if(y & ) res = res * x % MOD;

        x = x * x % MOD;

    }

    return res;

}

LL C(LL x,LL y){

    if(x < y || y < ) return ;

    if(y == x || y == ) return ;

    LL ans = ;

    for(int i=;i<y;i++){

        ans = (x - i) % MOD * inv[y - i] % MOD * ans % MOD;

    }

//    printf("x = %lld y = %lld ans = %lld\n",x,y,ans);

    return ans;

}

LL solve(int n,LL s){

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

        inv[i] = qp(i,MOD - );

    LL ans = ;

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

        LL now = ;

        int num = ;

        for(int j=;j<n;j++){

            if(i & ( << j)){

                num++;

                now += a[j] + ;

            }

        }

        LL tmp = C(s - now + n -,n - );

        if(num & ) ans = (ans - tmp + MOD) % MOD;

        else ans = (ans + tmp) % MOD;

    }

    return ans;

}

int main(){

    LL s;

    int n;

    scanf("%d %lld",&n,&s);

    for(int i=;i<n;i++) scanf("%lld",a + i);

    cout << solve(n,s) << endl;

    return ;

}

51nod  1407

i表示集合的状态

f(i)表示i & x= i的x的个数，即i是x的子集

可以分治求f

然后容斥下就可以

  //File Name: nod1407.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月09日 星期日 22时04分55秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#define LL long long

using namespace std;

const int MAXN =  << ;

const int MOD = (int)1e9 + ;

int f[MAXN];

LL p2[MAXN];

void init(){

    p2[] = ;

    for(int i=;i<MAXN;i++)

        p2[i] = p2[i-] *  % MOD;

}

void cal(int pre,int i){

    if(i < ) return ;

    cal(pre,i-);

    cal(pre+(<<i),i-);

    for(int j=;j<(<<i);j++)

        (f[pre+j] += f[pre+(<<i)+j] )%=MOD;

}

LL solve(int n){

    cal(,);

//    for(int i=0;i<=10;i++)

//        cout << f[i] << endl;

    LL ans = ;

    for(int i=,s;i<(<<);i++){

        s = ;

        for(int j=;j<;j++)

            if(i & (<<j)) s++;

        LL tmp = (p2[f[i]] -  + MOD) % MOD;

        if(s & ) ans = (ans - tmp + MOD) % MOD;

        else ans = (ans + tmp) % MOD;

    }

    return ans;

}

int main(){

    init();

    int n;

    scanf("%d",&n);

    for(int i=,a;i<n;i++){

        scanf("%d",&a);

        f[a]++;

    }

    cout << solve(n) << endl;

    return ;

}

51nod 1406

与上一道题一样

  //File Name: nod1406.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月09日 星期日 11时53分29秒

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

using namespace std;

int f[<<];

void solve(int pre,int i){

    if(i < ) return ;

    solve(pre,i-);

    solve(pre+(<<i),i-);

    for(int j=;j<(<<i);j++)

        f[pre+j] += f[pre+(<<i)+j];

}

int main(){

    int n;

    scanf("%d",&n);

    for(int i=,u;i<n;i++){

        scanf("%d",&u);

        f[u]++;

    }

    solve(,);

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

        printf("%d\n",f[i]);

    return ;

}

51nod  1362

枚举向右下方走的次数，可以得到公式

对于公式，有一问题，就是要求的是C(n,m)%p,这个时候p也可能是合数，n是10^9级别，但是m是1000级别的

注意到需要消除的数都是与p的gcd大于1的，所以只需要考虑p的质因子，将与p互质的部分直接求逆元计算，不互质的部分维护成质因子的幂次，从分子中减去即可。

O(nlogp)级别

  //File Name: nod1362.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月09日 星期日 19时14分21秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <vector>

#define LL long long

using namespace std;

vector<int> dive;

int s[];

LL mod;

LL qp(LL x,LL y){

    LL res = ;

    for(;y>;y>>=){

        if(y & ) res = res * x % mod;

        x = x * x % mod;

    }

    return res;

}

LL ext_gcd(LL a,LL b,LL &x,LL &y){

    if(a ==  && b == ) return -;

    if(b == ){x = ;y = ;return a;}

    LL d = ext_gcd(b,a%b,y,x);

    y -= a / b * x;

    return d;

}

LL inv(LL a,LL n){

    LL x,y;

    LL d = ext_gcd(a,n,x,y);

    if(d == ) return (x % n + n) % n;

    return -;

}

void cal_dive(LL p){

    dive.clear();

    for(int i=;i*i<=p;i++){

        if(p % i == ){

            dive.push_back(i);

            while(p % i == ) p /= i;

        }

    }

    if(p > ) dive.push_back(p);

    sort(dive.begin(),dive.end());

}

LL fact(LL x,int f){

    for(int i=;i<dive.size();i++){

        while(x % dive[i] == ){

            s[i]+=f;

            x /= dive[i];

        }

    }

    if(f == -) return inv(x,mod);

    return x;

}

LL cal(LL l,LL r,LL a,LL b,LL c){

    memset(s,,sizeof s);

    LL ans = fact(a,-);

    for(int i=;i<=b;i++)

        ans = ans * fact(i,-) % mod;

    for(int i=;i<=c;i++)

        ans = ans * fact(i,-) % mod;

    for(LL i=l;i<=r;i++)

        ans = ans * fact(i,) % mod;

    for(int i=;i<dive.size();i++){

        ans = ans * qp(dive[i],s[i]) % mod;

    }

    return ans;

}

LL solve(LL n,LL m){

    LL ans = ;

    LL ma = min(n,m);

    cal_dive(mod);

    for(int c=;c<=ma;c++){

        ans = (ans + cal(m-c+,m-c++n,n+,c,n-c)) % mod;

    }

    return ans;

}

int main(){

    LL n,m;

    cin >> n >> m >> mod;

    cout << solve(n,m) << endl;

    return ;

}

51nod 1197

由于每次跳跃都是*2的，字符串实际上可以划分成若干条链的组合，每一条链都是logn长度的

再加个矩阵乘法

  //File Name: nod1197.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月08日 星期六 20时18分58秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#define LL long long

using namespace std;

const int MAXN =  + ;

const int MOD = (int)1e9 + ;

const int N = ;

int f[MAXN][N],len[N],g[N];

struct matrix_t{

    LL x[N][N];

    matrix_t(int v){

        memset(x,,sizeof(x));

        for(int i=;i<=N;i++) x[i][i] = v;

    }

    matrix_t operator*(const matrix_t &r){

        matrix_t p();

        for(int k=;k<=N;k++){

            for(int i=;i<=N;i++){

                if(x[i][k] == ) continue;

                for(int j=;j<=N;j++){

                    p.x[i][j] += x[i][k] * r.x[k][j] % MOD;

                    p.x[i][j] %= MOD;

                }

            }

        }

        return p;

    }

    matrix_t power(LL p){

        matrix_t r(),a = *this;

        for(;p;p>>=){

            if(p & ) r = r * a;

            a = a * a;

        }

        return r;

    }

};

LL solve(int n,LL m){

    f[][] = ;

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

        f[i][] = ;

        for(int j=;j<=;j++)

            f[i][j] = (0LL + f[i-][j] + f[i/][j-]) % MOD;

    }

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

        len[i] = (0LL + f[n][i] - f[n/][i] + MOD) % MOD;

    matrix_t mat();

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

        mat.x[][i] = len[i];

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

        mat.x[i][i-] = ;

    g[] = ;

    for(int i=;i<N;i++)

        for(int j=;j<= && j <= i;j++)

            g[i] = (0LL + g[i] + 1LL * g[i-j] * len[j] % MOD) % MOD;

    if(m < N) return g[m];

    mat = mat.power(m - );

    LL ans = ;

    for(int i=;i<N;i++)

        ans = (0LL + ans + mat.x[][i] * g[N - i] % MOD) % MOD;

    return ans;

}

int main(){

    int n;

    LL m;

    cin >> n >> m;

    cout << solve(n,m) <<endl;

    return ;

}

51nod 1251

枚举出现最大频率的那个频率，对于剩下的容斥就可以，发现对于枚举i，后面的复杂度是n/i

所以n / 1 + n / 2 + n / 3 + ... = O(nlogn)

  //File Name: nod1251.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月08日 星期六 14时39分39秒

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#define LL long long

using namespace std;

const int MAXN =  + ;

const int MOD = (int)1e9 + ;

LL jie[MAXN],inv[MAXN];

LL qp(LL x,LL y){

    LL res = ;

    for(;y;y>>=){

        if(y & ) res = res * x % MOD;

        x =x * x % MOD;

    }

    return res;

}

void init(){

    jie[] = ;

    for(int i=;i<MAXN;i++)

        jie[i] = jie[i-] * i % MOD;

    for(int i=;i<MAXN;i++)

        inv[i] = qp(jie[i],MOD - );

}

LL solve(int n,int m){

    if(m == ) return ;

    LL ans = ,tmp;

    for(int i=,ma;i<=n;i++){

        ma = (n - i) / i;

        for(int j=;j<=ma;j++){

            if(m -  < j) continue;

            tmp = jie[n-(j+)*i+m-]*inv[m-]%MOD*inv[n-(j+)*i]%MOD;

            tmp = tmp*jie[m-]%MOD*inv[j]%MOD*inv[m--j]%MOD;

            if(j & ) ans = (ans - tmp + MOD) % MOD;

            else ans = (ans + tmp) % MOD;

        }

    }

    return ans * m % MOD;

}

int main(){

    init();

    int t;

    scanf("%d",&t);

    while(t--){

        int n,m;

        scanf("%d %d",&n,&m);

        printf("%lld\n",solve(n,m));

    }

    return ;

}

51nod 1668

推下dp公式，矩阵乘法

  //File Name: nod1668.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月04日 星期二 16时04分05秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <vector>

#define LL long long

using namespace std;

const int N = ;

const int MOD = (int)1e9 + ;

int g[];

struct matrix_t{

    LL x[N+][N+];

    matrix_t(int v = ){

        memset(x,,sizeof x);

        for(int i=;i<=N;i++) x[i][i] = v;

    }

    matrix_t operator*(const matrix_t &r){

        matrix_t p();

        for(int k=;k<=N;k++){

            for(int i=;i<=N;i++){

                if(x[i][k] == ) continue;

                for(int j=;j<=N;j++){

                    (p.x[i][j] += x[i][k] * r.x[k][j] % MOD) %= MOD;

                }

            }

        }

        return p;

    }

    matrix_t power(LL p){

        matrix_t r(),a = *this;

        for(;p;p>>=){

            if(p & ) r = r * a;

            a = a * a;

        }

        return r;

    }

};

LL solve(LL n){

    g[] = ,g[] = ,g[] = ,g[] = ;

    if(n <= ) return g[n];

    matrix_t mat();

    mat.x[][] = mat.x[][] = mat.x[][] = ;

    mat.x[][] = mat.x[][] = mat.x[][] = ;

    mat = mat.power(n - );

    LL ans = mat.x[][] * g[] % MOD + mat.x[][] * g[] % MOD +

        mat.x[][] * g[] % MOD + mat.x[][] * g[] % MOD;

    return ans % MOD;

}

int main(){

    LL n;

    cin >> n;

    cout << solve(n) << endl;

    return ;

}

51nod 1309

求出a中不同的排列有P种

考虑每个数ai会在哪些排列中产生贡献，设a中比M大的数有k个，一个小于等于M的数ai能产生贡献当且仅当ai在排列中的位置在这k个数之前，即对于这k+1个数，ai的位置在最前，由于ai 与这k个数都不相同，这样的概率是1 / (k+1) ,所以ai可以产生贡献的排列有P / (k+1)  个，设a中 <= M 的数的和是S，则答案是

S * P / (k + 1)

先统计出来，对于每一个询问，2分得到答案

  //File Name: nod1309.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月05日 星期三 13时22分11秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#include <map>

#define LL long long

#define fir first

#define sec second

using namespace std;

const int MAXN = ;

const int MOD = (int)1e9 + ;

int a[MAXN];

map<int,LL> pre_s,ans;

map<int,int> pre_num;

LL P,jie[MAXN];

LL qp(LL x,LL y){

    LL res = ;

    for(;y>;y>>=){

        if(y & ) res = res * x % MOD;

        x = x * x % MOD;

    }

    return res;

}

int bs(int l,int r,int x){

    if(a[l] > x) return -;

    if(a[r] <= x) return a[r];

    while(r - l > ){

        int mid = l + r >> ;

        if(a[mid] <= x) l = mid;

        else r = mid;

    }

    return a[l];

}

void solve(int n,int q){

    jie[] = ;

    for(int i=;i<MAXN;i++) jie[i] = jie[i-] * i % MOD;

    sort(a,a+n);

    P = jie[n];

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

        pre_s[a[i]] += a[i];

        pre_num[a[i]]++;

    }

    for(map<int,int>::iterator it=pre_num.begin();it!=pre_num.end();it++)

        P = P * qp(jie[it->sec],MOD - ) % MOD;

//    cout << P << endl;

    for(map<int,int>::iterator pre=pre_num.begin(),it;pre!=pre_num.end();pre++){

        it = ++pre;

        --pre;

        if(it==pre_num.end()) break;

        pre_num[it->fir] += pre_num[pre->fir];

//        cout << it->fir << " " << pre_num[it->fir] << endl;

    }

    for(map<int,LL>::iterator pre=pre_s.begin(),it;pre!=pre_s.end();pre++){

        it = ++pre;

        --pre;

        if(it == pre_s.end()) break;

        (pre_s[it->fir] += pre_s[pre->fir]) %= MOD;

//        cout << it->fir << " " << pre_s[it->fir] << endl;

    }

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

        ans[a[i]] = pre_s[a[i]] * P % MOD * qp(n-pre_num[a[i]]+,MOD - ) % MOD;

//        cout << a[i] << " " << pre_s[a[i]] << " " << n - pre_num[a[i]] + 1 <<endl;

    }

    for(int i=,x;i<q;i++){

        scanf("%d",&x);

        x = bs(,n-,x);

//        cout << x << endl;

        if(x == -) puts("");

        else printf("%lld\n",ans[x]);

    }

}

int main(){

    int n,q;

    scanf("%d %d",&n,&q);

    for(int i=;i<n;i++) scanf("%d",a + i);

    solve(n,q);

    return ;

}

51nod 1667

把甲的数字写成Li+xi的形式，乙的写成Ri-yi的形式，整理后发现，其实要求的是：

x1 + x2 + ... + xn < S ，0 <= xi <= MAi 这种形式，S和MAi都是常数

容斥就可以了

  //File Name: nod1667.cpp

  //Author: long

  //Mail: 736726758@qq.com

  //Created Time: 2016年10月04日 星期二 20时22分27秒

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <iostream>

#define LL long long

using namespace std;

const int MOD = (int)1e9 + ;

const LL INF = ;

int l[],r[],k1,k2;

LL A,inv[],ma[];

LL qp(LL x,LL y){

    LL res = ;

    for(;y>;y>>=){

        if(y & ) res = res * x % MOD;

        x = x * x % MOD;

    }

    return res;

}

LL C(LL x,LL y){

    if(x < y || y < ) return ;

    if(y ==  || y == x) return ;

    LL res = ;

    for(LL i=;i<y;i++)

        res = res * (x - i) % MOD * inv[y-i] % MOD;

//    cout << x << " " << y << endl;

//    cout << res << endl;

    return res;

}

LL cal(int n){

    if(A < ) return ;

    LL res = ,s,tmp;

    for(int i=,num;i<(<<n);i++){

        num = ,s = ;

        for(int j=;j<n;j++){

            if(i & (<<j)){

                num++;

                s += ma[j] + ;

            }

        }

        tmp = C(A-s+n-,n-);

        if(num & ) (res = res - tmp + MOD) %= MOD;

        else (res += tmp) %= MOD;

    }

//    if(res < 0) cout << "fff " << endl;

    return res;

}

void solve(){

    LL ansl = ,ansg = ,anseq = ,sum = ;

    A = ;

    for(int i=;i<k1;i++) A -= l[i];

    for(int i=k1;i<k1+k2;i++) A += r[i];

    anseq = cal(k1+k2);

    A--;

    ansl = cal(k1+k2+);

    A = ;

    for(int i=;i<k1;i++) A += r[i];

    for(int i=k1;i<k1+k2;i++) A -= l[i];

    A--;

    ansg = cal(k1+k2+);

    for(int i=;i<k1+k2;i++){

        sum = sum * (r[i] - l[i] + ) % MOD;

    }

    sum = qp(sum,MOD - );

    ansl = ansl * sum % MOD;

    ansg = ansg * sum % MOD;

    anseq = anseq * sum % MOD;

    printf("%lld %lld %lld\n",ansg,anseq,ansl);

}

int main(){

    for(int i=;i<;i++) inv[i] = qp(i,MOD - );

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&k1);

        for(int i=;i<k1;i++)

            scanf("%d %d",&l[i],&r[i]),ma[i] = r[i] - l[i];

        scanf("%d",&k2);

        for(int i=k1;i<k1+k2;i++)

            scanf("%d %d",&l[i],&r[i]),ma[i] = r[i] - l[i];

        ma[k1+k2] = INF;

        solve();

    }

    return ;

}

相关文章