BZOJ4589: Hard Nim(FWT 快速冪)

来源:https://www.cnblogs.com/zwfymqz/archive/2018/11/29/10040817.html
-Advertisement-
Play Games

題意 "題目鏈接" Sol 神仙題Orzzzz 題目可以轉化為從$\leqslant M$的質數中選出$N$個$xor$和為$0$的方案數 這樣就好做多了 設$f(x) = [x \text{是質數}]$ $n$次異或FWT即可 快速冪優化一下,中間不用IFWT,最後轉一次就行(~~然而並不知道為什 ...


題意

題目鏈接

Sol

神仙題Orzzzz

題目可以轉化為從\(\leqslant M\)的質數中選出\(N\)\(xor\)和為\(0\)的方案數

這樣就好做多了

\(f(x) = [x \text{是質數}]\)

\(n\)次異或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(opt == 1) 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(opt == 1) 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(opt == 1) a[j + k] = add(x, y), a[j + k + mid] = add(x, -y);
                else a[j + k] = mul(add(x, y), inv2), a[j + k + mid] = mul(add(x, -y), inv2);               
            }

}
int main() {
    N = 1 << (read());
    for(int i = 0; i < N; i++) A[i] = read();
    for(int i = 0; i < N; i++) B[i] = read();
    FWTor(A, 1); FWTor(B, 1);
    for(int i = 0; i < N; i++) C[i] = mul(A[i], B[i]);
    FWTor(C, -1); FWTor(A, -1); FWTor(B, -1);
    for(int i = 0; i < N; i++) printf("%d ", C[i]); puts("");
    FWTand(A, 1); FWTand(B, 1);
    for(int i = 0; i < N; i++) C[i] = mul(A[i], B[i]);
    FWTand(C, -1); FWTand(A, -1); FWTand(B, -1);    
    for(int i = 0; i < N; i++) printf("%d ", C[i]); puts("");
    FWTxor(A, 1); FWTxor(B, 1);
    for(int i = 0; i < N; i++) C[i] = mul(A[i], B[i]);
    FWTxor(C, -1); FWTxor(A, -1); FWTxor(B, -1);    
    for(int i = 0; i < N; i++) printf("%d ", C[i]);
    return 0;
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1, int 整數 2. str 字元串 3. bool 布爾值 4. list 列表. 一般存放大量的數據 ["門神xxxx", "風扇哥xxxx", 元素] 5. tuple 元組. 只讀列表, 只能看啥也不能幹. (元素, 元素) 6. dict 字典. {"風扇哥":"王偉哲", "wlh" ...
  • python元編程,使用__setatt__,__getattribute__,__delattr__等特殊方法實現定製類 ...
  • 摘要:本文主要對Java這門編程語言進行簡單的介紹。 Java簡介 說明 Java語言歷時十多年,已發展成為人類電腦史上影響深遠的編程語言,從某種程度上來看,它甚至超出了編程語言的範疇,成為一種開發平臺,一種開發規範。Java語言所崇尚的開源、自由等精神,吸引了全世界無數優秀的程式員。事實是,從人 ...
  • 1.管道 進程間通信(IPC)方式二:管道(不推薦使用,瞭解即可),埠易導致數據不安全的情況出現。 2.共用數據 進程之間數據共用的模塊之一Manager模塊(少用): 進程間數據是獨立的,可以藉助於隊列或管道實現通信,二者都是基於消息傳遞的雖然進程間數據獨立,但可以通過Manager實現數據共用 ...
  • 一、input()函數 在 Python 中,使用內置函數 input()可以接收用戶的鍵盤輸入。 input()函數的基本用法如 下: 其中,variable 為保存輸入結果的變數,雙引號內的文字用於提示要輸入的內容。 二、print()函數預設的情況下,在Python中,使用內置的print() ...
  • 一:EL表達式 1.概述:在jsp開發中,為了獲取Servlet域對象中存儲的數據,經常要寫很多java代碼,這樣的做法會使JSP頁面混亂,難以維護,為此,在JSP2.0規範中提供了EL表達式。它是Expression Language的縮寫。 2.語法:${表達式} 2.1內置對象: 2.1.1獲 ...
  • 一、引言 官網文檔:http://www.mybatis.org/generator/index.html 通過使用官方提供的mapper自動生成工具,mybatis-generator-core-1.3.2來自動生成po類和mapper映射文件。 作用:mybatis官方提供逆向工程,可以使用它通 ...
  • 1. 什麼是列表 定義: 能裝對象的對象 在python中使用 [] 來描述列表, 內部元素用逗號隔開. 對數據類型沒有要求 列表存在索引和切片. 和字元串是一樣的. 2. 相關的增刪改查操作 添加: 1. append() 追加 2. insert(位置, 元素) 插入指定元素到指定位置 刪除: ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...