Submission #287027

#	Time	Username	Problem	Language	Result	Execution time	Memory
287027		tqbfjotld	Intergalactic ship (IZhO19_xorsum)	C++14	0 / 100	331 ms	2560 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/2);
    return (t*t)%MOD;
}
int modinv(int a){
    return fastExp(a,MOD-2);
}

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

int newv[1005];

int div2 = modinv(2);

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<128; 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);
        assert(a==b);
        vector<int> temp;
        for (int x = a; x<=b; x++){
            temp.clear();
            for (int y = 0; y<128; y++)
                temp.push_back((div2*occ[x][y^c])%MOD);
            for (int y = 0; y<128; y++){
                occ[x][y] *= div2;
                occ[x][y]%=MOD;
                occ[x][y] += temp[y];
                occ[x][y]%=MOD;
            }
        }
    }
    int someNumber = fastExp(2,-q);
    int otherNum = fastExp(2,q);
    long long something = 0;
    long long tans = 0;
    for (int x = 1; x<=n; x++){
        int toAdd = 0;
        int t = 0;
        for (int y = 0; y<128; y++){
            int mult = occ[x][y];
            t += mult;
            tans += (y*y*x*(n-x+1)*mult)%MOD;
            tans += 2*y*(n-x+1)*(something*mult)%MOD;
            tans %= MOD;
            toAdd += (y)*((someNumber*mult)%MOD)*x;
            toAdd %= MOD;
        }
        something += toAdd;
        assert(t==otherNum);
    }
    printf("%lld",tans);
}

Compilation message (stderr)

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

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