DoorKickers的博客

博客

BZOJ3771瞎写

2020-03-16 17:45:01 By DoorKickers

题目大意

我们讲一个悲伤的故事。 从前有一个贫穷的樵夫在河边砍柴。 这时候河里出现了一个水神,夺过了他的斧头,说: “这把斧头,是不是你的?” 樵夫一看:“是啊是啊!” 水神把斧头扔在一边,又拿起一个东西问: “这把斧头,是不是你的?” 樵夫看不清楚,但又怕真的是自己的斧头,只好又答:“是啊是啊!” 水神又把手上的东西扔在一边,拿起第三个东西问: “这把斧头,是不是你的?” 樵夫还是看不清楚,但是他觉得再这样下去他就没法砍柴了。 于是他又一次答:“是啊是啊!真的是!” 水神看着他,哈哈大笑道: “你看看你现在的样子,真是丑陋!” 之后就消失了。 樵夫觉得很坑爹,他今天不仅没有砍到柴,还丢了一把斧头给那个水神。 于是他准备回家换一把斧头。 回家之后他才发现真正坑爹的事情才刚开始。 水神拿着的的确是他的斧头。 但是不一定是他拿出去的那把,还有可能是水神不知道怎么偷偷从他家里拿走的。 换句话说,水神可能拿走了他的一把,两把或者三把斧头。 樵夫觉得今天真是倒霉透了,但不管怎么样日子还得过。 他想统计他的损失。 樵夫的每一把斧头都有一个价值,不同斧头的价值不同。总损失就是丢掉的斧头价值和。 他想对于每个可能的总损失,计算有几种可能的方案。 注意:如果水神拿走了两把斧头a和b,(a,b)和(b,a)视为一种方案。拿走三把斧头时,(a,b,c),(b,c,a),(c,a,b),(c,b,a),(b,a,c),(a,c,b)视为一种方案。

随笔瞎写

考虑一个生成函数 A=a0+a1x+a2x2+a3x3++anxn 把系数看成方案数, 把指数看成价值

两个多项式的卷积为 C=A×B=i,jaibj 看一个简单的例子 A=2x+x2B=3x+2x2C=6x2+4x3+3x3+2x4=6x2+7x3+2x4 显然, 卷积后的多项式可以代表从A,B 里各选出一个物品, 然后总价值达到某一个数的方案数

这个题中, 我们要从A里选出两个物品, 就可以自己对自己进行卷积 A=2x+x2A×A=4x2+4x3+x4 但是存在一个物品被选中两次的情况

我们设B为每个物品取两次的情况 B=2x2+x4 显然, 最终答案为A×AB .

同理我们考虑从A中选3个物品, A×A×A= 发现可能会出现一个物品被选中多次的情况

枚举一下哪个物品被多选了, 设为x

发现可能会出现(x,x,x),(x,x,y),(y,x,x),(x,y,x) 这几种情况

我们设D=A×B

发现可以得到(x,x,x),(y,x,x) 这两种情况

我们可以把结果乘三, 但发现(x,x,x)减多了, 那就再加回来

C为选三个物品的情况, 再加回来两次就好了

最终答案是三种情况加起来, 又因为不同顺序算一种, 所以要除一下 A+A×AB2!+A×A×AA×B3+2C3!

答案就算出来了

用FFT或者NTT加速

复杂度是O(不会分析但好像能过把)

SB代码

/*
Date&Time: 2:37pm 3/16/2020]
*/

#include <bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 3e6 + 10;
const int mod = 998244353;
const int g = 3;

int omega[N], omegaInv[N], rev[N], ta[N], tta[N], tab[N], a[N], b[N], c[N];
int n;

inline int fp(int a, int n, int mod) 
{
    int res = 1;
    while (n)
    {
        if (n & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res % mod;
}

inline int inv(int x)
{
    return fp(x, mod - 2, mod);
}

inline void init(const int n)
{
    int k = 0;
    while ((1 << k) < n) k++;
    int x = fp(g, (mod - 1) / n, mod);
    omega[0] = omegaInv[0] = 1;
    for (int i = 1; i < n; i++)
    {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
        omega[i] = (omega[i - 1] * x) % mod;
        omegaInv[i] = inv(omega[i]);
    }
}

inline void ntt(int *a, const int n, int *omega)
{
    for (int i = 0; i < n; i++)
    {
        if (i > rev[i]) continue;
        swap(a[i], a[rev[i]]);
    }
    for (int l = 2; l <= n; l *= 2)
    {
        int m = l / 2;
        for (int *p = a; p != a + n; p += l)
        {
            for (int i = 0; i < m; i++)
            {
                int t = (omega[n / l * i] * p[m + i]) % mod;
                p[m + i] = (p[i] - t + mod) % mod;
                p[i] = (p[i] + t) % mod;
            }
        }
    }
}

inline void dft(int *a, const int n)
{
    ntt(a, n, omega);
}

inline void idft(int *a, const int n)
{
    ntt(a, n, omegaInv);
    int x = inv(n);
    for (int i = 0; i < n; i++)
        a[i] = (a[i] * x) % mod;
}

inline void poly_multiply(int *a1, int n1, int *a2, int n2)
{
    int n = 1;
    while (n < n1 + n2 + 2) n *= 2;
    init(n);
    dft(a1, n), dft(a2, n);
    for (int i = 0; i < n; i++)
        a1[i] = (a1[i] * a2[i]) % mod;
    idft(a1, n);
    idft(a2, n);
}

inline void poly_squred(int *a, int n)
{
    int n1 = 1;
    while (n1 < n * 2 + 2) n1 *= 2;
    init(n1);
    dft(a, n1);
    for (int i = 0; i < n1; i++)
        a[i] = (a[i] * a[i]) % mod;
    idft(a, n1);
}

inline void poly_plus(int *a1, int n1 , int *a2, int n2, bool fl)
{
    int n = max(n1, n2);
    for (int i = 0; i <= n; i++)
        a1[i] = fl ? (a1[i] + a2[i]) % mod : (a1[i] - a2[i] + mod) % mod;
}

inline void poly_devide(int *a, int n, int v)
{
    int x = inv(v);
    for (int i = 0; i <= n; i++)
        a[i] = (a[i] * x) % mod;
}

inline void poly_times(int *a, int n, int v)
{
    for (int i = 0; i <= n; i++)
        a[i] = (a[i] * v) % mod;
}

int ans[N];

inline void print_poly(int* a, int n) 
{
    for (int i = 0; i <= n; i++)
    {
        cout << a[i] << ' ';
    }
    cout << endl;
}

signed main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int siz = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        siz = max(siz, x * 3);

        a[x]++, b[x * 2]++, c[x * 3]++;
        ta[x]++, tta[x]++, tab[x]++;

    }
    poly_squred(ta, siz);
    poly_multiply(tta, siz, ta, siz);
    poly_multiply(tab, siz, b, siz);
    poly_times(tab, siz, 3);
    poly_times(c, siz, 2);
    poly_plus(ans, siz, a, siz, 1);
    poly_plus(ta, siz, b, siz, 0);
    poly_devide(ta, siz, 2);
    poly_plus(ans, siz, ta, siz, 1);
    poly_plus(tta, siz, tab, siz, 0);
    poly_plus(tta, siz, c, siz, 1);
    poly_devide(tta, siz, 6);
    poly_plus(ans, siz, tta, siz, 1);
    for (int i = 0; i <= siz; i++)
    {
        if (ans[i])
            cout << i << ' ' << ans[i] << endl;
    }
    return 0;
}
/*
AC
*/

OrzCgl OrzSqy Orzxsj

评论

  • 2020-03-16 17:46:39
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。