【ZOJ】3874 Permutation Graph 【FFT+CDQ分治】

2024-09-05 14:18

本文主要是介绍【ZOJ】3874 Permutation Graph 【FFT+CDQ分治】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门:【ZOJ】3874 Permutation Graph

题目分析:

容易知道一个个连通块内部的标号都是连续的,否则一定会有另一个连通块向这个连通块建边,或者这个连通块向另一个连通块建边。而且从左到右左边的连通块内最大的标号小于右边连通块内最小的标号。

然后我们可以构造dp方程:

dp[n]=n!i!dp[ni]

容易发现右边存在一个卷积,由于给的素数正好是费马素数,所以可以用 NTT 来求卷积,保证精度。因为我们要求所有的dp值,因此我们要用 CDQ 分治优化。

my code:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )const int P = 786433 ;
const int MAXN = 262144 ;
const int g = 10 ;LL power ( int a , int b , LL res = 1 ) {for ( LL tmp = a ; b ; b >>= 1 , tmp = tmp * tmp % P ) if ( b & 1 ) res = res * tmp % P ;return res ;
}void NTT ( LL y[] , int n , int rev ) {LL inv = power ( n , P - 2 ) , wn , w , t ;for ( int i = 1 , j , k , t ; i < n ; ++ i ) {for ( j = 0 , k = n >> 1 , t = i ; k ; k >>= 1 , t >>= 1 ) j = j << 1 | t & 1 ;if ( i < j ) swap ( y[i] , y[j] ) ;}for ( int s = 2 , ds = 1 , k , i ; s <= n ; ds = s , s <<= 1 ) {wn = power ( g , ( P - 1 ) / s ) ;if ( rev == -1 ) wn = power ( wn , P - 2 ) ;for ( k = 0 ; k < n ; k += s ) {for ( i = k , w = 1 ; i < k + ds ; ++ i , w = w * wn % P ) {y[i + ds] = ( y[i] - ( t = w * y[i + ds] % P ) + P ) % P ;y[i] = ( y[i] + t ) % P ;}}}if ( rev == -1 ) for ( int i = 0 ; i < n ; ++ i ) y[i] = y[i] * inv % P ;
}LL x1[MAXN] , x2[MAXN] ;
LL f[MAXN] , dp[MAXN] ;void cdq ( int l , int r ) {if ( l + 1 == r ) return ;int m = ( l + r ) >> 1 , n = 1 ;cdq ( l , m ) ;while ( n < r - l + 1 ) n <<= 1 ;for ( int i = 0 ; i < m - l ; ++ i ) x1[i] = dp[i + l] ;for ( int i = m - l ; i < n ; ++ i ) x1[i] = 0 ;for ( int i = 0 ; i < n ; ++ i ) x2[i] = f[i] ;NTT ( x1 , n , 1 ) ;NTT ( x2 , n , 1 ) ;for ( int i = 0 ; i < n ; ++ i ) x1[i] = x1[i] * x2[i] % P ;NTT ( x1 , n , -1 ) ;for ( int i = m ; i < r ; ++ i ) dp[i] = ( dp[i] - x1[i - l] + P ) % P ;cdq ( m , r ) ;
}void preprocess () {f[0] = 1 ;for ( int i = 1 ; i < MAXN ; ++ i ) {f[i] = f[i - 1] * ( LL ) i % P ;dp[i] = f[i] ;}cdq ( 1 , 100001 ) ;//for ( int i = 1 ; i <= 10 ; ++ i ) printf ( "%lld\n" , dp[i] ) ;
}void solve () {int x , c , n ;int ans = 1 ;scanf ( "%*d%d" , &n ) ;for ( int i = 1 ; i <= n ; ++ i ) {scanf ( "%d" , &x ) ;int minv = 0x3f3f3f3f , maxv = 0 ;for ( int j = 0 ; j < x ; ++ j ) {scanf ( "%d" , &c ) ;minv = min ( c , minv ) ;maxv = max ( c , maxv ) ;}if ( maxv - minv + 1 != x ) ans = 0 ;ans = ans * dp[x] % P ;}printf ( "%d\n" , ans ) ;
}int main () {int T ;preprocess () ;scanf ( "%d" , &T ) ;for ( int i = 1 ; i <= T ; ++ i ) solve () ;return 0 ;
}

这篇关于【ZOJ】3874 Permutation Graph 【FFT+CDQ分治】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139194

相关文章

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

zoj 4624

题目分析:有两排灯,每排n个,每个灯亮的概率为p,每个灯之间互不影响,亮了的灯不再灭,问两排中,每排有大于等于m个灯亮的概率。 设dp[ i ][ j ]为第一排亮了i个灯,第二排亮了j个灯,距离目标状态的期望天数。显然 i >= m ,j >= m时 , dp[ i ][ j ] = 0 。 状态转移 : 第一排亮了a个灯,a 在[ 0 , n - i] 之间,第二排亮了b个灯 , b 在

zoj 3228 ac自动机

给出一个字符串和若干个单词,问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现,1为不可重叠出现。 Sample Input ab 2 0 ab 1 ab abababac 2 0 aba 1 aba abcdefghijklmnopqrstuvwxyz 3 0 abc 1 def 1 jmn Sample Output Case 1 1 1 Case 2

ZOJ Monthly, August 2014小记

最近太忙太忙,只能抽时间写几道简单题。不过我倒是明白要想水平提高不看题解是最好的了。 A  我只能死找规律了,无法证明 int a[50002][2] ;vector< vector<int> > gmax , gmin ;int main(){int n , i , j , k , cmax , cmin ;while(cin>>n){/* g

图神经网络框架DGL实现Graph Attention Network (GAT)笔记

参考列表: [1]深入理解图注意力机制 [2]DGL官方学习教程一 ——基础操作&消息传递 [3]Cora数据集介绍+python读取 一、DGL实现GAT分类机器学习论文 程序摘自[1],该程序实现了利用图神经网络框架——DGL,实现图注意网络(GAT)。应用demo为对机器学习论文数据集——Cora,对论文所属类别进行分类。(下图摘自[3]) 1. 程序 Ubuntu:18.04

SIGMOD-24概览Part7: Industry Session (Graph Data Management)

👇BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance 🏛机构:字节 ➡️领域: Information systems → Data management systemsStorage management 📚摘要:介绍了字节新提出的ByteGraph 3.0(BG3)模型,用来处理大规模图结构数据 背景

ZOJ 3324 Machine(线段树区间合并)

这道题网上很多代码是错误的,由于后台数据水,他们可以AC。 比如这组数据 10 3 p 0 9 r 0 5 r 6 9 输出应该是 0 1 1 所以有的人直接记录该区间是否被覆盖过的方法是错误的 正确方法应该是记录这段区间的最小高度(就是最接近初始位置的高度),和最小高度对应的最长左区间和右区间 开一个sum记录这段区间最小高度的块数,min_v 记录该区间最小高度 cover