くかんけつごうもんだい

質問する

セダ
数列が与えられ,数列部分と中をmで割った値の求め方の問題.やっぱり時間が足りない

ちょくせつかいほう

#include <iostream>
using namespace std;

long n, m;
int count = 0;

int main() {
    cin >> n >> m;
    long arr[n+1];
    long sum[n+1];
    sum[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i-1] + arr[i];
    }
    cout << "\n";
    for (int i = n; i > 1; i--) {
        for (int j = 1; j <= i; j++) {
            if ((sum[i] - sum[j-1]) % 3 == 0) count++;
        }
    }
    cout << count;
}

これはブルートフォスが一つ一つ訪問する方法です.
もちろんタイムアウトです.これで解けばゴール3ではない.

書き込みモジュール演算

検索結果によると、この問題は
PrefixSum[j]-PrefixSum[i]%MOD=0に満足している場合は、
PrefixSum[j]%MOD=PrefixSum[i]%MODも満足です.理解してこそ解けます.
じゃ、ゆっくり見ましょう.
例:

5 3
1 2 3 1 2

はい.
各数字と接頭辞Sumを表に表示すると、

0 1 2 3 4 5
0 1 2 3 1 2 
0 1 3 6 7 9

いいですよ.
ここでprefixSumの全てのmodを以下のように処理する.

0 1 2 3 4 5
0 1 2 3 1 2 
0 1 0 0 1 0

ここで上の条件j%mod=i%modを検索
1-1人(1,4)
0-0人(2,3)(2,5)(3,5)
全部で4つ存在します.
また、これらの接頭辞%mod=0は、1番目の要素からn番目の要素までの和がmod 0であることを示すため、それぞれ3つ加算される.
したがって、1+3+3=7となります.

도움이 된 코드 (https://cocoon1787.tistory.com/396)

#include<iostream>
#include <algorithm>
using namespace std;

long long n, m, val, sum;
long long cnt[1001];
long long ans = 0;

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> val;
        sum += val;
        cnt[sum % m]++;
    }
    
    ans += cnt[0];
	for (int i = 0; i <= 1000; i++) {
		ans += cnt[i] * (cnt[i] - 1) / 2;
	}
	
	cout << ans;
}

私のミス.

arr宣言はmain以外ではなく,中に近づくと0に初期化できない.

10^3まで勝つ必要はない.どうせmodmの最大値はm-1です.

arr,sum arrayはやりすぎた.

#include <iostream>
using namespace std;

int arr1[10];

int main() {
    int arr2[10];
    
    for (int i = 0; i < 10; i++) {
        cout << arr1[i] << " ";
    }
    cout << "\n";
    for (int i = 0; i < 10; i++) {
        cout << arr2[i] << " ";
    }
}

0 0 0 0 0 0 0 0 0 0 
875763392 383 1037047033 32758 1 0 7 0 875763360 383 

ご覧のように、外部宣言のarr 1はすべて0に初期化され、内部宣言のarr[2]は1つもできません.

整理する

原理さえわかれば解けると思いましたが、知らなかったので殴られました.