非常好的推式子的题 用到了很多知识点 推式子， 先交换 i   j  目的是把K放到外面来    后面先卷积预处理 得到p[j]   然后继续推式子 利用 得到   瞎卷一波就可以了。 注意一下    k−j   可能是负数，所以要倍长一下 要么三模数NTT，要么拆系数FFT FFT   更快些    #include <algorithm> #include <cstdio> #include <cstring> #include<iostream> using namespace std; int mo...

链接 https://blog.csdn.net/semiwaker/article/details/70054247  多项式入门  

https://www.oj.swust.edu.cn/problem/show/2781      式子很好推 很明显卷积即可 可以使用 NTT或者拆系数FFT 这里使用的是NTT #include <algorithm> #include <cstdio> #include <cstring> #include<iostream> using namespace std; int mod=1e9+7; namespace Math { inline int pw(int base, int p, const in...

Q - Cutting Game POJ - 2311 两个人在玩游戏。游戏规则如下：准备一张分成W x H的格子的长方形纸张，参与游戏的两个人轮流沿着格子的边界线切割纸张，水平或者垂直的奖纸张切割成两个部分。切割了n次之后就得到了n+1张纸，每次都选择切得的某一张纸再次进行切割。首先切出只有一个格子的纸张（1 x 1的各自组成的纸张）的一方获胜。 Input 输入包含多组测试样例。每组测试样例包含两个整数W和H(2 <= W, H <= 200)，分别表示纸张的长和宽。 Output 对于每个测试样例输出一行：如果先手必胜输出"WIN"，否则输出...

       本蒟蒻想要给大家写一篇尽可能详细的树上点分治的文章，以便刚入门的各位能够理解树上点分治，就不用像我一样在网上看了十几篇大佬的文章后还很蒙逼了（我太菜了QAQ），那么，我们就进入正题吧！        首先安利一波Guess_Ha大佬的树上点分治！        树上点分治主要解决有关树上路径统计的问题，我们这里以洛谷上的P3806 【模板】点分治1作为例题。        题目大意：有一棵树，m个询问，每次询问树上有没有两个点之间的路径长度为k。        根据树上点分治这个名字，那么我们自然就要分治啦，怎么分？题目只给了一棵树，于是我们就分这颗树，树上点分治的...

题目描述 对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。 输入输出格式 输入格式：   输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。   输出格式：   输出包含m行，依次为删除每个元素之前，逆序对的个数。   输入输出样例 输入样例#1： 复制 5 4 1 5 3 4 2 5 1 4 2 输出样例#...

题目背景https://www.luogu.org/problemnew/show/P3810 这是一道模板题 可以使用bitset，CDQ分治，K-DTree等方式解决。 题目描述                     输入输出样例 输入样例#1： 复制 10 3 3 3 3 2 3 3 2 3 1 3 1 1 3 1 2 1 3 1 1 1 2 1 2 2 1 3 2 1 2 1 输出样例#1： 复制 3 1 3 0 1 0 1 0 0 1 说明 1≤n≤100000,1≤k≤200000 1 \leq n \leq 100000, 1...

参考 https://www.luogu.org/problemnew/solution/CF1156D D. 0-1-Tree time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output You are given a tree (an undirected connected acyclic graph) consisting of nn vertices and n−1n−1 edges. A number i...

D. Neko and Aki's Prank time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, ...

The rules of Sith Tournament are well known to everyone. n Sith take part in the Tournament. The Tournament starts with the random choice of two Sith who will fight in the first battle. As one of them loses, his place is taken by the next randomly chosen Sith who didn't fight before. Does it need to...

题目描述 有一个长度为 nnn 的序列，xht37 现在想分块维护它。 PinkRabbit 要求他只准将序列分成 PRPRPR 种长度的块。 NaCly_Fish 要求他只准将序列分成 NFNFNF 种长度的块。 同一个人可能会要求 xht37 多次相同的块长。 xht37 想同时满足 PinkRabbit 和 NaCly_Fish 要求，只好使用两个人都允许的长度分块。 xht37 想知道，有多少种不同的分块方案，答案对 109+710 ^ 9 + 710​9​​+7 取模。 输入格式 第一行一个正整数 nnn，表示序列的长度。 第二行一个正整数 PRPRPR，表示 Pi...

请参考 https://www.cnblogs.com/Troywar/p/9078013.html  「常系数齐次线性递推」——矩阵快速幂的优化 https://blog.csdn.net/corsica6/article/details/82696715   常系数齐次线性递推优化矩阵快速幂-bzoj4161-4944 https://www.luogu.org/blog/Zhang-RQ/chang-ji-shuo-ji-ci-xian-xing-di-tui-chu-tan    常系数齐次线性递推初探    

链接：https://ac.nowcoder.com/acm/problem/20146 来源：牛客网   题目描述 脸哥最近在玩一款神奇的游戏，这个游戏里有 n 件装备，每件装备有 m 个属性，用向量zi(aj ,.....,am) 表示  (1 ≤ i ≤ n; 1 ≤ j ≤ m)，每个装备需要花费 ci，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。 对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。 严格的定义是，如果脸哥买了 zi1,......

链接：https://ac.nowcoder.com/acm/problem/19928 来源：牛客网   时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述 传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。  本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可...