BZOJ4589: Hard Nim(FWT 快速幂)

BZOJ4589: Hard Nim(FWT 快速幂)。题意

主题素材链接

Description

Claris和NanoApe在玩石子游戏,他们有n堆石子,准绳如下:

  1. Claris和NanoApe多少人轮班拿石子,Claris先拿。

2.
每一回只可以从一群中取多少个,可将一群全取走,但不可能不取,获得结尾1颗石子的人制伏。

分歧的上马局面,决定了最后的胜球者,有些规模下先拿的Claris会赢,其他的规模Claris会负。

Claris很好奇,假使那n堆石子满意每堆石子的发端数量是不超过m的质数,何况她们都会遵从最优战略玩游戏,那么NanoApe能获胜的框框有多少种。

出于答案或然相当大,你只要求交给答案对10^9+7取模的值。

Description

闻明娱乐设计员vfleaking,近期迷上了Nim。普通的Nim游戏为:四个人张开娱乐,N堆石子,每一遍合能够取中间某一群的随便多少个,能够取完,但不可能不取。何人不能够取哪个人输。那一个娱乐是有必胜计策的。于是vfleaking决定写一个玩Nim游戏的阳台来坑游戏发烧友。
为了设计美丽一点的启幕局面,vfleaking用以下措施来找灵感:拿精湛多石子,把它们聚成一批一批的,对每一群编号1,2,3,4,…n,在堆与堆间连边,未有自环与重边,从随机堆到自由堆都独有独一一条路径可到达。然后他不停地拓宽如下操作:

1.随机选八个堆v,u,询问若在v到u间的路线上的石子堆中玩Nim游戏,是或不是有必胜计谋,若是有,vfleaking将会驰念将这几个石子堆作为开头局面之一,用来坑游戏者。
2.把堆v中的石子数变为k。

鉴于vfleaking太懒了,他无意本人入手了。请写个程序帮帮他啊。

迎接访问~原著出处——博客园-zhouzhendong

cabet888,Sol

神仙题Orzzzz

难题能够转正为从\(\leqslant M\)的质数中选出\个\和为\的方案数

诸有此类就好做多了

设\ = [x \text{是质数}]\)

\次异或FWT即可

迅猛幂优化一下,中间不用IFWT,最终转一遍就行(然而并不知道为什么)

哪位大佬教教小编那题的DP怎么写啊qwqqqq

死过可是去样例。。

#include<bits/stdc++.h>using namespace std;const int MAXN = (1 << 17) + 10, mod = 998244353, inv2 = 499122177;inline int read() {    char c = getchar(); int x = 0, f = 1;    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N, A[MAXN], B[MAXN], C[MAXN];int add(int x, int y) {    if(x + y < 0) return x + y + mod;    return x + y >= mod ? x + y - mod : x + y;}int mul(int x, int y) {    return 1ll * x * y % mod;}void FWTor(int *a, int opt) {    for(int mid = 1; mid < N; mid <<= 1)         for(int R = mid << 1, j = 0; j < N; j += R)            for(int k = 0; k < mid; k++)                 if a[j + k + mid] = add(a[j + k], a[j + k + mid]);                else a[j + k + mid] = add(a[j + k + mid], -a[j + k]);}void FWTand(int *a, int opt) {    for(int mid = 1; mid < N; mid <<= 1)         for(int R = mid << 1, j = 0; j < N; j += R)            for(int k = 0; k < mid; k++)                 if a[j + k] = add(a[j + k], a[j + k + mid]);                else a[j + k] = add(a[j + k], -a[j + k + mid]);}void FWTxor(int *a, int opt) {    for(int mid = 1; mid < N; mid <<= 1)         for(int R = mid << 1, j = 0; j < N; j += R)            for(int k = 0; k < mid; k++) {                int x = a[j + k], y = a[j + k + mid];                if a[j + k] = add, a[j + k + mid] = add;                else a[j + k] = mul, inv2), a[j + k + mid] = mul(add, inv2);                           }}int main() {    N = 1 << ;    for(int i = 0; i < N; i++) A[i] = read();    for(int i = 0; i < N; i++) B[i] = read();    FWTor; FWTor;    for(int i = 0; i < N; i++) C[i] = mul(A[i], B[i]);    FWTor; FWTor; FWTor;    for(int i = 0; i < N; i++) printf("%d ", C[i]); puts("");    FWTand; FWTand;    for(int i = 0; i < N; i++) C[i] = mul(A[i], B[i]);    FWTand; FWTand; FWTand;        for(int i = 0; i < N; i++) printf("%d ", C[i]); puts("");    FWTxor; FWTxor;    for(int i = 0; i < N; i++) C[i] = mul(A[i], B[i]);    FWTxor; FWTxor; FWTxor;        for(int i = 0; i < N; i++) printf("%d ", C[i]);    return 0;}

Input

输入文件包括多组数据,以EOF为末段。

对此每组数据:

共一行四个正整数n和m。

每组数据有1<=n<=10^9, 2<=m<=四千0。

不超过80组数据。

Input

 第一行三个数n,表示有微微堆石子。
接下去的一行,第i个数表示第i堆里有微微石子。
接下去n-1行,每行四个数v,u,代表v,u间有一条边平昔相接。
接下去二个数q,代表操作的个数。
接下去q行,每行起始有二个字符:
万一是Q,那么后边有四个数v,u,询问若在v到u间的门路上的石子堆中玩Nim游戏,是不是有必胜战术。
如假使C,那么前面有三个数v,k,代表把堆v中的石子数变为k。

对于100%的数据:
1≤N≤500000, 1≤Q≤陆仟00, 0≤任哪一天候每堆石子的个数≤32767
其中有30%的数据:
石子堆组成了一条链,那3个点会导致您DFS时爆栈(只怕你不要DFS?)。别的的多寡DFS目测不会爆。

瞩目:石子数的界定是0到INT_MAX

去知乎看该题解


发表评论

电子邮件地址不会被公开。 必填项已用*标注