QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413349#4888. Decoding The Messagechenxinyang2006WA 1ms3732kbC++205.3kb2024-05-17 13:40:542024-05-17 13:40:54

Judging History

你现在查看的是最新测评结果

  • [2024-05-17 13:40:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3732kb
  • [2024-05-17 13:40:54]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
#define mod 65535
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

template <int P>
class mod_int
{
    using Z = mod_int;

private:
    static int mo(int x) { return x < 0 ? x + P : x; }

public:
    int x;
    int val() const { return x; }
    mod_int() : x(0) {}
    template <class T>
    mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    bool operator==(const Z &rhs) const { return x == rhs.x; }
    bool operator!=(const Z &rhs) const { return x != rhs.x; }
    Z operator-() const { return Z(x ? P - x : 0); }
    Z pow(long long k) const
    {
        Z res = 1, t = *this;
        while (k)
        {
            if (k & 1)
                res *= t;
            if (k >>= 1)
                t *= t;
        }
        return res;
    }
    Z &operator++()
    {
        x < P - 1 ? ++x : x = 0;
        return *this;
    }
    Z &operator--()
    {
        x ? --x : x = P - 1;
        return *this;
    }
    Z operator++(int)
    {
        Z ret = x;
        x < P - 1 ? ++x : x = 0;
        return ret;
    }
    Z operator--(int)
    {
        Z ret = x;
        x ? --x : x = P - 1;
        return ret;
    }
    Z inv() const { return pow(P - 2); }
    Z &operator+=(const Z &rhs)
    {
        (x += rhs.x) >= P && (x -= P);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        (x -= rhs.x) < 0 && (x += P);
        return *this;
    }
    Z operator-()
    {
        return -x;
    }
    Z &operator*=(const Z &rhs)
    {
        x = 1ULL * x * rhs.x % P;
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o)                                  \
    friend T operator o(const Z &lhs, const Z &rhs) \
    {                                               \
        Z res = lhs;                                \
        return res o## = rhs;                       \
    }
    setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
    
    friend istream& operator>>(istream& is, mod_int& x)
    {
        long long tmp;
        is >> tmp;
        x = tmp;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mod_int& x)
    {
        os << x.val();
        return os;
    }
};

using Z = mod_int<mod>;
Z power(Z p,ll k){
    Z ans = 1;
    while(k){
        if(k % 2 == 1) ans *= p;
        p *= p;
        k /= 2;
    }
    return ans;
}
int T,n,k;
int occ[260],_occ[260];
int a[15];

const int m = 256;
Z brute(){
    n = 0;
    rep(i,0,m){
        while(occ[i]){
            a[n++] = i;
            occ[i]--;
        }
    }

//    rep(i,0,n - 1) printf("%d ",a[i]);
//    printf("\n");
    Z answer = 1,sum;
    rep(S,0,(1 << n) - 1){
        if(popcnt(S) != (n + 1) / 2) continue;
        sum = 0;
        rep(i,0,n - 1){
            if((S >> i) & 1) sum += a[i];
            else sum += 256 * a[i];
        }
        answer *= sum;
    }
    int rk = 1;
    rep(i,1,n / 2) rk *= i;
    rep(i,1,(n + 1) / 2) rk *= i;
    return power(answer,rk);
}

bitset <520> dp[260],ndp[260];
void trans(int C){
    rep(i,0,m) ndp[(i + C) % 257] |= dp[i] << 1;
    rep(i,0,m){
        dp[i] |= ndp[i];
        ndp[i].reset();
    }
}

int check(int maj){//除了 maj,剩下 occ 的和至多 2*256
    if(maj == -1) maj = 0;

    int sz = 0;
    ll inst = 0;
    //目标子集大小是 n/2
    rep(i,0,m){
        inst += 1ll * i * occ[i];
        dp[i].reset();
        ndp[i].reset();
    }
    inst = inst * 129 % 257;
    dp[0].set(0);
    rep(i,0,m){
        if(i == maj) continue;
        while(occ[i]){
            trans(i);
            occ[i]--;
            sz++;
        }
    }

    rep(i,0,m){
        rep(j,0,min(n / 2,sz)){
            if(dp[i].test(j) && occ[maj] >= n / 2 - j && (i + 1ll * maj * (n / 2 - j)) % m == inst) return 0;
        }
    }
    return 1;
}

void solve(){
    memset(occ,0,sizeof(occ));
    scanf("%d",&k);
    rep(i,1,k){
        int pos;
        scanf("%d",&pos);
        scanf("%d",&occ[pos]);
    }
    n = 0;
    rep(i,0,m){
        n += occ[i];
        _occ[i] = occ[i];
    }
    if(n <= 11){
        printf("%d\n",brute().val());
        return;
    }
    rep(p,1,256){
        int i1 = -1,i2 = -1;
        rep(i,0,m){
            if(!_occ[i]) continue;
            if(i1 == -1) i1 = i;
            else i2 = i;
        }
        if(i2 == -1){
            printf("%d\n",check(i1));
            return;
        }
        _occ[i1]--;_occ[i2]--;
    }
}

int main(){
//    freopen("test.in","r",stdin);
    scanf("%d",&T);
    while(T--) solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3708kb

input:

5
1
42 1
2
0 1
1 1
1
239 2
2
1 1
2 1
3
1 1
2 2
3 2

output:

42
256
514
1284
61726

result:

ok 5 number(s): "42 256 514 1284 61726"

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3732kb

input:

100
1
213 79
1
54 69
1
218 55
1
248 80
1
101 8
1
153 79
1
240 45
1
112 70
1
217 5
1
208 64
1
48 30
1
0 19
1
53 40
1
63 17
1
179 65
1
221 22
1
135 84
1
138 20
1
54 29
1
114 19
1
253 94
1
240 36
1
40 94
1
244 93
1
239 24
1
133 8
1
105 91
1
45 43
1
241 74
1
206 17
1
100 73
1
133 44
1
57 70
1
56 72
1
47...

output:

1
1
1
1
32896
1
1
1
43570
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
32896
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
15420
1
22101
1
1
1
1
1
1
1
1
1
239
1
1
1
1
1
1
1
1
1
1
1
1
39321
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

wrong answer 1st numbers differ - expected: '21846', found: '1'