T1：字符交換 T2：平方數 T3：多維網絡
誒一看這不是水題AK場嗎？然後80分鐘就拿到了285分。
然後，對拍？還是卡T2常數？還是想T2正解？
於是上述三項我依次進行了。
前兩項讓我的分數絲毫不變但是吃掉了我一個多小時的時間。
卡常卡的也不徹底，不然就能再多個5分。因為心裏還想着我想想正解。
最後剩餘不多的時間裏想到了一個接近正解的思路。。。因為沒有時間寫所以也就放棄了進一步的思考。
首先肯定還是要%%%Paris值得紀念的考試。
然後至於我。。。現在真的是水題考不高，難題不會做。。。
沒前途。聯賽啊。。。省選啊。。。不要止步於此啊。。。
T1：字符交換
二分答案。枚舉從哪個字符開始。
最優決策一定是聚攏到最中間的那個字符的位置。
前綴和+等差數列求和就可以把絕對值拆掉。
總複雜度$O(nlogn)$
1 #include<cstdio>
2 #include<vector>
3 using namespace std;
4 vector<int>v[26];
5 char s[4005];int n,k,tot[26][4005];
6 int cal(int l,int r){return (l+r)*(r-l+1)/2;}
7 int tp(int i,int l,int r){return tot[i][r]-tot[i][l-1];}
8 bool chk(int len){
9 for(int i=0;i<26;++i)if(v[i].size()>=len)for(int j=1;j+len-1<=v[i].size();++j){
10 int l=j,r=j+len-1,m=j+(len>>1),mp=v[i][m-1];
11 if(-tp(i,l,m)+cal(mp-m+l,mp)+tp(i,m+1,r)-cal(mp+1,mp+r-m)<=k)return true;
12 }
13 return false;
14 }
15 int main(){freopen("swap.in","r",stdin);freopen("swap.out","w",stdout);
16 scanf("%d%d%s",&n,&k,s+1);
17 for(int i=1;i<=n;++i)v[s[i]-'a'].push_back(i);
18 for(int i=0;i<26;++i)for(int j=0;j<v[i].size();++j)tot[i][j+1]=tot[i][j]+v[i][j];
19 int l=1,r=n,ans;
20 while(l<=r)if(chk(l+r>>1))ans=l=l+r>>1,l++;else r=(l+r>>1)-1;
21 printf("%d\n",ans);
22 }View Code
T2：平方數
如果一個數含有平方因子，那麼把它幹掉之後這個數與其它數的關係不變。
於是篩出$\sqrt{1e9}$以內的所有質數（4300個左右），用它幹掉所有平方因子，然後哈希表統計答案。
複雜度$O(4000n)$，能得到$70~90$不等。
1 #include<cstdio>
2 #include<cmath>
3 using namespace std;
4 struct hash_map{
5 int fir[2000005],l[300005],to[300005],w[300005],cnt;
6 int &operator[](int x){
7 int r=x%2000003;
8 for(int i=fir[r];i;i=l[i])if(to[i]==x)return w[i];
9 l[++cnt]=fir[r];fir[r]=cnt;to[cnt]=x;return w[cnt];
10 }
11 }M;
12 int al[33333],cnt,p[4444],n,q[4444];long long ans;
13 int main(){freopen("square.in","r",stdin);freopen("square.out","w",stdout);
14 for(int i=2;i<=1000;++i)if(!al[i]){
15 p[++cnt]=i;
16 for(int j=2;j*i<=1000;++j)al[i*j]=1;
17 }
18 for(int i=1;i<=cnt;++i)q[i]=p[i]*p[i];
19 q[++cnt]=1000000007;
20 scanf("%d",&n);
21 while(n--){
22 int x,y=1;scanf("%d",&x);
23 for(int i=1;x>=q[i];++i){
24 while(x%q[i]==0)x/=q[i];
25 if(x%p[i]==0)x/=p[i],y*=p[i];
26 }
27 int q=sqrt(x);if(q*q!=x)y*=x;
28 int &P=M[y];ans+=P;P++;
29 }printf("%lld\n",ans);
30 }暴力
進一步優化這個思路，$\sqrt{1e9}$顯然就是複雜度瓶頸。
考慮如何能夠不篩那麼多。
對於每一個數，它含有超過1000的平方因子至多有1個（$1000^2=1000000$,放不下兩個）
那麼把它們都篩一遍是多餘的。
那麼就篩到1000，考慮剩下的是什麼。
改變篩的策略，對於你枚舉的1000以內的數時，不止幹掉平方因子，單個一次的因子也幹掉（但是要記錄下來累乘到一個變量y裏）
最後剩下的數，對它進行質因數分解，它的最小因子也大於1000。而且它之可能是以下4種情況：
- 是一個平方數
- 是兩個大於1000的質數相乘
- 是一個大於1000的質數
- 是1
繼續上面的思路，我們只需要幹掉它的平方因子。
因為現在它不可能是平方數×另一個數的形式，所以我們直接開根判斷它是不是平方數。
如果是就幹掉，否則剩餘的部分也累乘到y裏。
那麼y就是原數幹掉所有平方因子之後所剩下的。
1000以內的質因子只有170個。總複雜度$O(170n)$
（cbx實踐證明，就算你不用質數篩而是1000個全篩$O(1000n)$也是能AC的，但是在老年評測機下就不一定了）
1 #include<cstdio>
2 #include<cmath>
3 using namespace std;
4 struct hash_map{
5 int fir[2000005],l[300005],to[300005],w[300005],cnt;
6 int &operator[](int x){
7 int r=x%2000003;
8 for(int i=fir[r];i;i=l[i])if(to[i]==x)return w[i];
9 l[++cnt]=fir[r];fir[r]=cnt;to[cnt]=x;return w[cnt];
10 }
11 }M;
12 int al[33333],cnt,p[4444],n,q[4444];long long ans;
13 int main(){freopen("square.in","r",stdin);freopen("square.out","w",stdout);
14 for(int i=2;i<=1000;++i)if(!al[i]){
15 p[++cnt]=i;
16 for(int j=2;j*i<=1000;++j)al[i*j]=1;
17 }
18 for(int i=1;i<=cnt;++i)q[i]=p[i]*p[i];
19 q[++cnt]=1000000007;
20 scanf("%d",&n);
21 while(n--){
22 int x,y=1;scanf("%d",&x);
23 for(int i=1;x>=q[i];++i){
24 while(x%q[i]==0)x/=q[i];
25 if(x%p[i]==0)x/=p[i],y*=p[i];
26 }
27 int q=sqrt(x);if(q*q!=x)y*=x;
28 int &P=M[y];ans+=P;P++;
29 }printf("%lld\n",ans);
30 }View Code
T3：多維網絡
部分分給的很全啊。
首先最基本的就是有$n$種物品每種有$a_i$個那麼本質不同的排列數是$\frac{(\sum\limits_{i=1}^{n} a_i)!}{\prod\limits_{i=1}^{n}a_i!}$
觀察部分分提示，n=0的直接就是套式子。
n=1需要去掉經過了這個點的路徑，那麼就計算一下經過這個點的路徑有多少，其實就是把路徑拆成了兩部分，相乘即可。
n=2的話也一樣啊，只不過要去掉兩種經過了這兩個點之一的路徑，但是減多了，還要加回來兩個點都經過了的路徑。
n=3。。。
這不就是容斥麼？？？
但是在n=500時，手動容斥估計碼長都能超限。
運用一些性質，每個點只會走到各座標都比它大的點。我們把這樣的關係連邊。然後邊權就是從一個點走到另一個點的方案數，套上面的式子。
然後就可以得到一個DAG。（當然沒有環。。。）。DAG？當然拓撲啦。
然後這個容斥説白了就是奇加偶減，考慮奇偶。
就是如果路徑上有奇數個點，那麼答案加這麼多，否則減。
初始狀態是在原點，偶數步方案數為1，奇數步方案數為0。
然後跑拓撲，按照邊權統計方案。
最後輸出終點的奇數步-偶數步就是答案。
在有重複點的時會出鍋（DAG有環），我判掉了不知道有沒有用。。。
1 #include<cstdio>
2 #define mod 1000000007
3 int n,d,x[105][505],fac[10000005],inv[10000005],dp[2][505];
4 int fir[505],l[250005],to[250005],w[250005],deg[505],ec,q[505];
5 int qpow(long long b,int t,long long a=1){for(;t;t>>=1,b=b*b%mod)if(t&1)a=a*b%mod;return a;}
6 bool com(int p1,int p2){
7 for(int i=1;i<=d;++i)if(x[i][p1]>x[i][p2])return false;
8 return true;
9 }
10 bool sam(int p1,int p2){
11 for(int i=1;i<=d;++i)if(x[i][p1]!=x[i][p2])return false;
12 return true;
13 }
14 void Swap(int p1,int p2){
15 for(int i=1;i<=d;++i)x[i][p1]^=x[i][p2]^=x[i][p1]^=x[i][p2];
16 }
17 int cal(int p1,int p2){
18 int tot=0,ans;
19 for(int i=1;i<=d;++i)tot+=x[i][p2]-x[i][p1];
20 ans=fac[tot];
21 for(int i=1;i<=d;++i)ans=1ll*ans*inv[x[i][p2]-x[i][p1]]%mod;
22 return ans;
23 }
24 void link(int a,int b,int v){l[++ec]=fir[a];fir[a]=ec;to[ec]=b;w[ec]=v;deg[b]++;}
25 main(){freopen("net.in","r",stdin);freopen("net.out","w",stdout);
26 fac[0]=1;
27 for(int i=1;i<=10000000;++i)fac[i]=1ll*fac[i-1]*i%mod;
28 inv[10000000]=qpow(fac[10000000],mod-2);
29 for(int i=9999999;~i;--i)inv[i]=inv[i+1]*(i+1ll)%mod;
30 scanf("%d%d",&d,&n);n++;
31 for(int i=1;i<=d;++i)scanf("%d",&x[i][n]);
32 for(int i=1;i<n;++i)for(int j=1;j<=d;++j)scanf("%d",&x[j][i]);
33 for(int i=1;i<n;++i)for(int j=i+1;j<n;++j)if(sam(i,j))Swap(j,n-1),Swap(n-1,n),n--;
34 for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)if(i!=j&&com(i,j))link(i,j,cal(i,j));
35 dp[0][0]=1;
36 for(int h=1,t=1;h<=t;++h){
37 int p=q[h];
38 for(int i=fir[p];i;i=l[i]){
39 deg[to[i]]--;
40 if(!deg[to[i]])q[++t]=to[i];
41 dp[1][to[i]]=(dp[1][to[i]]+1ll*dp[0][p]*w[i])%mod;
42 dp[0][to[i]]=(dp[0][to[i]]+1ll*dp[1][p]*w[i])%mod;
43 }
44 }
45 printf("%d\n",(dp[1][n]-dp[0][n]+mod)%mod);
46 }View Code
$Fate \ is \ Fake$
