T1

考虑容斥枚举x的倍数即可。

#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e6+5,mod=1e9+7;
int fac[maxn],inv[maxn],invf[maxn],g[maxn];
int t[maxn];
int c(int x,int y)
{if(x>n>>m>>k;fac[0]=invf[0]=1;for(int i=1;i<=n;i++){if(i!=1)inv[i]=inv[mod%i]*(mod-mod/i)%mod;else inv[1]=1;fac[i]=fac[i-1]*i%mod;invf[i]=invf[i-1]*inv[i]%mod;}for(int i=1;i<=n;i++){int x;cin>>x;t[x]++;}for(int i=m;i;i--){int cnt=0;for(int j=1;i*j<=m;j++){cnt+=t[i*j];g[i]=(g[i]-g[i*j]+mod)%mod;}g[i]=((g[i]+c(cnt,k))%mod+mod)%mod;}for(int i=1;i<=m;i++) cout<

T2

设 \(f_{i,j}\) 表示在i这个节点转j次的最小时间。

同时记录一下i在哪个路径上

然后顺着环走即可

#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=10005,maxm=50005,maxk=105;
int n,m,s,k,cnt,rt[maxm];
int t,ans,f[maxm][maxk];
struct node 
{int to;int len;int st,ti;
}a[maxm];
struct que
{int x,k;int t;bool bj;
};
vector > g[maxm];
vector p[maxm];
queue q;
void add(int x,int y,int z,int st,int ti)
{a[x].to=y;a[x].len=z;a[x].st=st;a[x].ti=ti;
}
int calc(int now,int s,int t)
{if (now<=s) return s;int n=(now-s)/t;if ((now-s)%t!=0) n++;return n*t+s;
}
signed main()
{freopen("Transit.in","r",stdin); freopen("Transit.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>m>>s>>k>>t;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;g[u].push_back({v,w});g[v].push_back({u,w});}for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());for(int i=1;i<=s;i++){int num,x,y;cin>>num>>x>>y;int lst=0,u=0;for(int j=1;j<=num;j++){int v;cin>>v;cnt++;p[v].push_back(cnt);rt[cnt]=v;if(!u) u=v,lst=cnt;else{int l=0,r=g[u].size()-1,mid,res=0;while(l<=r){mid=(l+r)>>1;if(v<=g[u][mid].first) res=mid,r=mid-1;else l=mid+1;}add(lst,cnt,g[u][res].second,x,y);lst=cnt;x+=g[u][res].second;u=v;}}}memset(f,0x3f,sizeof(f));for(int i=0;i

=inf) cout<<"NIE"<

T3

考虑依次加入等质量的物品，就像快速幂一样，做一个dp

再用差分优化即可。

每次将加进来的物品。跟当前的进行归并。然后在同余取出所有相同的位置即可。

#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=5e5+5;
pair a[maxn];
int ans,n,m;
vector dp;
signed main()
{freopen("miner.in","r",stdin); freopen("miner.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i].second>>a[i].first;sort(a+1,a+n+1);m/=a[1].first;int now=a[1].first;for(int i=1;i<=n;i++){if(a[i].first==now) dp.push_back(a[i].second);else{sort(dp.begin(),dp.end());int mm=m%(a[i].first/a[i-1].first);while(mm>0&&dp.size()>0) ans+=dp.back(),dp.pop_back(),mm--;m/=(a[i].first/a[i-1].first);int c=a[i].first/a[i-1].first;vector f;while(dp.size()>0){int s=0;for(int j=1;j<=c&&dp.size()>0;j++) s+=dp.back(),dp.pop_back();f.push_back(s);}swap(f,dp);dp.push_back(a[i].second);now=a[i].first;}}sort(dp.begin(),dp.end());while(m>0&&dp.size()>0) ans+=dp.back(),m--,dp.pop_back();cout<