依旧是好一场烂一场。
依旧是那么菜。
依旧是难止颓废。
依旧是在此方仰望，幻想？
上面这段中二的东西是为了防止Parisb说我的标题与内容无关而diss我莫名其妙115的语文。
但是菜是的确是菜。。。
这次没改题就来写博是因为考场心态稍炸，想稍微写一下。
考前日常毒奶：
我看了下总刷题排行榜，Dybala699，Mr_zkt598。
我想让他们凑个整，我就说zkt要A2个，Dybala要A1个。
然后两个都说中了。。。我并不知道这次T2可以那样AC。
然后我就被Dybala良心谴责了（他T2小问题打飞了本来能AC的）啊啊啊我没脸我错了
然而反正我自己也就A了一个。。。
回归正题：
上来看题，都不会。
然后T1可以打表找规律，26分钟搞定，高精数组开的20，WA60。
然后看T2，不会，看了一个小时，不会，去厕所，听Parisb说Dybala切题好快，心态稍炸。
突然发现自己电脑底下的有3盒空的百醇，以及一大堆零食袋子，心烦。
又怕自己被冤枉于是这次考试很短时间就去了3次厕所，每次都用演算纸包着零食的盒子怕被其他老师看见。
往厕所运了3次之后总算清干净了，舒坦一些，然后关上柜子，忽然又一盒空百醇掉到了我的脚上。
后来又运了一趟。。。
另外我这一个小时没碰鼠标键盘，而Yu-shi在我旁边一直码一直码码了一个半小时。。。心态更崩了。
打了半个正解，TLE40。
然后这边的人开始问T3的样例的时，坐在角落听不清他们在说什么，只听到T3balabalaT3balabala
意思就是他们都进T3了，我T2动还没动呢
心理压力更大了。
然后又看了一个小时，想到了题解里的那个正解（不是bitset）但不会证明，把int数组写成char数组，RE30。
其实复杂度算错了，一看n会死就又没想bitset。一直在想n。
然后自己不会证也没什么想法，进T3，样例锅了，发大样例。
大样例暴力跑不出来，小样例暴力输出不对。
这是考场心态。
然后T3乱打暴力就扔了，过会T1发现数组锅了，改正。结束。
算复杂度时要考虑bitset的1/32的常数。
稳住心态！稳住心态！稳住心态！尽量不要受周围人的干扰。
按照自己的步调来，不管什么分数都是自己考的，没有人为你负责。
抗干扰能力还是要练，至少现在不会被LNC***键盘而干扰过甚。（虽然能听出来他要AK了）
但是问题还是很多。环境的改变不是理由因为你的确不能改变csp的考场。。。
啊。。。收到一个信息奥赛三调进步奖，真是讽刺。
从好变菜再变得稍微不那么菜就能拿进步奖。。。
算了吧。
稳住心态。
加油吧。。。
T1：棋盘
打表找到的式子，还不会证：
f[i]=f[i-1]*i+(-1)
转自skyh。我菜鸡就不写了。
#include<cstdio>
struct bigint{
int ws,a[];
void operator++(){
a[]++;
for(int i=;a[i]>=;++i)a[i]-=,a[i+]++;
if(a[ws+])ws++;
}
void operator--(){
a[]--;
for(int i=;a[i]<;++i)a[i]+=,a[i+]--;
if(!a[ws])ws--;
}
void operator*=(int k){
for(int i=;i<=ws;++i)a[i]*=k;
for(int i=;i<=ws;++i)a[i+]+=a[i]/,a[i]%=;
if(a[ws+])ws++;
}
void print(){
printf("%d",a[ws]);
for(int i=ws-;i;--i)printf("%04d",a[i]);
puts("");
}
}ans;
int main(){
int n;scanf("%d",&n);
if(n==){puts("");return ;}
for(int i=;i<=n;++i){
ans*=i;
if(i&)--ans;
else ++ans;
}
ans.print();
}
T2：传递
用bitset的做法我就不说了。虽然我考场上没想到。
题解的结论仅在竞赛图下成立：
考虑两个点u，v。
如果P中存在路径由u到v，那么就必须有一条P边由u到v
1）如果同时Q中存在路径由v到u，那么就必须有一条Q边由v到u，与上面矛盾。
此时PQ的边都建出来的话会形成经过uv的环。
2）如果同时Q中存在路径由u到v，那么就必须有一条Q便又u到v，与上面矛盾
此时P与Q的反边都建出来的话也会形成经过uv的环。
所以只要把P所有边建出来，Q边正着建后判个环，Q边反着建后再判个环，就好了。
拓扑。数组不要开成char。
因为是竞赛图，所以每两个点之间都有一条单向边，所以上述判断条件就是充分必要条件了。
#include<cstdio>
int n,deg[],q[];char m[][];
int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%d",&n);char T=;
for(int i=;i<=n;++i)scanf("%s",m[i]+);
for(int i=;i<=n;++i)deg[i]=;
for(int i=;i<=n;++i)for(int j=;j<=n;++j)if(m[i][j]!='-')deg[i]++;
int t=;
for(int i=;i<=n;++i)if(!deg[i])q[++t]=i;
for(int h=;h<=t;++h)for(int i=;i<=n;++i)if(m[i][q[h]]!='-'){
deg[i]--;
if(!deg[i])q[++t]=i;
}
if(t!=n){T=;goto output;}
for(int i=;i<=n;++i)deg[i]=;t=;
for(int i=;i<=n;++i)for(int j=;j<=n;++j)
if(m[i][j]=='P')deg[i]++;
else if(m[i][j]=='Q')deg[j]++;
//for(int i=1;i<=n;++i)printf("%d ",deg[i]);
for(int i=;i<=n;++i)if(!deg[i])q[++t]=i;
for(int h=;h<=t;++h)for(int i=;i<=n;++i)if(m[i][q[h]]=='P'||m[q[h]][i]=='Q'){
deg[i]--;//printf("%d->%d\n",q[h],i);
if(!deg[i])q[++t]=i;
}
if(t!=n)T=;
output:puts(T?"T":"N");
}
}
T3：异或
不会。注意d要小于min(a)而不是小于等于。