JZOJ 4425 Fenwit

发表于 | 分类于 |

考虑 FWT 的快速幂，\(O(\log T)\) 貌似接受不了，来个扩欧。

但是 \(2\) 貌似没逆元，不过可以把模数换成 \(2^M \cdot P\)，最后把得到的结果直接除以 \(2^M\)。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cmath>
#include <cstdio>
#define add(x,y) (x + y >= mod ? x + y - mod : x + y)
#define dec(x,y) (x < y ? x - y + mod : x - y)
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int M = 18;
const int N = 1 << 18;
int n,m,p,t,phi,b[M + 5];
long long mod,f[N + 5],g[N + 5];
inline long long fmul(long long a,long long b)
{
    return (a * b - (long long)((long double)a / mod * b) * mod + mod) % mod;
}
inline long long fpow(long long a,int b)
{
    long long ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = fmul(ret,a)),a = fmul(a,a);
    return ret;
}
inline void fwt(long long *a,int type)
{
    for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
        for(register int i = 0;i < n;i += w)
            for(register int j = 0;j < m;++j)
            {
                long long t = a[i | j | m];
                a[i | j | m] = dec(a[i | j],t),
                a[i | j] = add(a[i | j],t);
            }
    if(type == -1)
    	for(register int i = 0;i < n;++i)
    		a[i] /= n;
}
int calc(int n)
{
    int ret = 1;
    for(register int i = 2;i * i <= n && n > 1;++i)
    {
        if(!(n % i))
            ret *= i - 1,n /= i;
        for(;!(n % i);ret *= i,n /= i);
    }
    n > 1 && (ret *= n - 1);
    return ret;
}
int read()
{
    long long x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';ch = gc());
    for(;ch >= '0' && ch <= '9';ch = gc())
    {
        x = 10 * x + (ch ^ '0');
        x >= phi && (w |= 1,x %= phi);
    }
    w && (x += phi);
    return x;
}
int main()
{
    read(m),read(p),n = 1 << m,mod = (long long)p * n,phi = calc(p),t = read();
    for(register int i = 0;i < n;++i)
    	read(f[i]),f[i] %= mod;
    for(register int i = 0;i <= m + 1;++i)
    	read(b[i]),b[i] %= mod;
    for(register int i = 0;i < n;++i)
    	g[i] = b[__builtin_popcount(i)];
    fwt(f,1),fwt(g,1);
    for(register int i = 0;i < n;++i)
    	f[i] = fmul(f[i],fpow(g[i],t));
    fwt(f,-1);
    for(register int i = 0;i < n;++i)
    	printf("%lld\n",f[i]);
}