Submission #287000

#	Time	Username	Problem	Language	Result	Execution time	Memory
287000		tqbfjotld	Intergalactic ship (IZhO19_xorsum)	C++14	17 / 100	2075 ms	640 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;
#define int long long
///subtask 3 (i hope)

int MOD = 1000000007LL;
int modinv(int a);
int fastExp(int b, int a){
    if (a<0) return modinv(fastExp(b,-a));
    if (a==0) return 1;
    if (a&1) return (b*fastExp(b,a-1))%MOD;
    int t = fastExp(b,a>>1);
    return (t*t)%MOD;
}
int modinv(int a){
    return fastExp(a,MOD-2);
}

int orig[1005];
int occ[1005][35];
int l[100005];
int r[100005];
int v[100005];

int newv[1005];

main(){
    int n;
    scanf("%lld",&n);
    for (int x = 1; x<=n; x++){
        scanf("%lld",&orig[x]);
    }
    int q;
    scanf("%lld",&q);
    if ((n<=30 && q<=20) || (n<=100 && q<=10)){
        for (int x = 0; x<q; x++){
            scanf("%lld%lld%lld",&l[x],&r[x],&v[x]);
        }
        long long ans = 0;
        for (int bitmask = 0; bitmask<(1<<q); bitmask++){
            for (int x = 1; x<=n; x++){
                newv[x] = orig[x];
            }
            for (int x = 0; x<q; x++){
                if (bitmask & (1<<x)){
                    for (int y = l[x]; y<=r[x]; y++){
                        newv[y] ^= v[x];
                    }
                }
            }
            long long something = 0;
            long long tans = 0;
            for (int x = 1; x<=n; x++){
                tans += newv[x]*newv[x]*x*(n-x+1);
                tans += 2*newv[x]*(n-x+1)*something;
                tans %= 1000000007LL;
                something += newv[x]*x;
                something %= 1000000007LL;
            }
            ans += tans;
            ans %= 1000000007LL;
        }
        printf("%lld",ans);
        return 0;
    }
    for (int x = 1; x<=n; x++){
        for (int y = 0; y<32; y++){
            if (orig[x]==y){
                occ[x][y] = fastExp(2,q);
            }
            else occ[x][y] = 0;
        }
    }
    for (int x = 0; x<q; x++){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        vector<int> temp;
        for (int x = a; x<=b; x++){
            temp.clear();
            for (int y = 0; y<32; y++)
                temp.push_back((modinv(2)*occ[x][y^c])%MOD);
            for (int y = 0; y<32; y++){
                occ[x][y] *= modinv(2);
                occ[x][y]%=MOD;
                occ[x][y] += temp[y];
                occ[x][y]%=MOD;
            }
        }
    }
    long long something = 0;
    long long tans = 0;
    for (int x = 1; x<=n; x++){
        int toAdd = 0;
        for (int y = 0; y<32; y++){
            int mult = occ[x][y];
            tans += (y*y*x*(n-x+1)*mult)%MOD;
            tans += (2*y*(n-x+1)*something*mult)%MOD;
            tans %= 1000000007LL;
            toAdd += (y)*((fastExp(2,-q)*mult)%MOD)*x;
            toAdd %= 1000000007LL;
        }
        something += toAdd;
    }
    printf("%lld",tans);
}

Compilation message (stderr)

xorsum.cpp:27:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main(){
      |      ^
xorsum.cpp: In function 'int main()':
xorsum.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
xorsum.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |         scanf("%lld",&orig[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
xorsum.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     scanf("%lld",&q);
      |     ~~~~~^~~~~~~~~~~
xorsum.cpp:37:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |             scanf("%lld%lld%lld",&l[x],&r[x],&v[x]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9
• Subtask 5: 8 / 8
• Subtask 6: 0 / 11
• Subtask 7: 0 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8