T1考场上想到是个数学，用介乘减什么东西，然后打表找规律1h，没紧张度又花1h调了调高精，
还有1h多然后写了写T2T3的暴力，T2想到了做过的一道模拟42的T1，但没细想，所以bitset没想到
以为A了T1不会垫底，所以很放松，还要提升
先看了skyh博客，没看懂，
引用百度百科：
令
是
的一个错排，如果每个元素都不在其对应下标的位置上，即
，那么这种排列称为错位排列，或错排、重排（Derangement）。
我们从分析1 2 3 4的错排开始：1 2 3 4的错排有:4 3 2 1，4 1 2 3，4 3 1 2，3 4 1 2，3 4 2 1，2 4 1 3，2 1 4 3，3 1 4 2，2 3 4 1。第一列是4分别与123互换位置，其余两个元素错排。1 2 3 4->4 3 2 1，1 2 3 4->3 4 1 2，1 2 3 4-> 2 1 4 3第2列是4分别与312（123的一个错排）的每一个数互换3 1 2 4->4 1 2 3，3 1 2 4->3 4 2 1，3 1 2 4->3 1 4 2第三列则是由另一个错排231和4换位而得到2 3 1 4->4 3 1 2，2 3 1 4->2 4 1 3，2 3 1 4->2 3 4 1上面的分析结果，实际上是给出一种产生错排的结果。
f[n]=(n-1)*f[n-1]+(n-1)*f[n-2]
第一种情况 第一列是4分别与123互换位置，其余两个元素错排 ：(n-1)*f[n-2]
n-1是4能和前面的换位置的个数，f[n-2]是n-2个错排
同理后两个是 (n-1)*f[n-2]
T2【bitset】【BFS】
用bitset维护每个点能到的点集，暴力n^2
1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 #define R register 5 using namespace std; 6 inline int min(int x,int y){ 7 return x<y?x:y; 8 } 9 const int maxn=2048; 10 int n; 11 int a[maxn][maxn],b[maxn][maxn]; 12 char ch[maxn]; 13 int tot,dfn[maxn],low[maxn]; 14 int cnt,ins[maxn]; 15 int top,sta[maxn]; 16 int vis[maxn]; 17 void init(){ 18 top=cnt=tot=0; 19 for(int i=1;i<=n;++i) vis[i]=ins[i]=dfn[i]=low[i]=0; 20 } 21 void tarjan(int x,int ff){ 22 dfn[x]=low[x]=++tot; 23 sta[++top]=x,ins[x]=1; 24 vis[x]=1; 25 for(int y=1;y<=n;++y){ 26 if(ff==1&&!a[x][y]&&!b[x][y])continue; 27 if(ff==2&&!a[x][y]&&!b[y][x])continue; 28 if(!dfn[y]){ 29 tarjan(y,ff); 30 low[x]=min(low[x],low[y]); 31 } 32 else if(ins[y]) 33 low[x]=min(low[x],dfn[y]); 34 } 35 if(dfn[x]==low[x]){ 36 int y;++cnt; 37 do{ 38 y=sta[top--]; 39 ins[y]=0; 40 }while(y!=x); 41 } 42 } 43 int main(){ 44 // freopen("data","r",stdin); 45 int T;scanf("%d",&T); 46 while(T--){ 47 scanf("%d",&n); 48 for(int i=1;i<=n;++i){ 49 scanf("%s",ch+1); 50 for(int j=1;j<=n;++j){ 51 a[i][j]=b[i][j]=0; 52 if(ch[j]==‘P‘)a[i][j]=1; 53 if(ch[j]==‘Q‘)b[i][j]=1; 54 } 55 } 56 init(); 57 for(int i=1;i<=n;++i) 58 if(!vis[i]) tarjan(i,1); 59 if(cnt!=n){puts("N");continue;} 60 init(); 61 for(int i=1;i<=n;++i) 62 if(!vis[i])tarjan(i,2); 63 if(cnt!=n){puts("N");continue;} 64 puts("T"); 65 } 66 }
原文：https://www.cnblogs.com/casun547/p/11643977.html
