QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#128627#4794. Salajtraining4usacoWA 1ms3492kbC++171.5kb2023-07-21 14:02:342023-07-21 14:02:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-21 14:02:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3492kb
  • [2023-07-21 14:02:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 55;

int n, m, mod;
int dp[MAXN][MAXN];
int pref[MAXN][MAXN];

void solve() {
    cin >> n >> m >> mod;
    
    for(int i = 0; i <= n; ++i) {
        for(int j = 0; j <= n; ++j) {
            dp[i][j] = pref[i][j] = 0;
        }
    }
    
    dp[0][1] = 1;
    for(int j = 1; j <= n; ++j) {
        for(int i = n - 1; i >= 0; --i) {
            pref[i][j] = (pref[i + 1][j] + dp[i][j]) % mod;
        }
    }
	
	for(int i = 1; i <= m; ++i) {
	    for(int j = n - 1; j >= 0; --j) {
	        for(int k = n; k >= j + 1; --k) {
	            if(i <= j * (j - 1) / 2 + (k - j) * (k - 1) + (n - k) * (n - k - 1) / 2) {
	                if(j) dp[j][k] = dp[j - 1][k - 1];
	                else dp[j][k] = 0;
	                if(k == n) dp[j][k] += dp[j][n];
	                
	                dp[j][k] += pref[j + 1][k];
	                dp[j][k] %= mod;
	            }
	            else {
	                dp[j][k] = 0;
	            }
	        }
	    }
	    
	    for(int k = 1; k <= n; ++k) {
	        for(int j = n - 1; j >= 0; --j) {
	            pref[j][k] = pref[j + 1][k] + dp[j][k];
	            pref[j][k] %= mod;
	        }
	    }
	    
	    int ans = 0;
	    for(int j = 1; j <= n; ++j) {
	        ans += pref[0][j]; ans %= mod;
	    }
	    cout << ans << " ";
	}
	cout << endl;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int t; cin >> t;
    while(t--) solve();
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3492kb

input:

2
5 10 666013
6 9 10

output:

1 2 4 10 30 65 70 28 0 0 
1 2 4 9 2 5 5 4 2 

result:

wrong answer 4th numbers differ - expected: '9', found: '10'