代码编织梦想

题意 :给个序列ci,表示每个i初始颜色是ci,问进行交换操作k次,最后序列颜色不变的排列有多少个。(n<=2e5,k<=1e9,有多球同色的情况)

Solution:
\quad 入手的话,可能我们会考虑交换操作和颜色的关系,交换两个同色的下标无意义,交换不同色的(1,2)(2,3)(3,1)试图去找环,发现并不能抵掉交换操作QAQ。
\quad 考虑朴素的置换环吧。先连边 i − > p i i->p_i i>pi(一开始pi就是1-n的升序排列)。显然初始有n个大小为1的置换环。
\quad 接下来看交换操作,交换两个pi,会使置换环数量+1/-1.
证明(参考官方题解):若交换的两数在同个环内,所在环会分裂成两个。对于 a 1 − > a 2 − > . . . a i . . − > a j . . . − > a n − > a 1 a_1->a_2->...a_i..->a_j...->a_n->a_1 a1>a2>...ai..>aj...>an>a1,若交换 p a i 和 p a j ,会变成 p_{a_i}和p_{a_j},会变成 paipaj,会变成a_1->a_2->…a_i->a_{j+1}->a_{j+2}…->a_n->a_1 和 和 a_j->a_{i+1}->a_{i+2}…->a_j$。
\quad 若两个数不在同一环内,所在的两个环会合并。显然吧,不证了。。
设k次操作后置换环数量为c,若最后排列要满足 n-c <=k且k-(n-c)%2==0.
前一个不等式表示,k不能小于必要操作次数,后一个式子表示不必要操作需要抵消,因为每次只能+1/-1,那显然不必要操作数要是偶数。(所谓必要就是用最少步骤将置换环数变成c个)。
\quad 现在考虑各种形态的排列如何满足最后每个i要符合对应的染色ci。考虑将每个i逐步加入。
\quad f i , j f_{i,j} fi,j表示1~i的排列形成了j个置换环的合法方案数(所谓合法就是每个i的染色都是ci).
\quad 有转移方程 f i , j = f i − 1 , j − 1 + f i − 1 , j ∗ ∑ k = 1 i − 1 [ c k = = c i ] f_{i,j}=f_{i-1,j-1} + f_{i-1,j}*\sum_{k=1}^{i-1}[c_k==c_i] fi,j=fi1,j1+fi1,jk=1i1[ck==ci]。解释一下,若i成自环,那i直接染ci,否则可以替换掉前面颜色是ci的位置。
然后这个式子可以启发式合并求,类似第一类斯特林数。
∑ i = 1 n f n , i x i = ∏ i = 1 n ( x + c n t i ) , c n t i 表示在 i 前面且颜色是 c i 的数量 \sum_{i=1}^nf_{n,i}x^i=\prod_{i=1}^n(x+cnt_i),cnt_i表示在i前面且颜色是ci的数量 i=1nfn,ixi=i=1n(x+cnti),cnti表示在i前面且颜色是ci的数量
\quad 证明的话,目前只会归纳法证。
考虑 ∏ i = 1 n ( x + c n t i ) \prod_{i=1}^n(x+cnt_i) i=1n(x+cnti),设 x k x^k xk的系数为f(n,k). ∏ i = 1 n − 1 ( x + c n t i ) \prod_{i=1}^{n-1}(x+cnt_i) i=1n1(x+cnti),设 x k x^k xk的系数为f(n-1,k),x^{k-1}的系数为f(n-1,k-1).
f ( n , k ) = f ( n − 1 , k − 1 ) + f ( n − 1 , k ) ∗ c n t n f(n,k)=f(n-1,k-1) + f(n-1,k)*cnt_n f(n,k)=f(n1,k1)+f(n1,k)cntn系数的转移式与上面计数的转移式相同,且f(i,0)=0.
PS:要从本质的置换环考虑😄。

