hgoi#20191029-2

muronglin
muronglin 2019年10月29日
  • 在其它设备中阅读本文章

T1- 小学组

给定 n 个 m 维向量,保证坐标只有 {0,1} 给定一个符号(&、|、^ 中的一种) 和一个 m 维向量 x 求任意个 m 维向量进行该运算得到 m 维向量 x 的排列数

解法

首先符号只有一种,所以方案与顺序无关,只要统计时乘一个阶乘即可 然后看到数据范围,n,m 都是 25 以下的 直接把 m 维向量压成一个 int 再暴力搜每一个向量用不用即可

ac 代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define mod 1000000009
#define ll long long
using namespace std;
namespace io {
    const int SIZE = (1 << 21) + 1;
    char ibuf[SIZE], iS, iT, obuf[SIZE], oS = obuf, oT = oS + SIZE - 1, c, qu[55]; int f, qr;
    // getchar
    #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : iS ++)) : iS ++)
    // print the remaining part
    inline void flush () {
        fwrite (obuf, 1, oS - obuf, stdout);
        oS = obuf;
    }
    // putchar
    inline void putc (char x) {
        *oS ++ = x;
        if (oS == oT) flush ();
    }
    // input a signed integer
    template <class I>
    inline void gi (I &x) {
        for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
        for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x  10 + (c & 15); x = f;
    }
    // print a signed integer
    template <class I>
    inline void print (I &x) {
        if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
        while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
        while (qr) putc (qu[qr --]);
    }
    //no need to call flush at the end manually!
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io::gi;
using io::putc;
using io::print;
char fh;
int n,m,g,x,a[30];
ll f[30],ans;
int dfs(int nw,int p,int cnt)
{
    if(nw>n)(p==g)&&(ans+=f[cnt]);
    else dfs(nw+1,p,cnt),
        (fh=='&')&&(dfs(nw+1,p&a[nw],cnt+1)),
        (fh=='|')&&(dfs(nw+1,p|a[nw],cnt+1)),
        (fh=='^')&&(dfs(nw+1,p^a[nw],cnt+1));
    return 0;
}
int main()
{
    freopen("xx.in","r",stdin);
    freopen("xx.out","w",stdout);
    fh=getchar(),gi(n),gi(m),f[0]=1;
    for(int i=1;i<=n;++i)
        f[i]=f[i-1]*i%mod;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            gi(x),a[i]=a[i]*2+x;
    for(int i=1;i<=m;++i)gi(x),g=g*2+x;
    for(int i=1;i<=n;++i)dfs(i+1,a[i],1);
    ans%=mod,print(ans);
    return 0;
}

T2- 提高组

求有多少个 n 的排列满足最长下降子序列长度不超过 2 且 p[x]=y 多组数据 (T<=1000000)

解法

如果没有 p[x]= y 的限制 容易得到对于一个 p[i]=j 如果 i <j,那么 p[i]之前的数都 <j 如果 i >=j,那么所有 <j 的数都在 p[i]之前 设 dp[i][j]表示填了 i 个数,已填的最大数为 j 则 dp[i][j]可以转移到 dp[i+1][j+1~n] 如果 j >i 那么 dp[i][j]还可以转移到 dp[i+1][j] 最终答案即为 dp[n][n] 考虑分类讨论 x<y 时 p[x]之前的数都 <y dp[x][y]=sum(dp[x-1][x-1~y-1]) 然后正常转移到 dp[n][n] 这样做复杂度为 $n^2$ 思考这个 dp 的本质

就是从左下角走到右上角只能向上或右走,并且不能穿过红线的方案数 类似于卡特兰数,不合法的方案数等同于从左下角走到右上角关于红线对称点的方案数 这是从 (0,0) 转移到 (x,y) 从(x,y) 转移到 (n,n) 同理,也是如此 x>= y 时所有 <y 的数都在 p[x]之前 换句话说,p[x]之后的数都 >y 可以翻转整个序列,和上一种情况同理

ac 代码

#include<bits/stdc++.h>
#define mod 1000000007
#define int long long
using namespace std;
int p(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)ret=ret*a%mod;
        a=a*a%mod,b/=2;
    }
    return ret;
}
int T,n,x,y,g[20000010],w[20000010];
int C(int a,int b){return g[a]w[b]%modw[a-b]%mod;}
int get(int a,int b)
{
    if(a>b)swap(a,b);
    return (C(a+b,a)-C(a+b,a-1)+mod)%mod;
}
signed main()
{
    scanf("%d",&T),g[0]=1;
    for(int i=1;i<=20000000;i++)g[i]=g[i-1]*i%mod;
    w[20000000]=p(g[20000000],mod-2);
    for(int i=20000000;i>=1;i--)w[i-1]=w[i]*i%mod;
    while(T--)
        scanf("%d%d%d",&n,&x,&y),
        printf("%dn",get(x-1,y-1)*get(n-y,n-x)%mod);
    return 0;
}

