The 3rd Universal Cup. Stage 8: Cangqian
題解：
https://files.cnblogs.com/files/clrs97/ZJCPC24_Tutorial.pdf
Code：
A. Bingo
#include <bits/stdc++.h>
using namespace std;
string n;
int m;
typedef long long ll;
ll sum[1000005];
int pw[1000005];
bool all[1000005];
int sol[1000020];
void solv() {
cin >> n >> m;
int am = 0 ;
for(int i = 0;i < n.size();i++) am = (10LL * am + n[i] - '0') % m;
int ans = m - am;
sum[n.size()] = 0;
for(int i = 0;i < n.size();i++) {
sum[i] = 1LL * ('9' - n[i]) * pw[n.size() - i - 1] ;
}
all[n.size()] = 1;
for(int i = n.size() - 1;i >= 0;i--) {
all[i] = all[i + 1] && (n[i] == '9') ;
}
for(int i = n.size() - 1;i >= 0;i--) sum[i] += sum[i + 1];
string b; int d = m;
while(d) {
b += ((d % 10) + '0') ;
d /= 10;
}
reverse(b.begin() , b.end()) ;
vector<int> rm(b.size() + 1) ;
for(int i = b.size() - 1;i >= 0;i--) {
rm[i] = (b[i] - '0') * pw[b.size() - i - 1] + rm[i + 1] ;
}
for(int i = 0;i < n.size() && i + b.size() - 1 < n.size();i++) { //match
for(int j = 0 ; j <= b.size();j++) {
/// here mat , diff on n[i + j]
if(i + j >= n.size()) break ;
if(j == b.size()) {
if(!all[i + j]) ans = min(ans , 1) ;
break;
}
if(b[j] > n[i + j]) {
///
// printf("in %d %d : %d %d %d\n",i,j,(ll)(b[j] - n[i + j] - 1) * pw[n.size() - (i + j) - 1] , sum[i + j + 1] , 1LL * rm[j + 1] * pw[n.size() - (i+b.size())]) ;
ans = min((ll)ans , 1 + (ll)(b[j] - n[i + j] - 1) * pw[n.size() - (i + j) - 1] + sum[i + j + 1] + 1LL * rm[j + 1] * pw[n.size() - (i+b.size())]);
}
if(j == b.size() || i + j >= n.size() || b[j] != n[i + j]) break;
}
}
int L = (int)n.size() - 1;
// printf("L %d\n",L) ;
for(int i = 0;i < n.size() + 15;i++) sol[i] = 0;
for(int i = 0;i < n.size();i++) sol[n.size() - i - 1] = n[i] - '0' ;
sol[0] += ans ;
for(int i = 0;i <= L;i++) {
sol[i + 1] += sol[i] / 10;
sol[i] %= 10;
if(sol[i + 1]) L = max(L , i + 1) ;
}
for(int i = L;i >= 0;i--) cout << sol[i] ; cout << '\n';
return ;
}
int main() {
// freopen("in.txt","r",stdin);
// freopen("out2.txt","w",stdout) ;
ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
int t;cin >> t;
pw[0] = 1;
for(int i = 1;i <= 100000;i++) {
pw[i] = min(1000000000LL , pw[i - 1] * 10LL) ;
}
while(t--) solv() ;
}
B. Simulated Universe
#include<bits/stdc++.h>
using namespace std;
const int N=8e3+1e2+7;
int T,n;
int f[2][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>n;
for(int i=0;i<=n;i++)
f[0][i]=-1e9;
f[0][0]=0;
int now=0,last=1;
int ans=0;
for(int i=1;i<=n;i++)
{
swap(now,last);
for(int j=0;j<=i+1;j++)
f[now][j]=-1e9;
string ty;
cin>>ty;
if(ty=="B")
{
ans+=2;
for(int j=0;j<=i;j++)
{
if(f[last][j]<0)
continue;
f[now][j+1]=max(f[now][j],f[last][j]);
if(f[last][j])
f[now][j]=max(f[now][j],f[last][j]-1);
}
}
else
{
int a,b;
cin>>a>>b;
for(int j=0;j<=i;j++)
{
if(f[last][j]<0)
continue;
f[now][max(j-a,0)]=max(f[now][max(j-a,0)],f[last][j]);
f[now][j]=max(f[now][j],f[last][j]+b);
}
}
}
for(int i=0;i<=n;i++)
if(f[now][i]>=0)
{
ans-=i;
break;
}
cout<<ans<<"\n";
}
}
/*
1
3 6
1 2 3
4 5 6
6 9 9
8 12 13
10 15 17
12 18 21
*/
C. Challenge NPC
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii ;
vector<pii> Ed;
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ;
int k ; cin >> k;
int n = k + 2;
for(int i = 1;i <= n;i++) {
for(int j = 1;j < i;j++) {
Ed.push_back({j*2 , i*2 - 1});
Ed.push_back({j*2 - 1 , i *2});
}
}
cout << n*2 << ' ' << Ed.size() <<' ' << 2 << '\n' ;
for(int i = 1;i <= n*2;i++) {
cout << (i&1) + 1 <<' ' ;
}
cout << '\n';
for(auto [x,y] : Ed) cout << x <<' ' << y << '\n';
return 0;
}
D. Puzzle: Easy as Scrabble
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=300005,P=998244353;
#define NO {puts("NO"); exit(0);}
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
auto solve(){
int n,m;
cin>>n>>m;
vector<string> a(n+2);
for(auto &s:a) cin>>s;
vector f(n+2,vector<array<char,4>>(m+1));
vector inq(n+2,vector<bool>(m+2));
for(int i=1;i<=n;i++){
if(a[i][0]!='.')
f[i][1][0]=a[i][0];
if(a[i][m+1]!='.')
f[i][m][1]=a[i][m+1];
}
for(int j=1;j<=m;j++){
if(a[0][j]!='.')
f[1][j][2]=a[0][j];
if(a[n+1][j]!='.')
f[n][j][3]=a[n+1][j];
}
auto check=[&](int x,int y){
static int vis[256];
static int time;
int num=0; ++time;
for(auto c:f[x][y]){
if(!isalpha(c)) continue;
if(a[x][y]!='x') a[x][y]=c;
if(vis[c]!=time){
vis[c]=time;
num++;
}
}
if(num>1) return true;
return num==1&&a[x][y]=='x';
};
queue<pair<int,int>> qu;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(check(i,j)){
qu.push({i,j});
inq[i][j]=true;
}
}
}
while(qu.size()){
auto [x,y]=qu.front(); qu.pop();
inq[x][y]=false;
a[x][y]='x';
for(int i=0;i<4;i++){
if(!isalpha(f[x][y][i])) continue;
int nx=x+dx[i],ny=y+dy[i];
if(nx<=0||ny<=0||nx>n||ny>m) NO;
f[nx][ny][i]=f[x][y][i];
if(a[nx][ny]!='x') a[nx][ny]=f[x][y][i];
if(!inq[nx][ny]&&check(nx,ny)){
inq[nx][ny]=true;
qu.push({nx,ny});
}
}
f[x][y]={0,0,0,0};
}
puts("YES");
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='x') a[i][j]='.';
putchar(a[i][j]);
}
puts("");
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
// cout<<solve()<<'\n';
// cout<<(solve()?"Yes":"No")<<'\n';
}
return 0;
}
/* Generated by powerful Codeforces Tool(cf tool)
* Author: sleep__
* Time: 2024-04-04 14:25:05
**/
E. Team Arrangement
#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int N=65,inf=~0U>>1;
int n,i,w[N],num[N],ans;ull in[N],out[N];
struct E{int l,r;}e[N];
inline bool cmp(const E&a,const E&b){return a.r<b.r;}
inline void solve(int m){
int sum=0;
ull S=0;
for(int i=1;i<=m;i++){
S^=in[i];
int now=num[i];
sum+=now*w[i];
now*=i;
while(now--){
if(!S)return;
S-=S&-S;
}
S^=S&out[i];
}
if(sum>ans)ans=sum;
}
void dfs(int x,int m){
if(x>m)return;
num[x]=0;
dfs(x+1,m);
for(int i=1;;i++){
m-=x;
num[x]=i;
if(!m)solve(x);
if(m<=0)break;
dfs(x+1,m);
}
}
int main(){
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d%d",&e[i].l,&e[i].r);
sort(e,e+n,cmp);
for(i=0;i<n;i++){
in[e[i].l]^=1ULL<<i;
out[e[i].r]^=1ULL<<i;
}
for(i=1;i<=n;i++)scanf("%d",&w[i]);
ans=-inf;
dfs(1,n);
if(ans==-inf)puts("impossible");else printf("%d",ans);
}
F. Stage: Agausscrab
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+1e2+7;
int n;
string s[N];
int a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i]>>a[i];
string ans;
for(int i=1;i<=n;i++)
{
int r=0;
for(int j=1;j<=n;j++)
if(a[j]>a[i])
r++;
r+=1;
for(int j=1;j<=r;j++)
if(s[i].size())
s[i].pop_back();
ans+=s[i];
}
ans[0]=ans[0]-'a'+'A';
cout<<"Stage: "<<ans<<"\n";
}
G. Crawling on a Tree
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int N=10005,M=10005;
int n,m,i,lim[N],g[N],v[N<<1],w[N<<1],wt[N<<1],nxt[N<<1],ed;
int wf[N],wk[N],need[N],sz[N],heavy[N];
ll ans[M];
struct E{
ll s,d[M];
int l,r;
void clr(){
s=l=0;r=m;
for(int i=0;i<=m;i++)d[i]=0;
}
}f[15];
inline void add(int x,int y,int z,int k){
v[++ed]=y;
w[ed]=z;
wt[ed]=k;
nxt[ed]=g[x];
g[x]=ed;
}
inline void merge(const E&A,const E&B,E&C){
int l=A.l+B.l,r=min(A.r+B.r,m);
static ll d[M];
int i=A.l+1,j=B.l+1,k=l+1;
while(k<=r&&i<=A.r&&j<=B.r)d[k++]=A.d[i]<B.d[j]?A.d[i++]:B.d[j++];
while(k<=r&&i<=A.r)d[k++]=A.d[i++];
while(k<=r&&j<=B.r)d[k++]=B.d[j++];
C.s=A.s+B.s;
C.l=l;
C.r=r;
for(int i=l+1;i<=r;i++)C.d[i]=d[i];
}
void dfs(int x,int y){
need[x]=lim[x];
sz[x]=1;
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==y)continue;
wf[u]=w[i];
wk[u]=wt[i];
dfs(u,x);
sz[x]+=sz[u];
if(sz[u]>sz[heavy[x]])heavy[x]=u;
need[x]=max(need[x],need[u]);
}
}
void go(int x,int y,int o){
int u=heavy[x];
if(u){
go(u,x,o);
f[o+1].clr();
merge(f[o],f[o+1],f[o]);
}else f[o].clr();
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==y||u==heavy[x])continue;
go(u,x,o+1);
merge(f[o],f[o+1],f[o]);
}
int L=need[x],R=wk[x],W=wf[x];
int A=max(f[o].l,L*2-R),B=min(f[o].r,R);
if(A>B){
for(int i=1;i<=m;i++)puts("-1");
exit(0);
}
for(int i=f[o].l+1;i<=A;i++)f[o].s+=f[o].d[i];
f[o].l=A;
f[o].r=B;
f[o].s+=1LL*(max(L,A)*2-A)*W;
for(int i=A+1;i<=B&&i<=L;i++)f[o].d[i]-=W;
for(int i=max(A,L)+1;i<=B;i++)f[o].d[i]+=W;
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<n;i++){
int x,y,z,k;
scanf("%d%d%d%d",&x,&y,&z,&k);
add(x,y,z,k);
add(y,x,z,k);
}
for(i=2;i<=n;i++)scanf("%d",&lim[i]);
wk[1]=m*2;
dfs(1,0);
go(1,0,0);
for(i=1;i<=m;i++)ans[i]=-1;
ll sum=f[0].s;
for(i=f[0].l;i<=m;i++){
if(i>=need[1])ans[i]=sum;
if(i<m)sum+=f[0].d[i+1];
}
for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
}
H. Permutation
#include <bits/stdc++.h>
using namespace std;
int n;
const double C = (sqrt(5) - 1) / 2;
int f[1000005];
int d[1000005];
int qry(int l,int r) {
cout << "? " << l <<' ' << r << '\n' ;
fflush(stdout) ;
int x ; cin >> x;
return x;
}
void solv() {
cin >> n;
int l = 1 , r = n;
int lst_pos = -1;
while(l < r) {
int c = d[r - l + 1];
// printf("C %d %d %d\n",l,r,c) ;
if(lst_pos == -1) lst_pos = qry(l , r);
if(r - l == 1) {
if(lst_pos == l) l = r;
else r = l;
break ;
}
if(l + c - 1 >= lst_pos) {
int x = qry(l , l + c - 1);
if(x == lst_pos) r = l + c - 1;
else {
l = l + c;
lst_pos = -1;
}
}
else {
int x = qry(r - c + 1 , r);
if(x == lst_pos) l = r - c + 1;
else {
r = r - c;
lst_pos = -1;
}
}
}
cout << "! " << l << '\n' ;
fflush(stdout) ;
return ;
}
int main() {
// ios::sync_with_stdio(false) ; cin.tie(0) ;
int t;cin >> t;
f[1] = f[2] = 0;
for(int i = 3;i <= 1000000;i++) {
int mxc = (int)(C * i);
f[i] = 1e9;
for(int j = max(mxc - 10 , (i + 1)/2) ; j <= min(i - 1 , mxc + 10) ; j++) {
if(max(f[j] + 1 , f[i - j] + 2) < f[i]) {
f[i] = max(f[j] + 1 , f[i - j] + 2) ;
d[i] = j;
}
}
// if(f[i] > ceil(1.5 * log2(i)) - 1) {
// printf("%d %d %lf\n",i,f[i],ceil(1.5 * log2(i)) - 1);
// }
}
// printf("%d\n",f[1000000]) ;?
while(t--) solv() ;
}
I. Piggy Sort
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+1e2+7;
int T,n,m;
int x[N][N],sx[N];
map<int,int> vis[N];
int use[N];
int av[N],bv[N],fd,ans[N];
void dfs(int t)
{
if(t==n+1)
{
vector<int> id(n);
iota(id.begin(),id.end(),1);
sort(id.begin(),id.end(),[&](const int &a,const int &b){
if(av[a]*bv[b]!=av[b]*bv[a])
return av[a]*bv[b]<av[b]*bv[a];
return a<b;
});
fd=1;
for(int i=0;i<n;i++)
ans[id[i]]=i+1;
for(int i=1;i<=n;i++)
cout<<ans[i]<<" \n"[i==n];
return;
}
for(int i=1;i<=n;i++)
{
if(use[i])
continue;
int va=x[2][i]-x[1][t];
int vb=sx[2]-sx[1];
int ok=1;
for(int j=3;j<=m;j++)
{
if(va*(sx[j]-sx[1])%vb)
{
ok=0;
break;
}
int w=va*(sx[j]-sx[1])/vb+x[1][t];
if(!vis[j].count(w)||!vis[j][w])
{
ok=0;
break;
}
}
if(ok)
{
for(int j=1;j<=m;j++)
{
int w=va*(sx[j]-sx[1])/vb+x[1][t];
vis[j][w]--;
}
use[i]=1;
av[t]=va,bv[t]=vb;
dfs(t+1);
use[i]=0;
for(int j=1;j<=m;j++)
{
int w=va*(sx[j]-sx[1])/vb;
vis[j][w]++;
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
vis[i].clear();
sx[i]=0;
for(int j=1;j<=n;j++)
cin>>x[i][j],vis[i][x[i][j]]++,sx[i]+=x[i][j];
}
if(sx[1]==sx[2])
{
for(int i=1;i<=n;i++)
cout<<i<<" \n"[i==n];
continue;
}
fd=0;
dfs(1);
assert(fd);
}
}
/*
1
3 6
1 2 3
4 5 6
6 9 9
8 12 13
10 15 17
12 18 21
*/
J. Even or Odd Spanning Tree
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200005,K=18,M=500005,inf=~0U>>1;
int Case,n,m,cnt,i,j,x,y,z,tmp,f[N],g[N],v[N<<1],w[N<<1],nxt[N<<1],ed;
int d[N],fa[N][K],fe[N][K],fo[N][K];
long long mst,ans;int delta;bool on[M];
struct E{int x,y,z;}e[M];
inline bool cmp(const E&a,const E&b){return a.z<b.z;}
inline void umax(int&a,int b){a<b?(a=b):0;}
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int y){
for(int i=1;i<K;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
fe[x][i]=max(fe[x][i-1],fe[fa[x][i-1]][i-1]);
fo[x][i]=max(fo[x][i-1],fo[fa[x][i-1]][i-1]);
}
for(int i=g[x];i;i=nxt[i]){
int u=v[i],z=w[i];
if(u==y)continue;
d[u]=d[x]+1;
fa[u][0]=x;
if(z&1){
fe[u][0]=0;
fo[u][0]=z;
}else{
fe[u][0]=z;
fo[u][0]=0;
}
dfs(u,x);
}
}
inline int ask(int x,int y,int w[][K]){
if(x==y)return 0;
if(d[x]<d[y])swap(x,y);
int ret=0;
for(int i=K-1;~i;i--)if(d[fa[x][i]]>=d[y]){
umax(ret,w[x][i]);
x=fa[x][i];
}
if(x==y)return ret;
for(int i=K-1;~i;i--)if(fa[x][i]!=fa[y][i]){
umax(ret,w[x][i]);
umax(ret,w[y][i]);
x=fa[x][i];
y=fa[y][i];
}
umax(ret,w[x][0]);
umax(ret,w[y][0]);
return ret;
}
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%d%d",&n,&m);
for(i=0;i<=n;i++){
g[i]=d[i]=0;
for(j=0;j<K;j++)fa[i][j]=fe[i][j]=fo[i][j]=0;
}
mst=cnt=ed=0;
for(i=1;i<=m;i++){
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
on[i]=0;
}
sort(e+1,e+m+1,cmp);
for(i=1;i<=n;i++)f[i]=i;
for(i=1;i<=m;i++){
x=e[i].x,y=e[i].y,z=e[i].z;
if(F(x)==F(y))continue;
on[i]=1;
f[f[x]]=f[y];
mst+=z;
cnt++;
add(x,y,z),add(y,x,z);
}
if(cnt<n-1){
puts("-1 -1");
continue;
}
dfs(1,0);
delta=inf;
for(i=1;i<=m;i++){
if(on[i])continue;
z=e[i].z;
tmp=ask(e[i].x,e[i].y,z&1?fe:fo);
if(!tmp)continue;
z-=tmp;
if(delta>z)delta=z;
}
if(delta<inf)ans=mst+delta;else ans=-1;
if(mst&1)swap(ans,mst);
printf("%lld %lld\n",mst,ans);
}
}
/*
3
2 1
1 2 5
3 1
1 3 1
4 4
1 2 1
1 3 1
1 4 1
2 4 2
*/
K. Sugar Sweet 3
#include <bits/stdc++.h>
using namespace std;
int A , B , C , x;
int n ;
const int N = 605;
const int mod = 1e9 + 7;
int fpow(int a,int b) {
int ans = 1;
while(b) {
if(b & 1) ans = 1LL * ans * a %mod;
a = 1LL * a * a %mod; b>>= 1;
}
return ans;
}
int F[N][N];
// int Ga[N][N] , Gb[N][N], Gc[N][N];
// int dota[N][N] , dotb[N][N] , dotc[N][N];
int dot[N][N];
int Cata[N] ;
int d[N] ;
int t[N * 2] , rt[N * 2] ;
int lm ; ///多項式的項數
int mat[N][N] , rmat[N][N];
int C_(int a,int b) {
return 1LL * t[a] * rt[b] % mod * rt[a - b] % mod;
}
int A_(int a,int b) {
return 1LL * t[a] * rt[a - b] % mod;
}
vector<int> get_coe(int n , vector<int> w) { ///已知n個點值[1 to n]，求sum{ai * wi} 對應的 di的系數，i from 0 to n - 1
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
mat[i][j] = fpow(i , j - 1) ; // MAT * A = D
rmat[i][j] = (i == j) ;
}
}
for(int i = 1;i <= n;i++) {
int cur = -1;
for(int j = i ;j <= n;j++) {
if(mat[j][i]) {cur = j ; break ;}
}
for(int j = 1;j <= n;j++) {swap(mat[cur][j] , mat[i][j]) ; swap(rmat[cur][j] , rmat[i][j]) ;}
int r = fpow(mat[i][i] , mod - 2);
for(int j = 1;j <= n;j++) {
if(i == j) continue ;
int f = (mod - 1LL * mat[j][i] * r %mod) % mod;
for(int k = 1;k <= n;k++) {mat[j][k] = (mat[j][k] + 1LL * mat[i][k] * f) % mod ; rmat[j][k] = (rmat[j][k] + 1LL * rmat[i][k] * f) % mod;}
}
for(int j = 1;j <= n;j++) {
mat[i][j] = 1LL * mat[i][j] * r % mod;
rmat[i][j] = 1LL * rmat[i][j] * r % mod;
}
}
// for(int i = 1;i <= n;i++ , printf("\n")) for(int j = 1;j <= n;j++) printf("%d ",rmat[i][j]) ;
///A = Rmat * D
vector<int> coe(n) ;
for(int i = 0;i < n;i++) {
for(int j = 0;j < n;j++) {
coe[j] = (coe[j] + 1LL * w[i] * rmat[i + 1][j + 1]) % mod;
}
}
return coe;
}
int main() {
cin >> A >> B >> C >> x;
n = A + B + C;
if(n & 1) {
cout << 0 ; return 0;
}
if(A > n/2 || B > n/2 || C > n/2) {
cout << 0 ; return 0;
}
t[0] = rt[0] = 1;
for(int i = 1;i <= n + 1;i++) t[i] = 1LL * t[i - 1] * i % mod , rt[i] = fpow(t[i] , mod - 2) ;
Cata[0] = 1;
for(int i = 1;i <= n/2;i++) Cata[i] = 1LL * C_(i*2 , i) * fpow(i + 1 , mod - 2) % mod;
//// F[i][j]表示i個主元分j段的方案數，Fi(x)作為其egf
F[0][0] = 1;
lm = n / 2 + 1;
for(int i = 1;i <= n/2;i++) {
for(int j = 1;j <= i;j++) {
for(int k = 1;k <= i;k++) { ///最后一段包含的主元個數
F[i][j] = (F[i][j] + 1LL * F[i - k][j - 1] * Cata[k - 1]) % mod;
}
// printf("%d %d : %d\n",i,j,F[i][j]) ;
}
}
for(int i = 0;i <= n/2;i++) {
for(int j = 0;j <= i;j++) F[i][j] = 1LL * F[i][j] * rt[j] % mod ; ///變成egf
for(int j = 1;j <= lm;j++) {
dot[i][j] = 0;
for(int k = i;k >= 0;k--) dot[i][j] = (1LL * dot[i][j] * j + F[i][k]) % mod;
///dot 代表點值
}
}
vector<int> w(n/2 + 1) ;
for(int i = 0;i <= n/2;i++) w[i] = 1LL * fpow(i , x) * t[i] % mod;
vector<int> coe = get_coe(n/2 + 1 , w) ; /// coe.len = n/2 + 1
int ans = 0;
for(int a = 0;a <= n/2 && a <= A;a++) {
for(int b = 0;b + a <= n / 2 && b <= B;b++) {
int c = n / 2 - a - b;
if(c > C) continue ;
/// F[a] * F[b] * F[c]
for(int i = 1;i <= lm;i++) d[i] = 1LL * dot[a][i] * dot[b][i] % mod * dot[c][i] % mod;
// for(int i = 1;i <= lm;i++) printf("%d ",3LL * d[i] % mod) ; printf("\n") ;
int sol = 0;
for(int i = 1;i <= lm;i++) sol = (sol + 1LL * d[i] * coe[i - 1]) % mod;
int sol2 = 0;
for(int ab = 0;ab <= A - a && ab <= b; ab++){
int ac = (A - a - ab) ;
int bc = (c - ac) ;
int ba = (B - b - bc) ;
int ca = (a - ba) ;
int cb = (C - c - ca) ;
if(ac < 0 || bc < 0 || ba < 0 || ca < 0 || cb < 0) continue ;
sol2 = (sol2 + 1LL * C_(a , ba) * C_(b , ab) % mod * C_(c , ac)) % mod;
}
// printf("%d %d %d : %d %d\n",a,b,c,sol,sol2);
ans = (ans + 1LL * sol * sol2) % mod;
}
}
cout << ans << '\n';
}
L. Challenge Matrix Multiplication
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef pair<int,int> pii;
int to[N] , fir[N] , nxt[N] ;
bool ok[N];
int cc = 0;
int nc , nodes[N];
void adde(int u,int v) {
++cc;
to[cc] = v;
nxt[cc] = fir[u];
fir[u] = cc;
}
int in[N] , out[N] ;
int n ,m ;
int ans[N];
bool vis[N];
pii fr[N] ;
int cnt = 0;
int qu[N] , l , r;
void bfs(int u) {
l = 1 , r = 0;
qu[++r] = u;
vis[u] = 1;
while(l <= r) {
int u = qu[l++];
cnt++;
for(int i = fir[u] ; i ; i = nxt[i]) {
if(!vis[to[i]]) {
qu[++r] = to[i] ;
vis[to[i]] = 1;
}
}
}
return ;
}
int main() {
ios::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
clock_t cl = clock() ;
cin >>n>>m; //printf("??? %d %d\n",n,m);
for(int i = 1;i <= m;i++) {
int u , v;cin >> u >> v;
in[v]++ ; out[u]++;
adde(u , v);
}
for(int i = 1;i <= n;i++) ans[i] = 1;
int all = m;
clock_t sum0 = 0 , sum1 = 0;
while(all) {
// clock_t a = clock();
for(int i = 1;i <= n;i++) {
if(in[i] < out[i]) {
memset(vis,0,sizeof(vis)) ;
vis[i] = 1;
int lst;
for(int j = i ; j <= n;j++) {
if(!vis[j]) continue ;
if(in[j] > out[j]) {lst = j ; break ;}
for(int x = fir[j] ; x ; x = nxt[x]) {
if(!vis[to[x]] && !ok[x]) {
vis[to[x]] = 1;
fr[to[x]] = {j , x};
}
}
}
int u = lst ;
nc = 0;
while(u) {
nodes[nc++] = u;
if(u != i) in[u]--;
if(u != lst) out[u]--;
if(u == i) break ;
ok[fr[u].second] = 1;
u = fr[u].first ;
all--;
}
break ;
}
}
// sum0 += (clock() - a);
// a = clock() ;
cnt = 0;
memset(vis,0,sizeof(vis));
for(int i = 0;i < nc;i++) {
bfs(nodes[i]) ;
ans[nodes[i]] = cnt;
}
// static int gg = 0;
// sum1 += (clock() - a) ;
// printf("i-th round %d %d\n",++gg , nc) ;
}
// cerr << (double)(clock() - cl) / CLOCKS_PER_SEC <<' ' << (double)sum0 / CLOCKS_PER_SEC <<' ' << (double)sum1 / CLOCKS_PER_SEC << '\n';
// return 0;
for(int i = 1;i <= n;i++) cout << ans[i] <<' ' ;
cout << '\n';
}
M. Triangles
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
long long n,a,b;
cin>>n>>a>>b;
long long ans=0;
for(long long r=1;r<=n;r++)
{
ans+=r*(r+1);
if(r*2>n)ans-=(r*2-n)*(r*2-n+1)/2;
}
for(long long i=1;i<=b;i++)
{
ans-=(a-b+1);
ans-=max(min(a+1-i,n-a)-(b-i),0ll);
}
cout<<ans<<endl;
return 0;
}
浙公網安備 33010602011771號