hdu5530
2024-08-24 19:58:57
分治ntt
考虑从添加i,放在j位置,那么1->j是一个连通块,j+1->i和1->j不连通,那么我们可以列出式子dp[i]=∑j=1->i dp[i-j]*A(i-1,j-1)*j^2
dp[i]表示i个数的答案
然后化简一下就可以分治ntt了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + , P = ;
int n, k;
ll a[N], b[N], fac[N], inv[N], facinv[N], dp[N];
ll power(ll x, ll t)
{
ll ret = ;
for(; t; t >>= , x = x * x % P) if(t & ) ret = ret * x % P;
return ret;
}
void ntt(ll *a, int f)
{
for(int i = ; i < n; ++i)
{
int t = ;
for(int j = ; j < k; ++j) if(i >> j & ) t |= << (k - j - );
if(i < t) swap(a[i], a[t]);
}
for(int l = ; l <= n; l <<= )
{
ll w = power(, f == ? (P - ) / l : P - - (P - ) / l);
int m = l >> ;
for(int i = ; i < n; i += l)
{
ll t = ;
for(int k = ; k < m; ++k, t = t * w % P)
{
ll x = a[i + k], y = t * a[i + m + k];
a[i + k] = (x + y) % P;
a[i + m + k] = ((x - y) % P + P) % P;
}
}
}
if(f == -)
{
ll inv = power(n, P - );
for(int i = ; i < n; ++i) a[i] = a[i] * inv % P;
}
}
void cdq(int l, int r)
{
if(l == r) return;
int mid = (l + r) >> ;
cdq(l, mid);
n = ;
k = ;
while(n <= r - l + ) n <<= , ++k;
for(int i = ; i < n; ++i) a[i] = b[i] = ;
for(int i = l; i <= mid; ++i) a[i - l] = dp[i] * facinv[i] % P;
for(int i = ; i <= r - l; ++i) b[i] = (ll)i * i % P;
ntt(a, );
ntt(b, );
for(int i = ; i < n; ++i) a[i] = a[i] * b[i] % P;
ntt(a, -);
for(int i = mid + ; i <= r; ++i) dp[i] = (dp[i] + a[i - l] * fac[i - ] % P) % P;
cdq(mid + , r);
}
int main()
{
inv[] = inv[] = facinv[] = fac[] = ;
for(int i = ; i < N; ++i)
{
if(i != ) inv[i] = (P - P / i) * inv[P % i] % P;
facinv[i] = facinv[i - ] * inv[i] % P;
fac[i] = fac[i - ] * i % P;
}
dp[] = ;
cdq(, );
while(scanf("%d", &n) != EOF)
{ printf("%lld\n", dp[n]);
}
return ;
}
最新文章
- PHP中的数据库一、MySQL优化策略综述
- 【JS】键盘鼠标事件
- map容器的使用
- sql server 2000通过机器名可以连,通过ip连不上的问题
- Windows Phone的简单学习
- RabbitMQ(四) -- Routing
- java个人总结
- [poj3666]Making the Grade(DP/左偏树)
- 注意事项: Oracle Not Exists 及 Not In 使用
- MVC框架是什么
- php开发通用采集程序
- Python 2.7 学习笔记 基本语法和函数定义
- python解决接口测试获取手机验证码问题
- Scrum 冲刺 第七日
- Windows 10 IoT Core 17093 for Insider 版本更新
- Linux文本处理三剑客之grep
- java一些必会算法
- OO第1~3次作业总结
- 简单的贝叶斯分类器的python实现
- Go语言fmt库的print函数源码解析
热门文章
- LeetCode – Copy List with Random Pointer
- 【Sprint2 每日Scrum】 第一天(4.22)Sprint2计划会议成果
- 【每日Scrum】第二天(4.12) TD学生助手Sprint1站立会议
- 使用Python处理Excel文件的一些代码示例
- Django-extra的用法
- Attempting to write a row[5] in the range [0,394] that is already written to disk.
- 通过串口工具下发指令的Python脚本
- 2018.11.23-day27 面向对象(大总结)
- 使用注解来构造IoC容器-转
- 设置port转发来訪问Virtualbox里linux中的站点