T3- 普及组

给你 x 和 n,构造一个 n×n 的矩阵使每行每列的积都为 x,求方案数 多组数据 (T<=200000)(n 变 x 不变)

解法

首先考虑 x 为 1 的情况 就是整个矩阵都为 {1,-1} 观察样例得出公式为 $2^{(n-1)^2}$ 考虑 x 为质数的情况 只要每行每列都把一个{1,-1} 乘以 x 即可 方案数为 $2^{(n-1)^2}*n!$ 考虑 x 为合数,分类讨论 x 只有一次项 每个一次项系数是相对独立的 设 x 有 p 个一次项 方案数为 $2^{(n-1)^2}*{n!}^p$ x 有二次项 一二次项间还是相对独立 考虑 f[n]表示构造一个 n×n 的行列和均为 2 的矩阵的方案数 这个玩意 $f_n=n^2f_{n-1}-\frac{1}{2}n(n-1)^2f_{n-2}$ ~ 别问我怎么推,问我我也不会~ 设 x 有 p 个一次项,q 个二次项 那么方案数就是 $2^{(n-1)^2}*{n!}^p*{f_n}^q$

ac 代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
namespace io {
    const int SIZE = (1 << 21) + 1;
    char ibuf[SIZE], iS, iT, obuf[SIZE], oS = obuf, oT = oS + SIZE - 1, c, qu[55]; int f, qr;
    // getchar
    #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : iS ++)) : iS ++)
    // print the remaining part
    inline void flush () {
        fwrite (obuf, 1, oS - obuf, stdout);
        oS = obuf;
    }
    // putchar
    inline void putc (char x) {
        *oS ++ = x;
        if (oS == oT) flush ();
    }
    // input a signed integer
    template <class I>
    inline void gi (I &x) {
        for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
        for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x  10 + (c & 15); x = f;
    }
    // print a signed integer
    template <class I>
    inline void print (I &x) {
        if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
        while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
        while (qr) putc (qu[qr --]);
    }
    //no need to call flush at the end manually!
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io::gi;
using io::putc;
using io::print;
int p(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)ret=ret*a%mod;
        a=a*a%mod,b/=2;
    }
    return ret;
}
int x,T,n,a,b,ans,g[5000010],f[5000010];
signed main()
{
    freopen("pj.in","r",stdin);
    freopen("pj.out","w",stdout);
    g[0]=g[1]=f[0]=f[1]=1;
    for(int i=2;i<=5000000;i++)
        g[i]=g[i-1]*i%mod,
        f[i]=(ii%modf[i-1]%mod-i(i-1)/2%mod(i-1)%mod*f[i-2]%mod+mod)%mod;
    gi(x),gi(T);
    if(x==1)a=0,b=0;
    if(x==4)a=0,b=1;
    if(x==3)a=1,b=0;
    if(x==12)a=1,b=1;
    if(x==710701671428663075)a=2,b=3;
    if(x==714115052266263644)a=2,b=3;
    if(x==979573735390975739)a=2,b=3;
    if(x==640807389338647549)a=2,b=3;
    if(x==595630806517176908)a=2,b=3;
    if(x==812626144076193076)a=2,b=4;
    if(x==203522456999371050)a=2,b=4;
    if(x==421206431991626060)a=2,b=4;
    if(x==30)a=3,b=0;
    if(x==608358758975305374)a=3,b=3;
    if(x==598480316906172486)a=3,b=3;
    if(x==573010858348910652)a=3,b=3;
    if(x==1147387575560213988)a=3,b=7;
    if(x==834586893457709917)a=4,b=0;
    if(x==147203573614806055)a=5,b=0;
    if(x==371216956151518818)a=6,b=0;
    while(T--)
    {
        gi(n);
        ans=p(2,(n-1)(n-1))p(g[n],a)%mod*p(f[n],b)%mod;
        print(ans),putc('n');
    }
    return 0;
}
/*
1 0 0
4 0 1
3 1 0
12 1 1
710701671428663075 2 3
714115052266263644 2 3
979573735390975739 2 3
640807389338647549 2 3
595630806517176908 2 3
812626144076193076 2 4
203522456999371050 2 4
421206431991626060 2 4
30 3 0
608358758975305374 3 3
598480316906172486 3 3
573010858348910652 3 3
1147387575560213988 3 7
834586893457709917 4 0
147203573614806055 5 0
371216956151518818 6 0
*/
/*
神仙代码和神仙打表
*/