AGC这么hard的嘛，从A就开始卡题，然后只会AB。。
(f A - Triangle)
(f Description)：在坐标系中找三个整点，使其构成三角形面积为 (S/2) ， (1 ≤ S ≤ 10^{18}) ， (0 leq X,Y leq 10^9)
(f Solution)：我也不知道怎么说？？设三个点分别在 ((a,0) , (0,b) , (x,y))，且不妨设 (a leq x,bleq y)，那么可得 (S=2xy-ab-(x-a)y-x(y-b)) ，整理可得 (xy-S=(x-a)(y-b)) 。
为了让 (x,y,a,b leq 10^9) ，我们可以这么搞，找一对 (x,y) 使左边 (leq 10^9)，右边的话，直接 (x-a=1), (y-b=xy-S)，然后 (x,y) 找两个接近 (sqrt S) 的整数就过了。。
（其实可能还要证一下这样构造会满足 (y leq xy-S) ，但是因为太懒就省略了。。）
好像和官方题解不太一样，好像官方题解会真一点。。
#include<bits/stdc++.h>
#define LL long long
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=1002;
LL S;
void read(LL &x){ scanf("%lld",&x); }
int main(){
read(S);
LL x=sqrt(S)+0.0001,y=S/x;
if (x*y<S) x++;
LL v=x*y-S;
LL a=x-1,b=y-v;
printf("%lld %lld %lld %lld %lld %lld
",a,0,0,b,x,y);
return 0;
}
(f B - Do Not Duplicate)
(f Description)：给一个长度为 (N) 的数列 (A) ，将 (A) 重复 (K) 次得到数列 (X) ，将 (X) 中的数依次加入 (s) 中，规则是这样的：
- 如果 (s) 中没有 (X_i) 这个数，将 (X_i) 加到末尾
- 如果有，从末尾一直删除，直到数列中没有 (X_i) （不再加入）
求数列 (s) 。
(f Solution)：为什么感觉AGC的题解好难写，一种说不清的感觉。。这题的话，我们关心一下每次数列被清空是啥时候，如果这次在加入 (A_i) 的时候是空的，那么 (s) 第一个数就变成了 (A_{i}) ，那下次清空就是再次出现 (A_i) 的时候，设为 (A_j) ，那么接下去 s 的第一个数就变成了 (A_{j+1}) 。于是，我们从 (i) 向 (j+1) 连一条边。沿着边走就会出现环，相当于有循环节，把循环节从 (N imes K) 里去掉，剩下的暴力就行。
具体可能还是要看代码实现，但是我代码很丑呢。。
#include<bits/stdc++.h>
#define LL long long
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=200002;
int n,a[N];
int b[N];
int h[N],w;
int to[N];
LL K;
void read(int &x){ scanf("%d",&x); }
void read(LL &x){ scanf("%lld",&x); }
void gooo(int p,int s){ //暴力按题意加入数字
memset(b,0,sizeof b);
fr(i,1,s){
if (!b[a[p]]) h[++w]=a[p],b[a[p]]=1;
else{
while(h[w]!=a[p]) b[h[w]]=0,w--;
b[h[w]]=0;w--;
}
p=p%n+1;
}
fr(i,1,w) printf("%d ",h[i]);
}
void goo(int p,LL s){ //暴力跳到最后一次清空
while(to[p]-p+1<=s){
s-=to[p]-p+1;
p=to[p]%n+1;
}
gooo(p,s);
}
int main(){
read(n);read(K);
fr(i,1,n) read(a[i]);
rf(i,n,1) b[a[i]]=i+n;
rf(i,n,1) to[i]=b[a[i]],b[a[i]]=i;
memset(b,0,sizeof b);
int p=1;LL s=0,sc=0; //s表示从1走完循环节的总次数，sc表示循环节上的总次数
while(!b[p]){
b[p]=1;
s+=to[p]-p+1;
p=to[p]%n+1;
}
int q=p;
while(1){
sc+=to[q]-q+1;
q=to[q]%n+1;
if (q==p) break;
}
if (n*K<=s) goo(1,n*K);
else goo(p,(n*K-s)%sc);
return 0;
}
(f C - GP 2)
(f Description)：一个长度为 (n) 的数列初始都为 (0) 。一次操作可以选择两个不同的位置，一个 (+1) ，一个 (+2) ，问 (M) 次操作后形成的数列有多少种可能，模 (998244353) 。
(f Solution)：可以发现最后形成数列是合法的充要条件如下
- (sum_{i=1}^n x_i=3M)
- (max{x_1,x_2,cdots,x_n} leq 2M)
- (sum_{i=1}^n [x_i mod 2=1] leq M)
不证了，感性理解下= =这个结论我倒是发现了，但是不知道是不是因为太久没做TC，数数水平下降到哪里去都不知道了QAQ。
先不考虑第二个条件emmm。。然后我们可以枚举有几个奇数，总数就是 $$sum_{i=1}^M {n choose i} cdot {(3M-i)/2+n-1 choose n-1}$$
考虑把不满足第二个条件的答案踢出去。注意到大于 (2M) 的数最多只有一个，把它减去 (2M) 后，问题就转化为求下面这个数列的数量（不妨设这个大于 (2M) 的数为 (x_1) ，最后要乘 (n)）
- (sum_{i=1}^n x_i=M)
- (sum_{i=1}^n [x_i mod 2=1] leq M)
- (x_1>0)
如果无视第三个条件的话，好像和上面求法差不多呢0_0
然后考虑怎么把不符合第三个条件的踢出去。那样的话 (x_1=0)，问题又转化了：
- (sum_{i=2}^n x_i=M)
- (sum_{i=2}^n [x_i mod 2=1] leq M)
还是一样的求法呢。。
贴代码
#include<bits/stdc++.h>
#define LL long long
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=3000002;
const int p=998244353;
int n,m;
LL mul[N],inv[N];
LL ans;
void read(int &x){ scanf("%d",&x); }
void read(LL &x){ scanf("%lld",&x); }
LL qpow(LL a,int n){
LL ans=1;
for(LL sum=a;n;n>>=1,sum=sum*sum%p) if (n&1) ans=ans*sum%p;
return ans;
}
void init(){
mul[0]=1;
frl(i,1,N) mul[i]=mul[i-1]*i%p;
inv[N-1]=qpow(mul[N-1],p-2);
rf(i,N-2,0) inv[i]=inv[i+1]*(i+1)%p;
}
LL C(int n,int m){
if (n<0||m<0||n-m<0) return 0;
return mul[n]*inv[m]%p*inv[n-m]%p;
}
void Add(LL &x,LL y){
x+=y;
while(x<0) x+=p;
while(x>=p) x-=p;
}
int main(){
read(n);read(m);
init();
fr(i,0,m)
if ((3*m-i)%2==0) Add(ans,C(n,i)*C((3*m-i)/2+n-1,n-1)%p);
fr(i,0,m)
if ((m-i)%2==0) Add(ans,-C(n,i)*C((m-i)/2+n-1,n-1)%p*n%p);
fr(i,0,m)
if ((m-i)%2==0) Add(ans,C(n-1,i)*C((m-i)/2+n-2,n-2)%p*n%p);
cout<<ans<<endl;
return 0;
}
(f D - Negative Cycle)
后面的，可能也不太懂，先咕咕咕。。