E

分别算横坐标和纵坐标

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long LL;
const LL mod=998244353;
LL dx[N][2],dy[N][2];
LL f[N],inv[N];
int H,W,K;
LL C(int a,int b)
{
    return f[a]*inv[b]%mod*inv[a-b]%mod;
}
LL ksm(LL a,LL n)
{
    LL res=1;
    while(n)
    {
        if(n&1)res=a%mod*res%mod;
        a=a%mod*a%mod;
        n>>=1;
    }
    return res;
}
void init()
{
    f[0]=inv[0]=1;
    for(int i=1;i<=K;i++) f[i]=f[i-1]*i%mod;
    inv[K]=ksm(f[K],mod-2);
    for(int i=K-1;i;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
void solve()
{
    scanf("%d %d %d",&H,&W,&K);
    init();
    int x1,x2,y1,y2;
    dx[0][1]=dy[0][1];
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    if(x1==x2) dx[0][1]=1;
    else dx[0][0]=1;
    if(y1==y2) dy[0][1]=1;
    else dy[0][0]=1;
    for(int i=1;i<=K;i++)
    {
        dx[i][1]=(dx[i-1][0])%mod;
        dx[i][0]=((H-1)%mod*dx[i-1][1]%mod+(H-2)%mod*dx[i-1][0]%mod)%mod;
        dy[i][1]=(dy[i-1][0])%mod;
        dy[i][0]=((W-1)%mod*dy[i-1][1]%mod+(W-2)%mod*dy[i-1][0]%mod)%mod;
    }
    LL ans=0;
    for(int i=0;i<=K;i++)
    {
        LL res=dx[i][1]*dy[K-i][1]%mod;
        res=res*C(K,i)%mod;
        ans=(ans+res)%mod;
    }
    printf("%lld",ans);

}
int main()
{
    //int t;
    //scanf("%d",&t);
    //while(t--)
    //{
        solve();
    //}
}

View Code

F

把n！转换成2ⁿ

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define dec(i,a,b) for(ll i=(a);i>=(b);i--)
#define pll pair<ll,ll>
using namespace std;
ll INF = 0x7f7f7f7f7f7f7f7f;
const int N = 2e5 + 5;
ll mod = 998244353;

ll n, x, y;
ll dp[1 << 18], a[20], b[20];

ll f(ll s, ll x) {
    ll res = 0;
    rep(i, 0, n-1) {
        if ((s & (1ll << i)) == 0 && i < x)
            res++;
    }
    return res;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> x >> y;
    rep(i, 1, n)
        cin >> a[i];
    rep(i, 1, n)
        cin >> b[i];
    dp[0] = 0;
    for (ll S = 1; S < (1ll << n); S++)
        dp[S] = INF;
    for (ll S = 0; S < (1ll << n); S++) {
        ll sz = 0;
        rep(i, 0, n-1) {
            if (S & (1ll << i))
                sz++;
        }
        rep(i, 0, n-1) {
            if (S & (1ll << i))
                continue;
            dp[S | (1ll << i)] = min(dp[S | (1ll << i)], dp[S] + abs(a[i+1] - b[sz + 1]) * x + f(S, i) * y);
        }
    }
    cout << dp[(1 << n) - 1] << '\n';
    return 0;
}

View Code