C++(g++ 7.5.0) 解法, 执行用时: 1003ms, 内存消耗: 68564K, 提交时间: 2023-03-29 22:23:07

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll mod = 1234567890;
const ll M=1e9+13;
const ll mm = 1e5 + 10;
const int m=1e6;
ll jc[mm],a[mm];
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,q;
    cin>>n>>q;
    jc[0]=1;
    for(int i=1;i<=n;i++){
        jc[i]=jc[i-1]*i%mod;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<ll>b;
    b.push_back(0);
    int bbbb=0;
    for(int i=1;i<=n;i++){
        if(jc[a[i]])b.push_back(jc[a[i]]);
        else bbbb=1;
    }
    int nn=b.size();
    nn--;
    for(int i=1;i<=nn;i++){
        b[i]=(b[i-1]+b[i])%mod;
    }
    vector<ll>v;
    for(int i=0;i<=nn;i++){
        for(int j=i+1;j<=nn;j++){
            v.push_back(((b[j]-b[i])%mod+mod)%mod);
        }
    }
    if(bbbb)v.push_back(0);
    sort(v.begin(),v.end());
    while(q--){
        ll x;
        cin>>x;
        if(*lower_bound(v.begin(),v.end(),x)==x)cout<<"ZNnb\n";
        else cout<<"WNMnb\n";
    }
}

C++14(g++5.4) 解法, 执行用时: 962ms, 内存消耗: 67704K, 提交时间: 2019-12-09 18:50:30

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
const int mod = 1234567890;
typedef long long ll;
ll a[maxn], b[maxn];
vector<ll> v;
int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    a[0] = 1;
    set<int> sp;
    for (int i = 1; i <= 1e5; i++) {
        a[i] = a[i - 1] * i % mod;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if(a[x]) b[++cnt] = a[x];
    }
    for (int i = 1; i <= cnt; i++) b[i] = (b[i] + b[i - 1]) % mod;
    for (int i = 1; i <= cnt; i++) {
        for (int j = i; j <= cnt; j++)
            v.push_back((b[j] - b[i - 1] + 2ll * mod) % mod);
    }
    if(n >= 3803) v.push_back(0);
    sort(v.begin(), v.end());
    while (q--) {
        ll x;
        scanf("%lld", &x);
        int k = lower_bound(v.begin(), v.end(), x) - v.begin();
        if(v[k] == x) printf("ZNnb\n");
        else printf("WNMnb\n");
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 858ms, 内存消耗: 29560K, 提交时间: 2020-02-25 14:45:29

#include<bits/stdc++.h>
using namespace std;
long long mod=1234567890;
long long a[200000],b[200000];
int w[10000000];
int main()
{
	int n,q,x,cnt=1,siz=0;
	scanf("%d%d",&n,&q);
	a[0]=1;
	for(int i=1;i<=100000;i++)
	a[i]=(a[i-1]*i)%mod;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(a[x])
		b[cnt++]=a[x];
	}
	for(int i=1;i<cnt;i++)
	b[i]=(b[i]+b[i-1])%mod;
	for(int i=1;i<cnt;i++)
	{
		for(int j=i;j<cnt;j++)
		{
			w[siz++]=(b[j]-b[i-1]+2*mod)%mod;
		}
	}
	if(n>=3803) w[siz++]=0;
	sort(w,w+siz);
	while(q--)
	{
		scanf("%d",&x);
		int k=lower_bound(w,w+siz,x)-w;
		if(w[k]==x)
		printf("ZNnb\n");
		else
		printf("WNMnb\n");
	}
	return 0;
}