夏令营501-511NOIP训练18——高三楼

￡神魔★判官ぃ 2023-06-05 12:44 7阅读 0赞

传送门：[QAQQAQ][]

题意：定义矩阵A与矩阵B重复，当且仅当A可以通过任意次行列交换得到B，例如下图A,B即为合法矩阵

![1.jpg][]

现求对于$n\*n$的矩阵有多少个不重复的矩阵

数据范围：

对于10%的数据 N≤5；  
对于50%的数据 N≤150；  
对于100%的数据T≤5 N≤2,000。

思路：这题暴力都不会打啊。。。

既然是行列变换，那么我们就要从行列变换中找到一些不变量。

我们可以把矩阵看成描述一个两边点数均为$n$的二分图的邻接矩阵，那么我们行列交换就相当于把两个点“扭一下”，但图的本质是不会变的。

我们这里定义“本质”是指连通块回路（即从一个点出发开始搜，再次搜回这个点的路径块）的情况，因为无论我们怎么换点，这些连通块的总个数和各自点数都是不会变的。（因为每个点都引出两条边，所以一定有联通块）

所以我们就要构造二分图，使这些二分图的连通块不相同。

因为连通块无序，而且在$2\*n$的二分图中构成一个连通块至少要四个点，我们把它简化到一边：一边构成连通块的的点数至少为二

所以题目就转化成了将$n$正整数拆分成若干个大于等于二的自然数，无序，求方案数。

简单吧！可是这种神仙YY题鬼想得到。。。

代码：（因为无序，所以要和完全背包一样先枚举往里面加的数，再枚举总和，可以保证一个数加完以后就不会再被考虑）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int MOD=100000007;
     
    int dp[2020];
     
    int main()
    {
        int t,n;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            memset(dp,0,sizeof(dp));
            dp[0]=1;
            for(int i=2;i<=n;i++)
            {
                for(int j=i;j<=n;j++) dp[j]=(dp[j]+dp[j-i])%MOD;
            }
            cout<<dp[n]<<endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11291610.html

[QAQQAQ]: https://dev.xjoi.net/contest/1219/problem/3
[1.jpg]: https://dev.xjoi.net/images/problem/1750/1.jpg
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/2fac0c722cf04e4f8342128f01f97075.png