const int N = 2e5+10;
int a[N],n,cnt[N],s[N],k;
Poly cal(int l,int r){
    if(l==r){
        return Poly{s[l],1};
    }
    int mid = (l+r)>>1;
    return mul(cal(l,mid),cal(mid+1,r));
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif  
    IOS;
    cin>>n>>k;
    _for(i,1,n) {
        cin>>a[i];
        s[i] = cnt[a[i]];
        cnt[a[i]]++;
    }
    Poly F = cal(1,n);
    F.resize(n+1,0);
    int ans = 0;
    _for(i,1,n){
        int t = n - i;
        if( t<=k && (k - t)%2==0 ) ans = (ans + F[i])%mod; 
    }
    cout<<ans;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_53688600/article/details/127277716

AtCoder Beginner Contest 234 题解(A-Ex)-爱代码爱编程

在我的博客内阅读。 A,B 略。 C 考虑将 K K K 二进制表示下的每个 1

第25期《AtCoder Beginner Contest 244 打比赛总结》-爱代码爱编程

又打了一场ABC。  AtCoder Beginner Contest 244 - AtCoderhttps://atcoder.jp/contests/abc244结果:A,B(300分)。 A题: A - Last Letter / Time Limit: 2 sec / Memory Limit: 1024 MB Score : 100 p

AtCoder Beginner Contest 246-爱代码爱编程

AtCoder Beginner Contest 246 文章目录 AtCoder Beginner Contest 246A - Four PointsB - Get CloserC - CouponD - 2-variable FunctionE - Bishop 2F - typewriterG - Game on Tree 3Ex -

AtCoder Beginner Contest 247 题解-爱代码爱编程

请看完后点个赞,谢谢​​​​​​​ A题 247A 直接覆盖就可以了,别忘了把第一位变成0 //AT247A 22-04-10 #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); stri

atcoder beginner contest 255 部分题解_山中一扶苏的博客-爱代码爱编程

本篇题解只是记录我的做题过程代码,不提供最优解 (另外这里所有的时间复杂度都只分析单个样例,不算 t t t的时间复杂度) A 点击此处查看对应的题目.本题设计算法:模拟 直接输出指定的点即可。

atcoder beginner contest 257_chels.的博客-爱代码爱编程

D - Jumping Takahashi 2 题目描述: 在二维平面上有n个蹦床,每个蹦床都有一个弹力值p,你自己有一个初始的弹跳能力S,从一个点蹦到另一个点的条件是 P i

atcoder beginner contest 255_chels.的博客-爱代码爱编程

C - ±1 Operation 1 题目描述: 给你一个等差数列,首项为A,公差为D,项数为N,问X和这N项中数字差的绝对值最小为多少 思路: 二分一下,找到离他最近的两项,求一个最小值就行 注意公差可能为负数,所以可以分情况讨论,或者可以将这N个数倒着看就成了公差为正数的一个等差数列 注意,如果二分的后找到大于等于x的位

atcoder beginner contest 258【比赛记录】_瘾ิۣۖิۣۖิۣۖิꦿ的博客-爱代码爱编程

        比赛过程非常不顺,D题INF开小了,wrong了好几发,还要边输入边操作时忘记处理不合理的情况了,心态崩溃,最后喜提掉分!!! ABC 模拟即可,注意B不要都错题,不要拐弯!!!C不要数组越界,自己RE了几发!!! D Trophy 贪心,枚举要玩的前缀1~i个,最后全部给第i个,找到最小值即可。 #include <bit

【abc】atcoder beginner contest 261 c++代码_chengor的博客-爱代码爱编程

A - Intersection #include<bits/stdc++.h> using namespace std; #define ll long long const int mo = 1e3; const int N = 1e5+5; int main() { ios::sync_with_stdio(false); cin.

atcoder beginner contest 262(abc262)a-ex 题解_cyl06的博客-爱代码爱编程

A - World Cup 我懒得分类讨论,直接枚举。 #include<bits/stdc++.h> #define Max(a,b) ((a<b)&&(a=b)) #define M

line verda programming contest (atcoder beginner contest 263) a~e 题解_goodcoder666的博客-爱代码爱编程

ABC263/LINE2022 A~E [A - Full House](https://atcoder.jp/contests/abc263/tasks/abc263_a)题目大意输入格式输出格式样例分析代码

atcoder beginner contest 265 题解 (a~d)_c2024xsc249的博客-爱代码爱编程

A - Apple Time Limit: 2 sec / Memory Limit: 1024 MB Score : 100

abc270 toyota motor corporation programming contest 2022(atcoder beginner contest 270) 题解_神奇的崔师傅的博客-爱代码爱编程

A - 1-2-4 Test 题意: 有三道题,分值分别为1,2,4,A做出了若干分的题目,B做出了若干分的题目,求他们总共做出了多少分的题目。 分析: 可以发现有几种关系: 解答: cout<<(a|b)<<endl;  B - Hammer 题意:x轴上有x,y,z三个点,从原点出发想要到达x点,y处有一

toyota motor corporation programming contest 2022(atcoder beginner contest 270) ab题解_三元湖有大锦鲤的博客-爱代码爱编程

A 1-2-4 Test 题意:有1、2、4分值的三道题,三位同学作答,第三位同学回答的题目是第一第二位同学至少一个人回答对的,问第三位同学最大得分。 分析:一开始不好入手,但是看到1,2,4,看到至少一个人回答出来的,

atcoder beginner contest 247_[abc247g] dream team-爱代码爱编程

AtCoder Beginner Contest 247 A - Move Right 右移一位,直接模拟。 void solve() { string s; cin >> s; s

nomura programming contest 2022(atcoder beginner contest 253)-爱代码爱编程

目录 C - Max - Min Query D - FizzBuzz Sum Hard C - Max - Min Query C - Max - Min Query 思路:map存,然后加减 注意:map存过的数即使,它的value变成0,它依然暂居迭代器的位置,但我们不需要value等于0的元素,所以及时erase掉即可。 拓展

atcoder beginner contest 258 a~ex 题解-爱代码爱编程

D - Trophy 题目大意 有一个游戏,由 N N