杭电杯第九场

个人题解，欢迎指正

P1007

DP,本人不会

Code：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

const int mod=998244353;
ll n,k,r;
int a[5010];
int dp[5010][5010];

void solve() {
    cin>>n>>k>>r;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(dp,0,sizeof(dp));
    dp[1][1]=1;
    for(int i=2;i<=n;i++) {
        ll p=upper_bound(a+1,a+n+1,a[i]-r)-a-1;
        for(int j=1;j<=i;j++){
            if(j==i) {
                dp[i][j]=dp[i-1][j-1];
            }
            else if(j==1) {
                ll p1=p;
                if(i-1-j>=0)
                   p1=p-(i-1-j);
                dp[i][j]=(p1*dp[i-1][j])%mod;
            }
            else {
                ll p1=p;
                if(i-1-j>=0)
                p1=p-(i-1-j);
                dp[i][j]=(dp[i-1][j-1]+(p1*dp[i-1][j])%mod)%mod;
            }
        }
    }
    cout<<dp[n][k]<<endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

P1008

即在[1,n]中有多少个数和x,y互质，将两个数质因数分解后容斥即可

坑点：1.有重复数据，需要记录 2.当gcd(x,y)==2时，路径数量多出来一条

Code：

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0;scanf("%lld",&x);return x;}
inline void writ(ll x){printf("%lld",x);}

int n,m;

inline int gcd(int x,int y){
    return !y?x:gcd(y,x%y);
}

void Qingtuan(){
    scanf("%d%d",&n,&m);
    int x,y;
    ll l;
    map<ll,int>mq;
    while (m--)
    {
        scanf("%d%d",&x,&y);
        if(gcd(x,y)==1){
            puts("1 1");continue;
        }

        auto gjj=[&](int a,int b)->int{
            set<int>q;ll lc=1;
            for (int i = 2; i <= a/i; i++)
            {
                if(!(a%i)){
                    q.insert(i);
                    while (!(a%i))a/=i;
                }
            }
            if(a>1)q.insert(a);
            for (int i = 2; i <= b/i; i++)
            {
                if(!(b%i)){
                    q.insert(i);
                    while (!(b%i))b/=i;
                }
            }
            if(b>1)q.insert(b);
            vector<int>pme(q.begin(),q.end());
            for(auto i:pme)lc*=i;
            if(mq.count(lc))return mq[lc];
            int sum=0;
            for(int i=1;i<(1<<pme.size());++i)
            {
                ll z=1,num=0;
                for(int j=0;j<pme.size();++j)
                    if(i>>j&1) z*=pme[j],++num;
                if(num&1) sum+=n/z;
                else sum-=n/z;
            }
            
            return mq[lc]=n-sum;
        };
        printf("2 %d\n",gjj(x,y)+(gcd(x,y)==2?1:0));
    }
}

int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    //int T=read();while (T--)
    Qingtuan();
    return 0;
}

P1010

观察后发现结果和顺序无关，直接按顺序计算即可

Code：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

const int mod=998244353;
const int maxn=505;
ll a[maxn];

void solve() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    for(int i=2;i<=n;i++) {
        a[i]=(a[i-1]+a[i]+a[i-1]*a[i])%mod;
    }
    cout<<a[n]<<endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}